Algorithm/BOJ172 [BOJ]2230번: 수 고르기 문제: https://www.acmicpc.net/problem/2230 기본적인 투 포인터 문제입니다. start와 end을 조절하면서 차이가 M이상인 경우를 찾습니다. 1. 차이가 M을 초과한다면 => start를 밀어서 차를 줄입니다. 2. 차이가 M보다 작다면 => end를 밀어서 차를 늘려봅니다. 3. 차이가 M이라면 => 답을 찾았으므로 루프를 빠져나옵니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ2230.java 2022. 3. 29. [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. [BOJ]1719번: 택배 문제: https://www.acmicpc.net/problem/1719 다익스트라로 해결한 문제입니다. 임의의 A->B 두 순서쌍 경로 사이에 가장 먼저 방문하게 되는 노드를 구해야하는 문제입니다. 다익스트라를 사용하면 임의의 노드 A에 대해 나머지 노드에 대한 최단 경로 + 방문 정보를 저장할 수 있습니다. 그래서 N 개의 노드에 대해 N번 다익스트라를 돌린 후 1회 다익스트라 수행 때 마다 i번째 노드에서 나머지 노드를 방문할 때 최초로 방문해야 하는 노드 정보를 저장합니다. N번을 모두 돌리게 되면 2차원 배열 정답을 완성할 수 있습니다. N제한이 작으므로 log(V*Elog(V)로도 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/.. 2022. 3. 23. 이전 1 ··· 3 4 5 6 7 8 9 ··· 43 다음
