본문 바로가기

전체 글82

[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.
[WEEK02] 완전탐색 1) Brute Force : for 문이나 if 문을 활용하여 모든 경우의 수 알아봄 2) 비트마스크 (Bitmask) : 각 원소가 A인지 B인지 두가지 상태만을 가질 때 0, 1로 구분하여 배열을 저장 3) 재귀함수 4) 순열 5) BFS, DFS 6) 백트래킹 : 현재 상태에서 가능한 모든 선택지를 다 따라 들어가며 탐색하는 알고리즘 : 원하는 값과 불일치하는 부분이 생기면 탐색을 진행하지 않고 전단계로 돌아감 ex) 오목에서 앞으로 진행될 수를 생각해보고 가장 적절한 자리에 두는 것 대표문제 : N과 M cf) DFS(Depth First Search)와 백트래킹의 차이점 : 백트래킹은 불필요한 탐색을 하지 않음 : DFS는 모든 경우의 수를 탐색함 2022. 10. 3.

티스토리툴바