본문 바로가기

Review57

[WEEK03] 최단경로 - 다익스트라 / 플로이드워셜 1. 다익스트라(Dijkstra) - 그래프에서 여러개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘 - '음의 간선'이 없을 때 정상적으로 작동 - 현실세계의 길에서는 음의 간선이 표현되지 않으므로 다익스트라 알고리즘은 실제 GPS 소프트웨어의 기본알고리즘으로 채택됨 구현과정 1. 출발 노드를 설정 2. 최단거리 테이블을 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신 5. 위의 과정에서 3번과 4번을 반복 - '각 노드에 대한 현재까지의 최단거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신 - 매번 현재 처리하고 있는 노드를 기준으.. 2022. 10. 11.
[WEEK03] BFS & DFS (+전위/중위/후위순회) 순서트리의 노드를 스캔하는 방법은 크게 두가지로 BFS와 DFS가 있음 1. BFS Breadth-First-Search - 가로검색, 수평검색 - 한 레벨 다음에 다음 레벨로 넘어가는 순서 - 가까운 노드부터 탐색하는 알고리즘 - 큐를 이용 / 구현은 큐 자료구조를 이용 동작방식 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 3. 2번의 과정을 더이상 수행하지 못할 때까지 반복 시간복잡도 - 탐색을 수행함에 있어 O(N)의 시간이 소요됨 - 실제 수행시간의 경우 DFS보다 좋음 - DFS는 재귀적으로 들어가기 때문에 실제 프로그램 수행시간은 느려질 수 있음 소스코드 # 출처 : 이코테 from c.. 2022. 10. 11.
[WEEK03] 신장트리와 최소신장트리 (크루스칼 + 프림 알고리즘) 1. 신장트리 Spanning Tree - 신장트리는 그래프 알고리즘 문제로 자주 출제되는 문제유형 - 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 - 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립조건이기도 함 최소신장트리 알고리즘 (MST; Minimum Spanning Tree) - 신장트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘 2. 크루스칼 알고리즘 특징 - 대표적인 최소신장트리 알고리즘 중의 하나 - 그리디 알고리즘으로 분류 - 모든 간선에 대해 정렬을 수행한 뒤에 가장 짧은 간선부터 집합에 포함시킴 (이때 사이클을 발생시킬 수 있는 간선의 경우 집합에 포함시키지 않음 => 최적의 해 보장) .. 2022. 10. 10.
[WEEK03] 그래프와 트리 (+인접행렬 / 인접리스트 / 이진트리) 1. 그래프 특징 - 노드와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조 - '서로 다른 개체 혹은 객체가 연결되어 있음' 혹은 '여러 개의 도시가 연결되어 있음' 내용이 나오면 그래프 알고리즘을 일단 생각 용어의 정리 1) 정점 (Vertex / Node) : 각각의 노드를 의미 2) 간선 (Edge / Link) : 그래프에서 각 정점들을 연결하는 선 : 화살표 표시 혹은 그냥 직선 3) 가중치 (Weight) : 간선 위에 표시된 숫자 : 비용을 표현하는 것 등에 쓰임 4) Directed Graph / Undirected Graph : 방향성 혹은 무방향성 그래프 5) Adjacency : 방향성 있는 그래프에서 간선으로 연결된 인접 정점 6) Degree out-degree.. 2022. 10. 10.
[WEEK03] 힙 / 우선순위 큐 1. 힙이란? 특징 - 힙은 일종의 반정렬 상태 (느슨한 정렬상태)를 유지함 - 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도 (혹은 반대) - 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리 장점 - 시간복잡도가 좋은편 - 힙 정렬이 가장 유용한 경우는 전체를 정렬하기보다 가장 큰 값 몇개만 필요할 때임 시간복잡도 - 힙 트리의 전체 높이 = log(n) / 하나의 요소 개수가 N개 - 따라서 T(n) = O(nlogn) 2. 우선순위 큐? 특징 - 우선순위의 개념을 큐에 도입한 자료구조 - 데이터들이 우선순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나감 - 우선순위 큐는 배열, 연결리스트, 힙으로 모두 가능하나 힙으로 구현하는 것이 가장 효율적임 - 여러 개.. 2022. 10. 10.
[WEEK02] 정렬 알고리즘 [Do it 자료구조와 함께 배우는 알고리즘 입문 with 파이썬] + [이것이 취업을 위한 코딩테스트다] 개념정리 정렬? : 항목의 값을 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말함 : 오름차순 정렬 혹은 내림차순 정렬 : 안정적인 알고리즘 / 그렇지 않은 알고리즘으로 나눌 수 있음 : 교환 / 선택 / 삽입이 핵심 1. 단순 정렬 알고리즘 1) 버블 정렬 (Bubble Sort) : 원소의 수가 n인 배열에서 n-1번 비교, 교환 하면 가장 작은 원소인 1이 맨 앞으로 이동함 (패스) : 이러한 일련의 과정을 지속적으로 거쳐 정렬 : 알고리즘 개선방법 (Do it 참고) : 시간복잡도 = O(n^2) 2) 셰이커 정렬 (Shaker Sort) : 버블정렬을 개선한 알고리.. 2022. 10. 3.

티스토리툴바