Elisom

백트래킹은 문제 해결 기법으로, 제약 조건 만족 문제에서 해를 찾기 위한 전략이다. 고려할 수 있는 모든 경우의 수를 상태 공간 트리(State Space Tree)를 통해 표현하여 각 후보군을 DFS 방식으로 탐색한다. Promising: 해당 루트가 조건에 맞는지 검사하는 기법 Pruning: 조건에 맞지 않으면 제거하고 다른 루트로 바로 넘어가 탐색 시간 절약하는 기법(가지치기) N Queen 문제 가장 대표적인 백트래킹 문제 유형. NxN 체스판에 N개의 Queen을 서로 공격할 수 없도록 배치하는 문제 ...체스에서 퀸은 가장 강력한 말인데, 수직/수평/대각선으로 이동 및 공격 가능함. 이 체스판 문제를 앞서 말한 대로 상태 공간 트리로 표현하고, Promising 및 Pruning을 하려면 아..

Prim's Algorithm은 먼저 다루었던 크루스칼 알고리즘과 같은 대표적인 최소 신장 트리 알고리즘이다. 프림 알고리즘이 크루스칼 알고리즘보다 조금 더 복잡하다. 두 알고리즘 모두 탐욕 알고리즘을 기반으로 하는데, Kruskal's algorithm은 단순히 가중치를 기준으로 sorting하여 작은 것부터 선택하며 MST를 구하지만, Prim's algorithm은 특정 정점에서 시작하여, 이 정점에 연결된 가장 작은 가중치의 간선을 선택하며 MST를 구한다. 하나의 정점을 정하고, 이 정점에 연결되어 있는 간선들을 리스트에 담은 후, 이 리스트에서 weight가 가장 작은 간선을 선택하여 cycle이 이루어지지 않는지 확인하고 연결한다. 이 때 간선들을 담는 리스트의 자료형으로 최소힙을 사용하면 ..

지난 Python 강의 기록에서 작성했던 Kruskal's algorithm에 대해 더 작성해보고자 한다. 패스트캠퍼스 Python 코딩테스트 강의 4주차 패스트캠퍼스 Python 코딩테스트 강의 [개발자 취업 합격 패스 with 코딩테스트, 기술면접]를 수강하며 정리한 글입니다🤓 Content 이번에는 앞서 배운 내용들을 바탕으로 고급 정렬 알고리즘을 배 elisom.tistory.com Kruskal's algorithm은 대표적인 최소 신장 트리 알고리즘이다. 신장 트리, Spanning tree. : 그래프의 모든 노드가 연결되어 있으며 트리의 속성을 만족하는 그래프 1. 모든 노드를 포함해야 함 2. 모든 노드가 서로 연결 3. 트리의 속성을 만족 (사이클x) 당장 눈앞의 최소 비용을 선택하여 ..