본문 바로가기

Algorithm125

[코딩 + 알고리즘 완주반] 24일차. 백트래킹 # 백트래킹 - 제약조건만족 문제에서 해를 찾기 위한 전략 - 해를 찾기 위해 조건을 점진적으로 체크하다가 해당 후보군이 제약조건을 만족할 수 없다고 판단하는 즉시 backtrack( 다시 이 후보군을 체크하지 않음) 하고 다른 후보군으로 넘어가 최적의 해를 찾는 방법 - 모든 경우의 수를 상태공간트리 (State Space Tree) 를 통해 표현 - 각 후보군을 DFS 방식으로 확인 - Promising : 해당 루트가 조건에 맞는지 검사하는 기법 - Pruning (가지치기) : 조건에 맞지 않으면포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법 # N-Queen 문제 N*N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제 퀸 : 수직, 수평, 대각선 이동 가능 Pr.. 2021. 4. 14.
[코딩 + 알고리즘 완주반] 23일차. 최소 신장 트리 - 프림 알고리즘 (Prim's algorithm) # 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방법 ( 크루스칼 알고리즘은 전체에서 가장 작은 간선) 1. 임의의 정점을 선택하여 연결된 노드 집합에 삽입 2. 선택한 정점에 연결된 간선들을 간선 리스트에 삽입 3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서 ( 전에 넣었던 간선들 포함 간선리스트에서 가장 최소인 값 ) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합에 이미 있다면 skip (cycle 방지) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합에 있지 않다면 해당 간선을 선택 ( 최소신장트리에 삽입 ) (해당 간선에.. 2021. 4. 13.
❗️[LEET CODE] 332. Reconstruct Itinerary # Problem You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexic.. 2021. 4. 10.
[코딩 + 알고리즘 완주반] 22일차. 최소 신장 트리 # 신장 트리 (Spanning Tree) 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 모든 노드 포함, 모든 노드 서로 연결, 사이클 존재하지 않음 # 최소 신장 트리 (Minimum Spanning Tree, MST) 가능한 신장 트리 중에서 간선의 가중치 합이 최소인 Spanning Tree Kruskal's algorithm(크루스칼 알고리즘), Prim's algorithm(프림 알고리즘) # Kruskal's algorithm(크루스칼 알고리즘) 가중치가 가장 작은 간선부터 연결 ( 사이클일 경우 넘어감 ) # Union-Find 알고리즘 - 사이클이 생기는지 확인하는 알고리즘 Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘 Di.. 2021. 4. 9.
[LEET CODE] 77. Combinations # Problem Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]. You may return the answer in any order. Constraints: 1 2021. 4. 9.
[코딩 + 알고리즘 완주반] 21일차. 최단 경로 알고리즘 # 최단 경로 문제 두 노드를 잇는 가장 짧은 경로 찾기 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로 # 단일 출발 및 단일 도착 최단 경로 문제 특정 노드에서 특정 노드에 도착하는 가장 짧은 경로 찾기 # 단일 출발 최단 경로 문제 특정노드와 그래프 내 모든 노드 각각의 가장 짧은 경로 찾기 # 전체 쌍 최단 경로 그래프 내 모든 노드 쌍에 대한 최단 경로 찾기 # 다익스트라 알고리즘 - 너비우선 탐색(BFS)과 유사 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리 구하기 (단일 출발 최단 경로 문제) 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를 갱신 # 우선순위 큐를 활용한 다익스트라 알고리즘 초기 첫 정점의 거리는 0, 나머지는 무한대로 저장 우선.. 2021. 4. 9.
반응형

티스토리툴바