본문 바로가기

Problem Solving/BOJ228

백준 16724번 피리 부는 사나이 - 스위프트(Swift) 풀이 + 그림 설명 1. DFS를 돌면서 이어져있는 칸들을 Union한다. 각 집합마다 SAFE ZONE은 한 개만 있으면 된다. 2. 이미 방문한 점이더라도 Union은 하고 넘어간다. 3. 집합의 개수가 곧 SAFE ZONE의 개수이다. 1. DFS를 돌면서 이어져있는 칸들을 Union한다. 각 집합마다 SAFE ZONE은 한 개만 있으면 된다. 어떤 칸들이 하나의 경로로 이어져있다면 결국 경로 중 어느 칸에서 출발하더라도 계속 가다 보면 그 경로의 끝 칸에 도달하게 된다. 따라서 그 끝 칸에만 SAFE ZONE을 설치하면 된다. 한 경로로 이어져 있는 칸들을 하나의 집합으로 처리하기 위해 유니온 파인드를 사용한다. DFS를 돌면서 한 경로로 이어져있는 칸들을 모두 union 해준다. 2. 이미 방문한 점이더라도 Uni.. 2022. 2. 5.

백준 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.

이전 1 ··· 31 32 33 34 35 36 37 ··· 46 다음

티스토리툴바