알고리즘 노트/BOJ (22) 썸네일형 리스트형 BOJ 1992: DFS와 BFS - 파이썬(Python) https://www.acmicpc.net/problem/1260DFS와 BFS를 구현하여 그래프 순회 결과를 출력하는 문제이다. DFS와 BFS는 각각 무엇인지 알아보자. DFS란 "Depth First Search"의 약자로 "깊이 우선 탐색"이라고도 한다. 해당 알고리즘의 예시를 문제에서 제시한 예시를 이용하여 작동 방식을 살펴보자.아래 그래프는 문제에서 제시한 입력을 기반으로 구성한 그래프 그림이다. 문제에서 제시한 시작 node는 1이므로 1부터 시작하자.다음 node는 어디로 진행해야 할까? 문제에서 여러 node와 연결되어 있다면 값이 작은 node를 우선 진행한다고 하였으므로 2로 진행하면 된다.그다음은 2에서 갈 수 있는 node는 4밖에 없으므로 4로 진행하면 된다.이제 4에서 진행할.. BOJ 1992: 쿼드트리 - 파이썬(Python) https://www.acmicpc.net/problem/19922차원 배열을 문제에서 제시하는 방법을 이용하여 1차원 배열로 압축하는 문제이다. 문제에서 제시한 예시를 살펴보고 규칙을 찾아보자. 1번째 단계는 압축할 수 없다. 왜냐하면 0과 1이 모두 섞여있기 때문이다. 2단계를 진행하기 위해 대상 배열을 4개의 영역으로 분할하자.해당 배열에서 왼쪽 위와 오른쪽 아래는 각각 0, 1로 압축할 수 있고, 나머지는 다시 분할해야 할 것이다. 우선 중간 결과는 아래처럼 나올 것이다.$$(0(????)1)$$ 이제 3단계를 진행해 보자. 2단계에서 완료된 왼쪽 위와 오른쪽 아래를 제외한 나머지 영역에 대해서만 진행하면 충분하다. 진행 완료한 칸은 회색으로 표시하였다. 아래 그림은 각 영역에 대해 분할한 모습이.. BOJ 10830: 행렬 제곱 - 파이썬(Python) https://www.acmicpc.net/problem/10830크기가 $N \times N$인 행렬 $A$의 $B$제곱인 $A^B$를 구하는 문제이다. 단순 곱을 하게 된다면 행렬 곱의 시간복잡도 $O(N^3)$을 B번 진행하게 되므로 $O(n^3 \times B)$가 될 것이다. 이는 제한 시간인 1초 이내로 실행할 수 없는 시간복잡도이다. 그렇다면 어떻게해야 시간복잡도를 줄일 수 있을까? "BOJ 1629: 곱셈" 문제에서 사용했던 "분할 정복"을 적용한 곱셈을 행렬 버전으로 적용하면 될 것 같다고 생각할 수 있을 것이다. 즉, 아래의 식을 이용하면 답을 구할 수 있다.$A^B = A^\frac{B}{2} \times A^\frac{B}{2}$$A^B = A \times A^{floor(\fra.. BOJ 2293: 동전 1- 파이썬(Python) https://www.acmicpc.net/problem/2293n가지의 동전을 이용해서 k원을 만들 수 있는 경우의 수를 구하는 문제이다. 문제에서 제시한 예시를 이용하여 분석해보자. 초기 상태는 아래의 그림처럼 구성할 수 있을 것이다. 우선, 사용 가능한 동전들을 순서대로 사용해서 1부터 시작하여 10까지 진행하는 것을 반복하면 될 것이다. 우선 동전 1일 경우, 모든 k에서 만들 수 있는 경우의 수는 1이 될 것이다. 왜냐하면 각 k는 1을 k개 가지고 있는 것과 같기 때문이다. 이제 동전 2일 때에는 어떻게 처리해야 할까? 동전 2는 k가 2인 것 부터 시작하면 충분하다. 왜냐하면 2로는 1을 만들 수 없기 때문이다. 현재 k에서 2를 뺀 index에 위치한 값을 더하는 것이다. 이렇게 하면 어.. BOJ 1918: 후위 표기식- 파이썬(Python) https://www.acmicpc.net/problem/1918주어진 수식을 후위 표기식으로 변환하는 문제이다. 우선 "후위 표기식"이 무엇인지 알아보자. 후위 표기법은 연산자를 연산 대상의 뒤에 쓰는 연산 표기법이다. 예시로 아래의 그림의 수식을 후위 표기식으로 변경해 보자.그림에 나와있는 화살표로 연산자를 이동시키면 "ABC*+DE/-"가 변환 결과가 된다. 해당 문제는 대표적인 "스택으로 해결할 수 있는 문제"이다. 그렇다면 스택을 어떻게 적용해야 해결할 수 있는지 확인해 보자. 우선, 가장 간단한 형태의 수식인 $A+B$ 로 시작해 보자. 초기 상태는 아래 그림처럼 "input", "stack", "result"로 구성할 수 있을 것이다. 이제 input의 index 순서대로 변환 과정을 진행해.. BOJ 11726: 2×n 타일링 - 파이썬(Python) https://www.acmicpc.net/problem/117262 x n 타일로 만들 수 있는 모든 경우의 수를 구하는 문제이다. 우선, 가장 간단한 경우들을 살펴보자. n = 1일 때에는 1가지 경우만 가능하다. 그렇다면 n = 2일 때에는 어떻게 구성될까? 해답은 아래의 2가지 경우가 가능하다. 이제 n = 3일 때에는 어떻게 구성될지 분석해보자. 우선, 가능한 모든 경우의 수는 아래의 그림과 같이 3가지이다. 위의 그림에서 규칙을 찾아보자. 2 x n 타일은 "가로로 2개" 또는 "세로로 1개"를 붙여서 구성할 수 있다는 것을 알 수 있다. 결과적으로, 아래의 식을 이용해서 문제를 해결할 수 있을 것이다. T[N] = T[N - 1] + T[N - 2]위의 접근법을 이용하여 코드로 구현한.. BOJ 1149: RGB거리 - 파이썬(Python) https://www.acmicpc.net/problem/1149아래의 조건을 만족하면서 최솟값을 구하는 문제이다.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.먼저, 모든 값이 0인 $N \times 3$ 배열을 구성하자. 맨 처음 index(즉, 0일 때)에는 입력으로 주어진 2중 배열의 0번째 배열의 값을 차례대로 저장한다. 그 다음, 아래의 점화식을 구성할 수 있을 것이다. 해당 점화식에서 i는 1 - N에서, j는 0 - 3 index에서 반복한다.cost[i][j] = a[i][j] + min(cost[i - 1][(j + 1) % 3], cost[i.. BOJ 2447: 별 찍기 - 10 - 파이썬(Python) https://www.acmicpc.net/problem/2447문제에서 제시한 규칙을 기반으로 별 찍기를 출력하는 문제이다. 우선 가장 간단한 형태부터 살펴보자. $N = 3$일 때를 살펴보자. 위의 그림에서, $i = 1, j = 1$(시작 $idx = 0$으로 가정) 일 때, 빈칸으로 변경해주어야 한다는 것을 알 수 있다. 이제 다음 형태를 살펴보자. N = 9일 때는 아래의 그림과 같이 구성될 것이다.해당 형태를 단계적으로 분석해보자. 우선, $3 \le i, j \le 5$ 부분에서는 모두 빈칸으로 설정되어야 한다는 것을 알 수 있다. 그다음에는 $N = 3$의 상태를 8개의 분할된 파트에서 각각 적용해 주면 되는 것으로 해석할 수 있다. 최종적으로, 적용 시작 지점을 좌상단 index(행과 .. 이전 1 2 3 다음