본문 바로가기

알고리즘78

16953번 - A->B 문제: 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.2를 곱한다.1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최 솟값에 1을 더한 값을 출력하라. 풀이:비록 dfs, bfs 과정에 나와있으나, 전혀 쓰지 않는것이 더 좋은 방법이다.최솟값이라는 말이 잘못된 것이, 하나의 경우밖에 나오지 않는다. 이유는 예제 3을 보면 알 것이다.예제 3의 예시에는 100 → 200 → 2001 → 4002 → 40021 이 나와있다.100부터 시작하지말고 40021부터 시작해보자.40021 → 4002 →  2001 →  200 →  100그렇다면 이때 경우는 2로 나눈다.가장 오른쪽에서 1을 뺀다.이 두가지이다. 2로 나누려면 짝수여야 하며, 1을 오른쪽에서 빼려면 한.. 2024. 7. 25.
1743번, 2606번 - DFS, BFS 오늘은 실버 고티어 문제 두 문제를 풀었다.최근 DFS, BFS를 많이 풀다 보니, 푸는 시간도 줄었고, 큰 고민도 하지 않았다. 1745번 - 음식물 피하기문제:N x M 사이즈의 지도에 음식물이 있는 위치가 K 번 주어진다.이때 가장 큰 음식물의 크기를 구하여라. 풀이:힌트를 보면 그동안 푼 문제들과 크게 다르지 않다는 것을 알 수 있을 것이다. 특히 아래 문제와 매우 비슷하다.1303번 - 4방향 탐색(dfs) (tistory.com) 과정은 아래와 같다.1. 저장 시 queue 형태에 저장해준다.2. 모두 저장이 끝난 후, poll() 한 좌표에 이전에 방문한 적이 없다면,     해당 좌표와 연결된 음식물의 크기를 끝까지 추적하는 함수를 호출한다.3. queue가 빌 동안 2번 과정을 반복해준다.. 2024. 7. 23.
2178 - 미로 탐색(bfs) 실버1 문제이다. 문제:N, M 크기의 미로가 주어진다. 미로에서 1은 지나갈 수 있는 곳이고, 0은 막힌 곳이다.(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하시오  풀이:미로를 이동하는 방법은 무었일까? 당연하게도 지나갈 수 있는 길로 계속해서 이동하는 것이다.그렇다면 최소 거리를 구하는 방법은 무엇일까? 다음 과정을 살펴보자. 1. 시작 위치는 (1,1)이다.2. 시작위치에서 갈 수 있는 위치는 (2, 1) (1, 2)이다. 둘다 한칸만 이동하면 된다.3. 이후 (1, 2)에서 이동 할 수 있는 위치는 (2, 2)이다.4. (2, 1)에서 이동 가능한 위치는 (2, 2), (3,1) 이며, 이중 (2, 2)는 이동할 필요가 없다.     이미 (1,1)에서.. 2024. 7. 22.
1303번 - 4방향 탐색(dfs) 문제:위의 입력과 같이 주어진다.가로, 세로가 N, M으로 주어진다.다음 M개 줄에 B와 W가 적혀져 있으며, N개가 뭉쳐있을 때는 N^2의 위력을 낼 수 있다.W와 B의 위력을 알아내라. 풀이:어떤 문자가 모여있는 것은 해당 문자 주변을 탐색해서 찾아내야 할 것이다.고로 아래와 같은 과정으로 생각해보았다. 현재 위치에서 4방향(상, 하, 좌, 우)으로 이동하면서 같은 문자(B 또는 W)를 찾는다.이동할 수 있는 방향으로 이동해 다시 4방향(상, 하, 좌, 우)를 둘러본다. 다시 돌아가지 않기 위해 들렸던 위치에는 흔적을 남긴다.더이상 이동 할 수 없다면, (해당 구역의 합)^2을 저장한다.이렇게 생각해보니까 dfs()를 사용하고 있다는 것을 눈치챘다.가능한 한 깊이 있는 노드를 먼저 탐색하고, 더 이상.. 2024. 7. 20.

티스토리툴바