본문 바로가기

프로그래밍/Python 알고리즘12

12. 알고리즘 고급 탐색, 최단 경로 알고리즘, 다익스트라 알고리즘 난이도 최상 1. 최단 경로 문제란? 최단 경로 문제란, 두 노드를 잇는 가장 짧은 경로를 찾는 문제다 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적이다. 최단 경로 문제 종류 1. 단일 출발 및 단일 도착 최단 경로문제 - 그래프 내의 특정 노드 u에서 출발해서, 또 다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제 2. 단일 출발 최단 경로문제 - 그래프 내의 특정 노드 u에서 출발해서, 그래프 내 모든 노드 각각에 도착하는 가장 짧은 경로를 찾는 문제 3. 전체 쌍 최단 경로 : 그래프 내의 모든 쌍에 대한 최단 경로를 찾는 문제 2. 최단 경로 알고리즘 - 다익스트라 알고리즘 다익스트라 알고리즘은 위의 최단 경로 문제 종류 중, 2번에 해당한다. 하나의 .. 2023. 2. 16.
11. 알고리즘 탐욕 알고리즘 (그리디 greedy) 1. 탐욕 알고리즘이란? Greedy algorithm 또는 알고리즘이라고 불린다 최적의 해에 가까운 값을 구하기 위해 사용된다 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제 1 동전문제 지불해야하는 값이 4720원 일 때 1원 50원 100원 500원 동전으로 동전의 수가 가장 적게 지불하시오. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현이 가능하다 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 된다 coin_list=[500,100,50,1] def min_coin_count(value, coin_list) : total_coin_count=0 details.. 2023. 2. 3.
10. 알고리즘 너비 우선 탐색, 깊이 우선 탐색 탐색 : 그래프를 탐색하는 알고리즘 그래프를 탐색한다 : 노드를 탐색하는 기법 1. BFS와 DFS란? 대표적인 그래프 탐색 알고리즘 너비 우선 탐색 : 정점들과 같은 레벨에 있는 노드(형제)들을 먼저 탐색하는 방식. 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회한다. 깊이 우선 탐색 : 정점의 자식들을 먼저 탐색하는 방식. 한 노드의 자식을 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회한다. 2. 파이썬으로 BFS와 DFS 그래프를 표현하는 방법 딕셔너리와 리스트 자료구조를 활용해서 그래프를 표현할 수 있다. 각 노드를 key로, 각 노드에 인접한 노드들의 리스트를 value로 가지는 딕셔너리를 만들면 된다. graph = dict() graph['.. 2023. 2. 3.
9. 알고리즘 그래프(Graph)와 자료구조 1. 그래프(Graph)란? IT에서 그래프는 실제 세계의 현상이나 사물을 정점(vertex) 또는 노드(Node)와 간선(Edge)으로 표현하기 위해 사용한다. 집에서 회사로 가는 경로 집-버스-회사 집-지하철-회사 집, 버스, 지하철, 회사는 정점(노드)이고, -는 간선이다. 2. 그래프(Graph)관련 용어 노드(Node) : 위치를 말한다. 정점(vertex)라고도 한다. 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 된다. (link 또는 branch라고도 한다) 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) 참고용어 정점의 차수(Dgree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입차수(In-Degree) .. 2023. 1. 26.
8. 알고리즘 이진탐색(Binary Search)과 순차탐색 1. 이진탐색(Binary Search)란? 탐색할 자료를 둘로 나누어 해당 데이터가 있을 만한 곳을 탐색하는 방법 문제 : 1-30번째 병뚜껑에 각각 1~100 사이의 번호가 표시되어 있다. 이중에 70이 있을지 없을지 확인하는 방법은? 조건 1) 가장 적게 병을 따야 한다. 2) 각 병뚜껑에 쓰여진 번호는 낮은 번호 순으로 기입되어 있다. 방법 : 가운데 있는 병뚜껑을 순차적으로 따서 범위를 좁힌다. 이것이 이진탐색방법이다. 순차탐색 : index 0 부터 하나씩 찾기 때문에 훨씬 느리다. 2. 분할정복알고리즘과 이진탐색 분할정복 알고리즘 Divide : 문제를 하나 또는 둘 이상으로 나눈다. Conquer : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. 이진.. 2023. 1. 26.
7. 알고리즘 정렬 병합정렬(merge sort) 1. 병합정렬 (merge sort) 분할정복 알고리즘을 사용한다. 재귀용법을 활용한 정렬 알고리즘이다 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 병합정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다. 2. 알고리즘 이해 알고리즘 내부에서는 먼저 모두 데이터길이가1일 때 까지 나눈 후, 비교 및 병합을 반복한다. 데이터가 네개일 때 예 : data_list=[1,9,3,2] 먼저 [1,9],[3,2]로 나눈다 다시 앞부분을 [1],[9]로 나눈다 다시 정렬해서 합친다 [1,9] 다음 [3,2]은 [3],[2]로 나눈다 다시 정렬해서 합친다 [2,3] 이제[1,9],[3,2]를 합친다. 12이니[1,2]다 9>3이니[1,2,3.. 2023. 1. 26.

티스토리툴바