전체 글361 [BOJ]1940번: 주몽 문제: https://www.acmicpc.net/problem/1940 여러 가지로 해결할 수 있지만 저는 이분 탐색으로 해결하였습니다. 먼저 오름차순 정렬을 통해 이분 탐색을 할 수 있게 합니다. 루프를 한 번 돌면서 첫 번째 갑옷을 고르고, 나머지 후보 갑옷을 이분 탐색을 통해 logN에 탐색합니다. 그래서 두 갑옷의 쌍을 고르는 작업을 NlogN에 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1940.java 2022. 3. 29. [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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 91 다음
