이지코딩

그리디 알고리즘을 사용하는 문제였다. 처음에는 무작정 회의 시간이 가장 짧은것 순으로 붙이면 되겠다 라고 생각 했다. 하지만, 순서가 정해져야 하므로 말도 안되는 방법이다. 이 문제의 가장 중요한 부분은 "가장 먼저 끝나는 회의"의 순서를 찾아야 한다는 것이다. 먼저 끝나는 회의를 찾고, 끝나는 시간 이후에 가장 먼저 시작하는 회의를 찾는 것을 반복하면 이 문제를 해결할 수 있다. 만약 먼저 끝나는 회의의 정렬을 위해 퀵소트를 사용한다면, 워스트 케이스의 경우 O(N^2)의 시간 복잡도를 가지게 되므로 시간이 부족하게 된다. 이때문에 C++ 라이브러리에 있는 sort()를 사용하였다. 개인적으로 틀린 부분은 회의의 시작시간과 끝나는 시간이 같은 경우의 예외 사항때문에 많이 틀렸다. (5,8) (8,8) ..

BFS를 처음 배웠을때는 무작정 돌리면 끝나는 건줄 알았는데... 이걸 또 응용하는 문제들이 생겨버릴줄을 몰랐다. 문제의 핵심은 "외부 공기와 첩촉한 부분"만 시간이 지날수록 없어진다는 것이다. 위 처럼 중간에 구멍이 있을 경우에는 외부공기와 차단되어있기에 구멍과 맞닿아 있는 부분은 녹아내리지 않는다. 그냥 [0][0] 위치부터 외부 공기를 계속 BFS를 통해 점령해가면서 접촉하는 치즈를 시간별로 녹이는 방법이 정석적일 수도 있으나, 치즈의 모양이 복잡할 경우 시간 초과가 날 수도 있을것 같아 새로운 방식으로 접근하였다. 먼저, [0][0]을 시작으로 BFS를 시작하여 외부 공기와 맞닿는 치즈의 테두리를 찾아낸다. 이후에는 찾아낸 테두리를 외부 공기라고 생각하고, BFS를 통해 또 맞닿아 있는 치즈를 찾..

단순 미로찾기처럼 한 점에서 마지막 점까지 찾는 BFS가 아닌, 동시에 여러 시작점에서 BFS가 적용되야하는 문제다. 물이 차기 시작하는 점이 여러곳 이기에 각자 일분마다 각각 BFS를 통해 확장해 가고, 비버 또한 일분마다 BFS를 통해 물을 피해 확장해나가야 한다. 미로찾기 BFS처럼 한개의 while을 통해 이 문제를 풀려고 한다면 다음 시간에 물이 찰 곳을 알지 못해 비버가 엉뚱한 위치로 이동하게 된다. 이를 위해 여러개의 물, 비버의 BFS를 돌릴 여러개의 큐를 만들고, 각 시간마다 각 큐를 BFS를 통해 확장 시켜야한다. 입력 데이터를 받을때 몇개의 물로 차는 구역의 수를 알 수 없으므로 큐의 갯수를 미리 정할 수 없다. 이를 위해 필요시 큐를 생성하고, 각 물이 차는 지역의 큐를 모은 벡터와..

손풀기용 브론즈 문제!! 딱 문제 보자마자 느껴지는 브루트포스. 최대 자연수가 1,000,000 이므로 생성자의 최대 자리수는 6자리 이고, 각 자리는 0부터 9까지 10개 이므로, 6중 for문을 사용한다 해도 시간복잡도는 10^6 이므로, 시간제한에 훨씬 못미친다. 즉, 6중 for문을 사용하는것이 제일 간편하다. 생성자의 각 자리수를 a~f까지 설정하고 모든 경우의 분해합을 확인하고, 없을경우 0을 출력하면 끝! #include using namespace std; void Solve(int n) { int _tem = 0; for (int a = 0; a < 10 && _tem==0 ; a++) { for (int b = 0; b < 10 && _tem == 0; b++) { for (int c ..

미로에서 최단거리를 찾는 법은 BFS를 사용하면 간단하게 풀리지만, 벽을 뚫고 다닌다면 이야기가 달라진다.... 그런데 벽을 또 한번만 뚫을 수 있다고 한다..... 벽을 뚫었을 경우에 대한 플래그를 어떻게 활용을 해야 한다는것은 알겠지만 4방향에서 어느곳을 뚫어야 할지 선택하는것은 불가능 하므로, 모든 경우의 수를 따져봐야 한다. 그래서 방문체크를 하는 배열에 차원을 더해 플래그를 표시하여 모든 곳에서 플래그를 볼 수 있도록 하였다. 또한, 전에 풀었던 문제들의 다른 솔루션을 보았더니 4방향을 체크하는 것을 for문을 사용하여 더욱 짧고 직관적으로 작성하는 방법이 있기에 그것또한 사용하였다. 세상은 넓고 고수는 많다.... BFS를 사용하여 최단거리를 찾는 방법은 똑같지만, 벽을 뚫고 왔는지, 아닌지를..

그냥 문제를 읽으면 수학이나 규칙을 찾는것 같지만, 그래프탐색을 탐색해서, 계층구조를 탐색하고, 몇번째 계층에 k가 있는지 찾아내는 문제이다. 그러므로 BFS(너비우선탐색)을 사용하는 문제이다. 예시로 문제를 설명해보자. 입력 : 8 20 위와 같은 경우에는, 8 - 9 - 10 - 20 이므로, 3번만에 목적지에 도착할 수 있다. 이처럼 시작값 부터 모든 수를 탐색 해야 한다. 또한, 몇번만에 가는지를 알아야 한다. 위의 모든 조건을 한번에 해결할 수 있는 방법은 BFS 이다. 아래 그래프를 보자. 이제 계층구조가 한눈에 보인다. 8을 0층으로 새각했을때, 20은 3층에 있다. 즉, 최단거리가 3이라고 생각 할 수 있다. 이미 방문 되어있는 값은 더욱 적은 횟수로 도착할 수 있다는 것이므로, 재방문 하..

이전 글의 3차원 문제이다. 전 문제에서 배열 크기와 조건문만 추가 되었다. 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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 #include #include #include using na..

BFS를 사용하는 문제였다. 이런저런 조건이 많이 붙어 코드들이 조금 길어졌다.... 전반적으로 전문제에서도 사용했던 BFS와 비슷했다. 하지만, 익은 토마토의 위치(1)들이 여러개 있으므로, 시작부터 Queue에 좌표들을 넣어놓는 과정이 필수이다. 토마토가 익는 시점을 알기위해 max 값을 방문시마다 업데이트를 해주고, 모든 토마토가 익었는지를 판별하는 부분들이 추가되어 추가적인 코드들이 필요했다. 일단, 모든 토마토가 익었는지를 판단하기 위해서 방문을 하거나, -1(벽)입 부분을 모두 count 하여 m*n과 비교하였다. 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 34 35 36 37..