알고리즘 (403) 썸네일형 리스트형 02. 분할 정복 예제 - 1 [1. 예제 => QUADTREE] 그래프와 순회. [16928] [1. 문제 설명] 1번 칸에서 시작해서 주사위를 굴려 나온 수 만큼 이동 하여, 100번 칸에 도달 할 때, 주사위를 굴려야 하는 최소 횟수 (특정 칸에서는 사다리를 타고 앞쪽 칸 으로 이동하거나, 뱀을 타고 뒤쪽 칸으로 이동 할 수 있다.) [2. 풀이 접근] 문제 상에서는 10x10 크기의 게임판이라는 표현이 있지만, 10x10 의 2차원 배열로 게임판을 모델링 할 필요는 없다. 사다리와 뱀에 대한 정보를 따로 취급 할 필요는 없다. 어차피 특정 칸으로 점프 하는 개념이기 때문이다. bfs 로 풀어야 하는 이유(?) 일단 어떤 칸에서 +1, +2, ... +6 만큼 떨어진 위치로 이동하는데 필요한 비용은 모두 같다.(edge 에 별다른 weight 가 없다.) 특정 노드까지 최대한 빨리 도달해야 한.. 그래프와 순회. [7576] [1. 문제 설명] 창고 내 한 격자에 토마토 한개를 보관 할 수 있다. 익은 토마토 하나는 인접한 곳에 익지 않은 토마토를 익게 할 수 있다. 창고 내 모든 토마토가 익는데 걸리는 최소 일수를 구하도록 하고, 모든 토마토가 익을 수 없는 경우 -1 을 출력 한다. [2. 풀이 접근] 잘못 된 접근 아직 방문하지 않은 좌표 중, 익은 토마토 위치에서 bfs 를 시작, 이 과정을 마지막 좌표까지 반복 => 처음에 익은 상태에 모든 토마토에서 이 과정이 동시에 시작되어야 함. => 위 방법은 잘못된 계산을 유도할 수 있음. 아래와 같이 A 와 B 가 모두 익은 상태인 경우, x3 가 익는 시점은 3 이 아니라 1 이다. => A - x1 - x2 - x3 - B 올바른 접근 최초 익은 토마토의 위치를 모두 .. 02. 분할 정복 [1. 개요] 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤, 각 문제에 대한 답을 재귀호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산 여기서 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 것이 아니라 거의 같은 크기의 부분 문제로 나누는 것 (=> 보통 절반씩 나눔 => O(logn)) 적용을 위해서는 문제에 몇 가지 특성이 성립해야 한다. 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다. => 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다. 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다. 보통 같은 작업을 더 빠르게 처리해 준다. [2. 구성 요소] Divide => 문제를 더 작은 문제로 .. 01 완전 탐색 예제 - 3 [예제 => CLOCKSYNC] 01. 완전 탐색 예제 - 2 [예제 => BOARDCOVER] 01. 완전 탐색 예제 - 1 [예제 1 => PICNIC] DFS 특성 DFS를 재귀없이 구현 시 유의점 https://testkernelv2.tistory.com/323 BFS 의 특성 https://testkernelv2.tistory.com/326 그래프와 순회. [7562] [1. 문제 설명] 현재 나이트 위치에서 다음 나이트 위치까지 이동 할 때, 필요한 최소 이동 횟수 [2. 풀이 접근] BFS 탐색은 DFS 와 달리 특별한 성질이 있다. 그 성질은 각 정점을 최단경로 방문한다는 것이다. (단, 이 경우 Edge 의 weight 라는 개념이 없거나, 모든 weight 가 같아야 한다.) 아래와 같은 그래프를 정점1에서 시작해서 DFS 로 탐색 할 때 (인접한 정점을 오름차순으로 방문한다 가정) 정점6에 방문하기 위해서는 4개의 edge 를 거쳐야만 한다. 하지만, BFS로 탐색 시, 총 2개의 edge 만을 거치면 된다. 따라서, bfs 로 나이트를 특정 위치에 도달 할 때 가지 각 방향으로 이동시키면 된다. [3. 코드] 이전 1 ··· 23 24 25 26 27 28 29 ··· 41 다음
