코딩고치

백 트래킹 기법 백 트래킹 또는 퇴각 검색이라 칭함 제약 조건 만족 문제를 풀기 위한 전략 후보군의 제약 조건을 체크하다가 만족할 수 없다고 판단되면 backtrack (다시는 이 후보군을 체크하지 않음), 그 후 다른 후보군으로 넘어감 계산의 양을 줄일 수 있음 모든 경우의 수를 상태 공간 트리로 표현 각 후보군을 DFS로 탐색 제약기 맞지 않으면 해의 후보가 될만한 곳으로 넘어가서 탐색 Promising: 조건이 맞는지 검사 Pruning: 조건이 맞지 않으면 다른 루트로 가서 탐색, 시간 절약 DFS로 탐색을 진행하면서 조건에 부합하는지 체크하고 부합하지 않으면 다른 루트로 가서 DFS 탐색을 진행 N Queen 문제 NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제 Prun..

최소 신장 트리 신장 트리 그래프의 모든 노드가 서로 연결됨과 동시에 트리의 속성을 가지는 그래프. 조건 모든 노드가 연결 트리의 속성 (사이클을 가지지 않음) 최소 신장 트리 Minimum Spanning Tree (MST) 참고 : https://en.wikipedia.org/wiki/Minimum_spanning_tree 신장 트리 중에서 간선의 가중치의 합이 가장 작은 신장 트리 크루스칼 알고리즘 모든 노드를 독립적인 집합으로 만듦 간선을 최소 가중치를 가진 순서대로 정렬 이 노드 순서대로 노드를 연결 사이클이 생기지 않도록 주의 사이클이 생기면 제외를 한 후 다음 가중치를 가지는 간선을 이용하여 노드 연결 Union-Find 알고리즘 이용 참고 : https://ko.wikipedia.org/w..

최단 경로 알고리즘 최단 경로 문제 두 노드를 잇는 최단 경로 찾는 문제 가중치 그래프에서 가중치 합이 최소가 되는 것을 찾는 문제 문제 종류 단일 출발 및 단일 도착 문제 특정 노드 2개를 선택 후 가장 짧은 경로를 찾는 문제 단일 출발 문제 특정 노드 1개에서 다른 노드들 간 가장 짧은 경로를 찾는 문제 전체 쌍 문제 그래프 내 노드 쌍에 대한 최단 경로를 찾는 문제 다익스트라 알고리즘 단일 출발에 대한 답을 찾는 문제 첫 노드를 기준으로 인접한 노드를 추가해 가면서 최단 거리를 구해나가는 방법 너비 우선 탐색과 유사 우선순위 큐를 이용 1) 첫 노드를 기준으로 각 노드들 간의 거리를 저장하는 배열 생성 첫 노드의 거리는 0, 나머지는 무한대로 설정 (inf) 첫 정점 거리 (0)을 먼저 배열에 입력..

탐욕 알고리즘 최적의 해에 가까운 값을 구하기 위한 방법이다. 여러 경우가 있을 때 매 순간 조건에 맞는 최적의 경우를 찾아나가는 방식이다. 예시 동전 문제 지불해야 할 값이 6870원 일 때 10, 50, 100, 500원 동전으로 가장 적은 수의 동전으로 계산 가장 큰 동전부터 지불 coins = [500, 100, 50, 1] def coin_count(price, coins): coin_count = 0 ledger = list() coins.sort(reverse=True) # 내림 차순으로 정리 for coin in coins: coin_num = price // coin coin_count += coin_num price -= coin_num * coin ledger.append([coin,..