문제 https://programmers.co.kr/learn/courses/30/lessons/43238 풀이 처음에 문제풀이 방법을 떠올리기 쉽지 않은 문제다. 풀이 시 다음 사람을 어떤 심사관에 배정할까 ? 라는 의문으로 시작하면 가능한 방법이 떠오르지 않는다. 이 문제는 파라메트릭 서치 개념을 사용해서 풀이할 수 있다. 파라메트릭 서치란 최적화 문제를 결정 문제로 바꾸어서 풀이하는 개념이다. 이 문제의 경우 "심사시간이 주어졌을 때, N명의 사람을 모두 심사할 수 있는가?" 라는 내용으로 주어진 시간 범위 내에서 이분탐색을 진행하며, N명의 사람을 심사할 수 있는가? 를 확인 후 N명의 사람을 모두 심사할 수 있는 시간들 중 최소값을 정답으로 결정하면 된다. 소스 코드 #include #inclu..
문제 https://programmers.co.kr/learn/courses/30/lessons/49189 N개의 노드 중 1번 노드와 가장 먼 거리의 노드수를 구하는 문제 문제 풀이 시작점이 정해져있고 최단거리로 이동할 경우 가장 먼 거리를 파악해야 한다. 1번 노드로부터 다익스트라 수행 후 가장 먼 거리를 가진 노드들의 수를 카운트하여 return 한다. 소스 코드 #include #include #include const int MAX_N = 20001; const int MAX_M = 50000; using namespace std; int solution(int n, vector edge) { vector adj[MAX_N]; int d[MAX_N]; int answer = 0; int maxD..
문제 https://www.acmicpc.net/problem/2170 풀이 시작하는 점을 1, 끝나는 점을 -1로 저장하고 스택을 이용해 겹치는 선분이 끝날 경우 길이를 구해줬습니다. 선분 A(1,3), 선분 B(4, 6) 을 예로 들면, 정점 1 스택에 push 정점 3 은 끝 점이므로 pop 하고 길이(3-1) 저장 정점 4 은 시작점이므로 push 정점 6 은 끝 점이므로 pop 하고 길이 (6,4) 저장 겹치는 경우도 손으로 해보면 올바르게 계산된다는 점을 알 수 있습니다. 소스코드 #include #include #include #include using namespace std; int n; vector points; int main(){ ios::sync_with_stdio(false..
문제 https://www.acmicpc.net/problem/7806 풀이 처음에는 n!을 기준으로 gcd(n,k) , gcd(n-1,k / gcd(n,k)) 이런 식으로 최대공약수를 구해나가려고 했습니다. 이런 식으로 구현하게 되면 시간초과가 발생합니다. 이 문제의 경우에는 K를 기준으로 소인수분해하고 해당 소수가 n!에 몇 개 존재하는 지 찾아내서 지수가 작은 수를 통해 최대공약수를 구하는 방식으로 구현해야 합니다. n! 을 소인수분해 할 때 일반적으로 사용되는 것처럼 소수로 계속 나누게 되면 엄청난 시간이 걸립니다. n! 을 소인수분해 할 때는 n / 소수^1 + n / 소수^2 + n / 소수^3 ... 하시면 n! 을 소인수분해 했을 때 소수 갯수를 구할 수 있습니다. 소스코드 #include..
문제 https://www.acmicpc.net/problem/14476 풀이 문제풀이를 완전탐색 알고리즘으로 생각을 해보면 1~N까지의 수를 하나씩 다 빼보고 그 중에 가장 큰 최대공약수를 가질 수 있는 수를 빼는 것입니다. 하지만 완전탐색의 경우 1~N까지 숫자를 빼는 것과 숫자를 뺀 나머지 수들의 최대공약수를 구하는 과정에 있어서 시간초과가 발생할 것이라고 생각 했습니다. 제 풀이는 1부터 N까지 모두 빼보는 것까지는 완전탐색과 똑같은 방법입니다. 다른 점은 Segement Tree 를 이용해서 1~N까지의 최대공약수를 미리 저장해놓는 것입니다. 현재 숫자를 빼고 Segement Tree를 Update 해주고 비교해주는 거라고 보시면 됩니다. 소스코드 #include #include using na..
문제 https://www.acmicpc.net/problem/6569 풀이 큰 직사각형의 상태를 0(빈 칸), 1(채운 칸) 으로 경우의 수를 계산해나갔습니다. 현재칸이 blockNum 일 때 너비 w만큼의 칸을 상태를 저장해놓고 상태에 따라 가능한 직사각형을 채운다고 생각하시면 됩니다. 예를 들어, 높이가 3 너비가 5이면 직사각형의 번호는 아래와 같습니다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0번째 칸에 높이 1, 너비 2 인 직사각형을 놓을 경우면 상태를 00011(10진수 3) 으로 표현하다고 생각하시면 됩니다. 소스코드 #include #include using namespace std; const int MAX_N = 11; long long gCache[(MAX_..
문제 https://www.acmicpc.net/problem/11727 풀이 취준생 때 이해하기 힘들어서 포기했던 문제다. 시간을 두고 천천히 그림을 그려가면서 생각해보면 점화식을 생각해낼 수 있습니다. 2x2 타일을 채우는 경우를 그림으로 그려보고, 2x3 을 채우는 방식을 생각해봅니다. 2x3은 앞 쪽에 2x1 타일을 채우고 나머지를 채우는 경우와 뒤 쪽에 2x1을 채우고 나머지를 채우는 경우로 생각 할 수 있습니다. 소스코드 // boj.kr/11727 // 2xn 타일링 #include using namespace std; #define MOD 10007 const int MAX_N = 1000; long long gCache[MAX_N+1]; int main(){ ios::sync_with_s..
문제 https://www.acmicpc.net/problem/1563 풀이 dynamic programming / recursion 을 통해 풀이 했습니다. gCache : day 에 출석, 지각, 결석 횟수 저장 recursion 함수를 통해 저장된 값이 있으면 활용하고 아닌 경우 다음날을 3가지 경우로 분기시켜 진행 시켰습니다. 출석하는 경우 (day + 1, attendance + 1, late, 0) ㄴ지각하는 경우 (day + 1, attendance, late +1, 0) 결석하는 경우 (day +1, attendance, late, absent+1) 소스코드 #include #include using namespace std; const int MAX_N = 1000 + 1; const i..
문제https://www.acmicpc.net/problem/15686풀이과정Dfs와 백트래킹을 통한 완전탐색으로 구현을 했습니다.M개의 치킨집을 골랐을 경우 최소거리의 합을 구하고 가장 작은 경우만 저장해서 출력했습니다.DFS와 백트래킹을 통한 완전탐색 문제를 풀어봤다면 푸실 수 있을 것 같습니다. 알고리즘 1(집), 2(치킨집) 일 경우 각각 person, chicken 벡터에 위치를 저장합니다. 재귀함수를 통해 M개의 치킨집을 선택합니다 person 벡터를 돌며 집과 선택된 치킨집의 거리 중 최소값만을 더합니다. 치킨집 M개를 뽑는 모든 경우를 탐색하고 최소거리의 합 중 가장 작은 값만 저장합니다. 소스코드#include #include #include using namespace std; #def..
문제https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu풀이모든 정점을 돌면서 Bfs로 서비스 영역을 늘려가는 식으로 구현했습니다.Bfs에서 현재 들어있는 큐의 사이즈만큼만 탐색을 한 뒤에 depth를 늘려줬습니다.이 때 depth 값이 서비스 영역의 크기 K와 똑같기 때문에 depth를 이용해 운영 비용을 계산했습니다.소스코드#include #include #include using namespace std; #define MAX_N 21 #define MIN_INF -987654321 int N, M; int city[MAX_N][MAX_N]; int memo[MAX_N + 1];..