본문 바로가기
반응형

Problem Solving242

백준 1766번 문제집 - C++(cpp) 풀이 1. 각 문제를 그래프의 정점으로 생각한다. 2. A번 문제를 B번 문제보다 먼저 푸는 것이 좋다면 A에서 B로 가는 방향 간선을 추가한다. 3. 우선순위 큐를 가지고 위상 정렬한다. 1. 각 문제를 그래프의 정점으로 생각한다. 선행 관계가 주어진 작업들의 작업 순서를 결정하는 것은 위상 정렬로 풀 수 있다. 먼저 주어진 상황을 그래프로 변환해야 한다. 각 문제를 정점으로 생각해준다. 2. A번 문제를 B번 문제보다 먼저 푸는 것이 좋다면 A에서 B로 가는 방향 간선을 추가한다. 그리고 A가 B보다 선행되어야 한다면, A에서 B로 가는 방향 간선을 추가한다. 3. 우선순위 큐를 가지고 위상 정렬한다. 완성된 그래프를 가지고 위상 정렬을 수행한다. 그런데 "가능하면 쉬운 문제부터 풀어야 한다."는 조건을 .. 2022. 2. 4.
백준 1007번 백터 매칭 - 스위프트(Swift) 풀이 1. 각 점을 위치 벡터로 생각한다. 2. 점 A에서 B로 가는 벡터는 (B 위치 벡터) - (A 위치 벡터)이다. 3. 절반을 역벡터로 만든 뒤 모든 벡터를 합치면 벡터 매칭에 있는 벡터의 합을 구할 수 있다. 1. 각 점을 위치 벡터로 생각한다. 먼저 각 점을 위치 벡터로 생각해줄 것이다. 2. 점 A에서 B로 가는 벡터는 (B 위치 벡터) - (A 위치 벡터)이다. 다음과 같은 성질을 이용할 것이다. 두 점 A, B를 골라 A→B 또는 B→A로 가도록 벡터로 잇는 작업은, 두 점 A, B를 고른 뒤 두 점으로 가는 위치 벡터 중 하나를 역벡터로 만드는 작업이라고 할 수 있다. 3. 절반을 역벡터로 만든 뒤 모든 벡터를 합치면 벡터 매칭에 있는 벡터의 합을 구할 수 있다. 결국 구해야 하는 것은 벡터.. 2022. 2. 4.
백준 2342번 Dance Dance Revolution - 스위프트(Swift) 풀이 1. dp(index, left, right) : 현재 두 발의 위치가 left, right일 때 arr[index...]를 모두 밟는 최소 비용 2. dp(index, left, right) = min(왼쪽 발을 움직일 때 비용, 오른쪽 발을 움직일 때 비용) 1. dp(index, left, right) : 현재 두 발의 위치가 left, right일 때 arr[index...]를 모두 밟는 최소 비용 현재의 움직임이 나중에 어떤 영향을 미칠지 예상할 수 없으므로 다이나믹 프로그래밍으로 해결할 수 있다. 현재 두 발의 위치가 left, right일 때 arr[index...]를 모두 밟는 최소 비용을 dp(index, left, right)라고 정의하자. 위치가 5가지이므로 총 5*5*100,000개.. 2022. 2. 3.
백준 2143번 두 배열의 합 - 스위프트(Swift) 풀이 1. A의 모든 부 배열에 대해 합을 구해 각 합을 만들 수 있는 경우의 수를 카운트해둔다. 2. B의 모든 부 배열에 대해 합을 구해 각 합을 만들 수 있는 경우의 수를 카운트해둔다. 3. A의 모든 부 배열합 sum에 대해 (A의 부 배열 합이 sum이 되는 경우의 수) X (B의 부 배열 합이 T-sum이 되는 경우의 수)를 더한다. 1. A의 모든 부 배열에 대해 합을 구해 각 합을 만들 수 있는 경우의 수를 카운트해둔다. N=1000이므로 O(N^2)으로 모든 부 배열을 다 고려해볼 수 있다. 모든 부 배열에 대해 합을 구하면서 그 합을 만들 수 있는 경우의 수를 카운트해준다. 부 배열 합이 sum이 되는 경우의 수(count)를 딕셔너리에 dict[sum] = count 형태로 저장해준다. 원.. 2022. 2. 3.
백준 1644번 소수의 연속합 - 스위프트(Swift) 풀이 1. 에라토스테네스의 체를 사용하여 4,000,000 이하인 소수 목록을 구한다. 2. 소수 목록에서 투 포인터를 사용하여 연속합이 N이 되는 경우를 모두 구한다. 1. 에라토스테네스의 체를 사용하여 4,000,000 이하인 소수 목록을 구한다. 일단 소수들을 구해야 한다. N=4,000,000이므로 4,000,000 이하인 소수 목록을 다 구한다. 에라토스테네스의 체를 사용하면 O(NloglogN)에 N이하인 모든 자연수에 대해 소수 여부를 구할 수 있다. 그리고 나서 소수들만 추려 배열을 만든다. 2. 소수 목록에서 투 포인터를 사용하여 연속합이 N이 되는 경우를 모두 구한다. 연속하는 모든 구간을 탐색하는 것은 불가능하다. 소수 개수(M)가 약 280,000개 이므로 O(M^2)의 시간 복잡도로는 .. 2022. 2. 3.
반응형

티스토리툴바