Problem Solving (22) 썸네일형 리스트형 [ACMICPC] 2468 . 안전 영역 2468번 안전 영역 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 맵이 주어지고 4방탐색을 하는 간단한 방법으로 DFS,BFS가 있다. 이 문제의 경우에는 최단거리 측정이 필요 없고 반복되는 탐색을 재귀로 쉽게 구현이 가능하므로 DFS를 사용하기로 한다. 2. DFS 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 // main ... for(int i=1;i<=max_height;i++){ ans = Math.max(ans,solveByDfs(i)); } // main ... static int solveByDfs(int rain){ chk = new boolean[N+2][N+2]; in.. [ACMICPC] 2470 . 두 용액 2470번 두 용액 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 바로 떠오르는 방법은 이중 포문을 이용하여 두 원소를 선택하는 방법으로 O(N^2)안에 답을 찾을 수 있다. 그러나 N의 최대 제한이 10만이기 때문에 O(N^2)의 방법은 불가능하다. 다음으로 두 가지의 방법을 더 떠올릴 수 있다. 이분탐색 1부터 N까지 모든 원소에 대해서 해당 원소를 정해놓고, 그 원소와의 합이 0에 가까운 다른 원소를 찾을 때 정렬이 되어있는 배열에서는 이분탐색을 사용할 수 있다. 투포인터 l=0, r=N-1부터 시작하여 두 위치에 있는 원소의 합이 0보다 작거나 같으면 l의 인덱스값을 올리고, 반대의 경우 r의 인덱스값을 줄이면서 답을 갱신하면 답을 찾을 수 있다. 2. 이분탐색 코드 1234567891.. [ACMICPC] 5525 . IOIOI 5525번 IOIOI 문제 보러가기 🅰 설계 1. 어떤 방법을 쓸 것인가? 가장 간단한 방법으로 모든 index 위치에서 Pn이 포함되어 있는지 확인하는 방법을 생각할 수 있다. 약 O((2N+1)*M) = O(NM) 정도의 시간이 걸린다. 이 방법으로 서브태스크1은 통과할 수 있다. 그러나 서브태스크2는 O(NM) = O(10^6 * 10^6) = O(10^12) 정도가 걸려 위의 방법을 사용하여 통과할 수 없다. 다음으로 생각할 수 있는 것은 '확인한 지점을 다시 확인해야하나?'라는 의문을 가질 수 있다. 예를 들어 IOIOIOI라는 문자열이 있을 때 0번째 indexI부터 IOIOI까지 확인했다면 그 후로는 5번째 이전의 index는 확인할 필요가 없다. 이후에 OI가 붙는지 아닌지만 확인하면 된다.. [ACMICPC] 1389 . 케빈 베이컨의 6단계 법칙 1389번 케빈 베이컨의 6단계 법칙 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 각 번호에서 다른 번호로 이동하는 데 얼마나 걸리는지 확인하는 법으로 크게 두 가지로 생각했다. BFS 1부터 N까지의 점에서 각각 시작해서 다른 모든 점까지 도착하는 시간을 계산하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738static int solveByBfs(){ int ansval = Integer.MAX_VALUE; int ansnum = 0; for(int i=1;i tmp){ ansval = tmp; ansnum = i; } } return an.. [ACMICPC] 1992 . 쿼드트리 1992번 쿼드트리 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 정해진 범위를 탐색하는 행동은 같고, 그 범위 내에서 점이 모두 같지 않으면 4가지 범위로 나눠서 각 범위마다 다시 같은 행동을 반복한다. 재귀로 행동을 반복하면서 인자로 범위를 정해주는 방법을 생각할 수 있다. 2. 재귀 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 static void split(int sy,int sx,int ey,int ex,int size){ char pivot = map[sy][sx]; for(int i=sy;i [ACMICPC] 1931 . 회의실 배정 1931번 회의실 배정 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? 시작 시간과 종료 시간에 대해서 생각해 보자. 최대한 많은 회의 수를 정하는 데는 회의가 얼마나 긴지 짧은지는 상관이 없다. (0,100),(7,9),(4,11)의 회의들이 있을 때를 생각해 보자. 시작 시간을 기준으로 : 시작 시간이 가장 빠른 첫 번째 회의는 빨리 시작하지만 100에 끝나게 되어 이 회의를 선택할 경우 (0,100) 사이의 회의는 모두 쓸 수 없게 된다. 회의의 시작 시간이 아무리 빨라도 종료 시간이 늦으면 다른 회의를 선택하는 것이 좋다. 종료 시간을 기준으로 : 종료 시간이 가장 빠른 두 번째 회의를 선택하면 (7,9) 사이의 회의를 선택할 수 없다. 종료 시간이 빠른 대로 회의를 배정하면 그 종료 시.. [ACMICPC] 1012 . 유기농 배추 1012번 유기농배추 문제 보러가기 🅰 설계 1. 어떤 방법을 사용할 것인가? map을 만들고 4방향을 탐색하며 연결된 부분을 다 체크하고 답의 value를 올리는 방식을 생각할 수 있다. BFS : Queue에 위치를 넣으면서 방문한 map을 0으로 바꿔주면 된다. DFS : 재귀로 방문한 map을 0으로 바꿔주면 된다. DFS를 사용하기로 한다. Queue에 넣고 빼는 작업 없이 재귀로 map의 방문 체크만 하면 되기 때문에 더 간단하게 풀 수 있다. 2. 방문 체크 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 for(int i=1;i [ACMICPC] 1300 . K번째 수 1300번 K번째 수 문제 보러가기 🅰 설계 1. 어떤 방법을 쓸 것인가? 문제에서 주어지는 k는 최대 10^9 = 10억이다. NxN 행렬을 만들어서 직접 정렬해보는 방법은 할 수 없다. B 행렬은 정렬되어 있다. 정렬된 상태에서 빠르게 답을 찾는 방법으로 이분 탐색을 생각해 볼 수 있다. 2. 이분 탐색을 어떻게 적용하는가? A 행렬에서 모든 행을 돌면서, 각 행에 x보다 작거나 같은 숫자를 카운트하여 그 개수가 k보다 작으면 답이 될 수 없고, k보다 크거나 같으면 답이 될 수 있다. 위 방법을 이분 탐색으로 구현하면 된다. 시간 복잡도는 행의 개수 N에 이분탐색 범위 log(N*N)을 곱해 O(N*log(N^2)) = O(2N*log(N))이 된다. 3. 전체 코드 12345678910111213.. 이전 1 2 3 다음