본문 바로가기
반응형

전체 글282

백준 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.
백준 12100번 2048 (Easy) - 스위프트(Swift) 풀이 + 그림 설명 1. 미는 방향으로 블록을 몬다. 2. 인접한 두 블록을 미는 방향으로 합칠 수 있으면 합친다. 3. 합치면서 생긴 빈자리를 없앤다. 4. 4^5가지 경우에 대해 전부 다 시뮬레이션(1-3과정)하여 최댓값을 구한다. 1. 미는 방향으로 블록을 몬다. 아래와 같은 보드 상태에서 위로 밀어야 하는 상황이다. 열 별로 차례로 밀어줄 것이다. 1열부터 밀어보자. 먼저 빈 공간이 없도록 윗방향으로 블록들을 몰아준다. 2. 인접한 두 블록을 미는 방향으로 합칠 수 있으면 합친다. 이제 합칠 차례이다. 만약 인접한 두 블록을 합칠 수 있는 경우 합친다. 미는 방향이 윗방향이기 때문에 윗블록이 남고 아랫 블록은 사라진다. 3. 합치면서 생긴 빈자리를 없앤다. 합치면서 생긴 빈자리를 또 메꿔주면 미는 작업이 끝난다. 나.. 2022. 1. 29.
반응형

티스토리툴바