본문 바로가기

알고리즘261

[BOJ]11660번: 구간 합 구하기 5 문제: https://www.acmicpc.net/problem/11660 2차원 DP 문제입니다. dp[i][j] : board[i][j] ~ board[N][j] ~ board[i][N] ~ board[N][N]의 합 즉, 쉽게 말해서 board[i][j] 좌표에서 아래쪽과 오른쪽으로 직선을 그었을 때 만들어지는 직사각형 영역의 합을 가지고 있습니다. dp를 이렇게 정의하면 주어진 구간합은 아래와 같이 구할 수 있습니다. (r1,c1) ~ (r2,c2)의 구간합 = dp[r1][c1] - dp[r2+1][c1] - dp[r1][c2+1] + dp[r2+1][c2+1] 이 부분은 그림을 직접 그려보시면 좀 더 쉽게 이해하실 수 있을 겁니다. 그래서 O(M)에 해결할 수 있습니다. 코드: https://.. 2022. 3. 24.
[BOJ]9370번: 미확인 도착지 문제: https://www.acmicpc.net/problem/9370 아이디어가 필요한 최단경로 문제입니다. 시작점 S, 도착점 T 그리고 중간지점 노드를 G, H라 하겠습니다. 후보 T 노드를 가는 S->T 경로중에 G-H를 경유해서 가는 T노드가 몇 개 있는지 구하는 문제입니다. 일일이 지나온 경로를 저장해서 찾아도 되지만 그렇게 하면 시간초과가납니다. 해결방법은 S->T 경로를 다음과 같이 정의하는 것입니다. S->G->H->T 또는 S->H->G->T 다익스트라(start, end)의 리턴값을 출발 노드(start)부터 도착 노드(end)까지의 거리로 가정하겠습니다. 이 때 아래 조건을 만족하는 T를 전부 구하면 됩니다. 다익스트라(start: S, end: T) = 다익스트라(start: S.. 2022. 3. 24.
[PRGRMS]12946번: 하노이의 탑 문제: https://programmers.co.kr/learn/courses/30/lessons/12946 분할정복 문제입니다. N번째 원판을 1->3번으로 이동시키기 위해서는 아래와 같은 과정을 거칩니다. 1. 1~N-1번째까지의 원판을 1->2번으로 이동 2. N번째 원판을 1->3번으로 이동 3. 1~N-1번째까지의 원판을 2->3번으로 이동 그러면 다시 N-1번째 원판을 1->2번으로 이동시키기 위해서는 아래와 같은 과정을 거칩니다. 1. 1~N-2번째 원판을 1->3번으로 이동 2. N-1번재 원판을 1->2번으로 이동 3. 1~N-2번째 원판을 3->2번으로 이동 즉, 위 과정을 기저사례까지 반복하기 때문에 아래 두 가지 케이스를 나눠서 재귀로 풀면됩니다. 1. N번째에 할 일 2. 1~N-.. 2022. 3. 23.
[PRGRMS]43238번: 입국심사 문제: https://programmers.co.kr/learn/courses/30/lessons/43238 이분 탐색을 활용한 결정 문제입니다. 주어진 문제를 아래와 같이 바꿔봅니다. Q. 임의의 시간 X 분동안 심사관 전체는 몇 명을 입국심사 할 수 있는가? X = 28로 놓고 보면 times [7, 10] 이므로 28 / 7 = 4 28 / 10 = 2 28분동안 4 + 2 = 6명을 심사할 수 있습니다. X = 27은 27 / 7 = 3 27 / 10 = 2 27분동안 3 + 2 = 5명을 심사할 수 있습니다. 이렇게 X를 전체 범위에서 이분 탐색으로 탐색하면서 주어진 X분동안 N명이상을 심사할 수 있다면, 정답후보 X분을 더 줄여보면서 탐색을 하고 N명이상 심사할 수 없다면 X분을 늘려가면서 정.. 2022. 3. 23.

티스토리툴바