알고리즘

문제 풀이 이분 탐색을 사용한다. 공유기를 설치할 간격을 이분 탐색으로 좁혀서 진행한다. 집의 좌표를 오름차순으로 정렬한다. 공유기를 설치할 수 있는 최소 간격과 최대 간격을 구한다. 최소 간격: 집 사이의 최소 거리인 1 최대 간격: 마지막 집과 처음 집 사이의 거리 설치할 간격을 이분 탐색으로 좁혀서 진행한다. 첫 집은 무조건 설치한다. 설치할 간격인 mid만큼 거리를 벌려서 공유기를 설치했을 때, 설치한 공유기의 수가 C이상인 경우 간격을 늘리고, 미만인 경우 간격을 줄인다. 설치한 공유기 수가 C를 만족한 경우 답을 갱신한다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); ci..

문제 풀이 다이나믹 프로그래밍 문제다. 모든 단계에서 모든 발의 위치의 최솟값을 cache로 담는다. 현재 단계를 검사할 때, 이전 단계의 cache를 사용한다. 이전 단계에서 발의 위치가 존재할 수 없는 것은 제외한다. 이전 단계에서 왼발/오른발을 현재 옮겨야 하는 위치로 옮겼을 때의 비용의 최솟값을 cache로담는다. 왼발을 움직이는 경우 cache[현재 단계][현재 옮겨야 하는 위치][오른발] = min( cache[현재 단계][현재 옮겨야 하는 위치][오른발], cache[이전 단계][이전 왼발의 위치][오른발] + (이전 왼발발에서 현재 옮겨야 하는 위치로의 비용) ) 오른발을 움직이는 경우 cache[현재 단계][왼발][현재 옮겨야 하는 위치] = min( cache[현재 단계][왼발][현재 ..

문제 풀이 방향 비순환 그래프와 위상 정렬 알고리즘을 사용한다. B를 거치기 위해서는 무조건 A가 먼저 거쳐야 한다. B의 indegree가 증가하고, A의 outdegree가 B로 저장된다. indegree가 0인 학생부터 queue에 넣는다. queue에서 나온 학생의 outdegree에 해당하는 학생의 indegree를 1차감한다. indegree가 0이 되면 queue에 넣는다. 코드 #include #include using namespace std; int indegree[32001]; vector outdegree[32001]; vector path; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int N..

문제 풀이 누적 합과 이분 탐색을 사용한다. 배열 A에서 얻을 수 있는 모든 부 배열의 합을 vector A에 저장한다. 배열 B에서 얻을 수 있는 모든 부 배열의 합을 vector B에 저장한다. 이분 탐색을 위해 vector B를 오름차순으로 정렬한다. upper_bound와 lower_bound로 (T - 현재 검사하는 vector A의 원소의 값)을 가지는 vector B의 원소의 수를 구한다. upper_bound는 현재 검사하는 벡터에서 N의 값을 초과하는 값의 첫 인덱스를 반환한다. lower_bound는 현재 검사하는 벡터에서 N의 값 이상의 값의 첫 인덱스를 반환한다. 코드 #include #include using namespace std; int A[1001]; vector sum_A..

문제 풀이 에라토스테네스의 체와 두 포인터 알고리즘을 사용한다. N까지 소수를 에라토스테네스의 체로 구한다. 가장 작은 소수인 2부터 두 포인터 알고리즘을 시작한다. (start, end = 2) start가 end 초과일 때까지 진행한다. start에서 end까지 소수의 합이 N이하라면 end를 다음 소수까지 증가시킨다. 초과라면 start를 다음 소수까지 증가시킨다. 코드 #include using namespace std; const int MAX = 4'000'001; bool prime[MAX]; // 에라토스테네스의 체 // N까지의 수 중 소수는 true로 표시 void eratosthenes(int N) { memset(prime, false, sizeof(prime)); for (int ..

문제 풀이 방향 비순환 그래프와 위상 정렬을 이용한다. indegree가 0인 노드부터 큐에 넣는다. 큐가 empty될 때까지 검사하며 하나씩 pop한다. 검사되는 노드인 current노드와 연결된 노드인 next의 indegree를 1감소 시킨다. next노드의 indegree가 0이 되었다면 큐에 넣는다. next노드까지 소모되는 시간은 (current노드 까지 소모 시간 + next노드의 build 시간)의 최대값이다. 코드 #include #include #include #include using namespace std; int N, K, W; int build_time[1001]; int indegree[1001]; vector outdegree[1001]; vector priority[100..

문제 풀이 분리 집합을 이용한다. 각 점이 하나의 노드이며, 입력이 간선이다. 간선을 들어오는 순서대로 사이클이 생기는 지 검사하면서 Union연산으로 노드를 잇는다. 코드 #include #include using namespace std; typedef struct { int x; int y; }edge; int parent[500'000]; int getParent(int n) { if (parent[n] == n) { return n; } return getParent(parent[n]); } bool cycle(int x, int y) { int p1 = getParent(x); int p2 = getParent(y); return p1 == p2; } void Union(int x, int y..

문제 풀이 다이나믹 프로그래밍을 사용한다. N번 집을 칠할 때, 1번 집의 색의 영향을 받는다. 1번 집을 R로 칠한 경우, G로 칠한 경우, B로 칠한 경우 세 가지를 모두 검사해야 한다. 1번 집을 칠한 색이외의 cache에는 충분히 큰 값을 두어 2번 집을 칠할 때 선택되지 않도록 해야한다. i번 집을 j색으로 칠했을 때의 최솟값은 i번 집을 j색으로 칠한 비용과 i - 1번 집을 j 이외의 색으로 칠한 비용의 합의 최솟값이다. N번 집은 1번 집을 칠했을 때의 색으론 칠할 수 없으니 그 경우는 제외해야 한다. 코드 #include #include #include using namespace std; int house[1001][3]; int cache[1001][3]; int main() { io..

문제 풀이 다이나믹 프로그래밍 문제로 S와 E가 입력될 때마다 처음부터 검사하면 시간초과이다. S와 E가 같다면 무조건 팰린드롬이다. S와 E가 1차이라면 num[S]와 num[E]만 검사하면 된다. S와 E에서부터 시작해서 num[S]와 num[E]가 같으면서 사이의 수열이 팰린드롬이라면 그 수열은 팰린드롬이다. 여기서 S와 E의 값을 각각 1늘리고 1줄이는 방식으로 검사하면서 num[S]와 num[E]가 같지않다면 그 수열은 팰린드롬이 아니다. '\n' 을 사용해야 한다. endl을 사용할 경우 시간초과가 발생한다. 코드 #include using namespace std; bool cache[2001][2001]; int num[2001]; int main() { ios_base::sync_with..

문제 풀이 다이나믹 프로그래밍 문제로 string 2차원 배열을 사용해서 cache와 같이 추가하면 시간초과가 발생한다. cache를 갱신시키면서 cache의 경로를 따로 저장하거나, 결과값에서부터 역추적하여 정답에 접근해야 한다. 코드 경로를 저장하는 방법 #include #include #include using namespace std; int cache[1001][1001]; // 경로를 저장하는 배열 pair path[1001][1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); string a; string b; cin >> a >> b; a = '0' + a; b = '0' + b; for (int ..