『コーディングテスト合格者になるためにーPython編』を精読すること

백트래킹-구현

주어진 배열이 queens = [2, 0, 3, 1]일 때, 인덱스는 행, 값은 열을 의미한다. 따라서 queens[2] = 3이므로, 2번 행에 있는 퀸은 3번 열에 위치한다. 즉, 해당 퀸의 좌표는 (2, 3)이다.   Q2. 현재 상태는 queens = [1, 3, ?, ?]이며, (2, 0)에 퀸을 놓는 상황을 가정한다. 이때 (2, 0)과 (0, 1)이 대각선 충돌인지 확인하기 위해 다음 수식을 적용한다. 행 차이: abs(2 - 0) = 2 열 차이: abs(0 - 1) = 1 두 값이 서로 같으면 대각선 충돌이지만, 여기서는 2 ≠ 1이므로 대각선 충돌이 아니다. 따라서 (2, 0)은 0번 행의 퀸과는 충돌하지 않는 위치이다.   Q3. Q2에서 확인한 결과 (2, 0)은 대각선 충돌이 발생하지 않으므로 유망한 위치이다. 따라서 이 경우에는 해당 위치에 퀸을 배치하고 다음 단계(3번 행)로 탐색을 진행해야 한다. 하지만 만약 (2, 0)이 충돌하는 위치였다면, 해

잠온 · 백트래킹-구현

拍手 0 · コメント 1

백트래킹-개념

백트래킹에서의 유망성 검사란 현재까지 구성한 부분 해가 이후의 선택을 통해 최종적인 정답으로 이어질 가능성이 있는지를 미리 판단하는 과정이다. 즉, 탐색을 진행하기 전에 해당 경로가 문제의 조건을 위반하는지 확인하고, 만약 이미 조건을 만족할 수 없는 상태라면 더 이상 깊이 탐색하지 않고 그 경로를 중단한다. 이를 통해 불필요한 탐색을 줄이고 효율적으로 해를 찾을 수 있다. 예를 들어 N-Queen 문제에서는 특정 위치에 퀸을 놓기 전에 같은 열이나 대각선 상에 이미 다른 퀸이 존재하는지를 검사하고, 이러한 조건을 만족하지 못하면 해당 위치는 유망하지 않다고 판단하여 탐색을 진행하지 않는다. 단순한 깊이 우선 탐색(브루트포스)과 백트래킹의 가장 큰 차이는 탐색 범위에 있다. 브루트포스 방식은 가능한 모든 경우의 수를 끝까지 탐색하기 때문에, 중간에 이미 정답이 될 수 없는 경우라도 끝까지 내려가 확인하게 된다. 반면, 백트래킹은 탐색 도중에 유망성 검사를 수행하여 더 이상 정

잠온 · 백트래킹-개념

拍手 0 · コメント 1

다익스트라-구현

처음 Home에서 B로 바로 가려면 비용이 5 발생한다. → distance[B] = 5 이후 Home에서 A를 거쳐 B로 가려면, Home에서 A로 가는데 2, A에서 B로 가는데 2, 총 비용이 4 발생한다. 이는 기존에 저장된 B까지의 거리 5보다 더 작으므로 B까지의 거리가 갱신된다. → distance[B] = 4 이 과정은 다익스트라 알고리즘의 greedy 특성을 잘 보여준다. 매 단계에서 현재까지 가장 비용이 적은 노드를 선택하고, 이를 통해 더 짧은 경로가 발견되면 기존 값을 갱신하면서 점진적으로 최적해에 도달하게 된다.   Q2. Home에서 School까지 도달할 수 있는 여러 경로 중 최소 비용 경로를 계산하면, Home → A → B → C → School 경로가 선택된다. 각 구간의 비용을 합하면 Home에서 A까지 2, A에서 B까지 2, B에서 C까지 1, C에서 School까지 3이므로 총 비용은 8이 된다. 따라서 Home에서 School까지의

잠온 · 다익스트라-구현

拍手 0 · コメント 1