15일차 강의 (31 ~ 33강) (완강)
트라이 (31강) 문자열을 효율적으로 처리하기 위한 트리 자료구조 + 단어 S를 삽입/탐색/삭제할 때 O(|S|) - 문자열을 그냥 배열에 저장하는 것 보다 최대 '4*글자의 종류'배 만큼 더 사용 (예를 들어 각 단어가 알파벳 대문자로만 구성되어 있을 경우 104배) 이론적인 시간복잡도와는 별개로 실제로는 트라이가 해시, 이진 검색 트리에 비해 훨씬 느림. 일반적인 상황에서는 해시나 이진 검색 트리를 사용하는게 좋으나 트라이의 성질을 사용해야 하는 문제가 여럿 존재 대표적인 활용 사례 : 자동완성기능 (접두사, 접미사 관련) 부록A - 문자열 기초 (32강) 문자열을 가지고 복잡한 연산을 해야한다면 그냥 파이썬을 쓰자 C++에는 split과 같이 구분자를 기준으로 문자열을 나눠주는 함수가 없음 주의사항..
14일차 강의 (30강)
30강 (KMP) 드물게 나옴 S[a:b] = "S[a]S[a+1]...S[b-1]" lSl는 S의 길이 접두사 = 문자열의 첫 문자를 포함하는 연속한 문자열 접미사 = 문자열의 끝 문자를 포함하는 연속한 문자열 패턴 매칭 문제 실패함수 KMP : 패턴 매칭 문제를 O(|A| + |B|)에 해결할 수 있는 기적의 알고리즘 굉장히 헷갈림 먼저 KMP에서 쓰이는 실패 함수를 알면 KMP를 이해하는데 도움이 됨 실패함수 F(x) : 문자열 S[0:x+1]에서 접두사와 접미사가 일치하는 최대 길이 KMP
13일차 강의 (28 ~ 29강)
플로이드 (28강) 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘 시간복잡도 O(V^3) 음수의 가중치를 가져도 상관은 없지만, 음수의 사이클을 가지면 사용 불가 대입이 빈번하게 발생할 경우 min(a,b) 사용보다 if문으로 직접 비교를 통해 필요한 경우에만 대입이 일어나도록 하는 것이 시간복잡도 측면에서 더 효율적임. (DP, 플로이드 등) 경로복원 → nxt테이블 이용 (최단 거리 갱신이 일어날 때 갱신) nxt테이블을 이용해 한 단계씩 앞으로 전진하면서 경로를 복원할 수 있음 다익스트라 (29강) 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 음수인 가중치를 가지면 사용할 수 없음 (→ 벨만포드 알고리즘 이용) 우선순위 큐를 이용한 구현 시 시간복잡도 O(ElogE) ..
DSU(Disjoint Set Union)(= 유니온 파인드 (Union-Find))
DSU Disjoint Set (서로소 집합)이란 서로 공통된 원소가 없는 집합을 말한다. = 유니온 파인드 (합집합 찾기) 공통 원소가 없는, 즉 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구 2가지 union, find 연산을 지원한다. 1. union은 2개의 set을 하나의 set으로 합쳐주는 것 2. find는 어떤 element가 주어질 때, 이 element가 속해져 있는 대표 원소를 반환 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 Union : 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합침 (root를 찾아서, 높이가 작은 쪽을 큰 쪽으로 합침) → 유니온 바이 랭크 (..
12일차 강의 (27강)
최소 신장 트리(MST) (27강) 부분그래프 → 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 그래프를 의미 신장트리 → 주어진 방향성이 없는 그래프의 부분 그래프들 에서 모든 정점을 포함하는 트리를 의미 최소신장트리 → 신장 트리중에서 간선의 합이 최소인 트리를 의미 크루스칼 알고리즘 (유니온 파인드 알고리즘 이용) 1. 간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택 2. 현재 선택한 간선이 정점 u, v를 연결하는 간선이라고 할 때 만약 u와 v가 같은 그룹이라면 아무 것도 하지 않고 넘어감, u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가 3. 최소 신장 트리에 V-1개의 간선을 추가시켰다면 과정을 종료, 그렇지 않다면 ..
11일차 강의 (24 ~ 26강)
24강 (그래프) 그래프 = 정점과 간선으로 이루어진 자료구조 단순 그래프 : 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프 표현법 1 - 인접 행렬 방향그래프 int adj_matrix[10][10] = {}; int v, e; cin >> v >> e; for (int i = 0; i > u >> v; adj_matrix[u][v] = 1; } 무방향그래프 int adj_matrix[10][10] = {}; int v, e; cin >> v >> e; for (int i = 0; i > u >> v; adj_matrix[u][v] = 1; adj_matrix[v][u] = 1; } 표현..
어느덧 방학이 4주도 안남았다. 이번 방학은 계획처럼 안된 것들이 많아서 생각이 복잡해졌다. 이미 지나간 일은 어쩔수 없으니 남은 4주라도 제대로 활용해보고자 한다. 우선 알고리즘 복습차원에서 듣고있는 강의는 5일이면 마무리 될 것 같다. (~2/11 or 2/12) 따로 해볼만한 것들을 생각해보았는데, 1. 프론트엔드 찍먹 2. 백엔드 복습 크게 이 두가지인 것 같다. 백엔드 복습은 한학기동안 공부했던 백엔드 내용을 전체적으로 돌아볼 생각이다. 그리고 시간상 자세히 알아보지 못했던 내용을 추가하여 블로그에 정리해볼 것이다. 사실 백엔드가 더 잘 맞을 것이라는 생각에 백엔드를 먼저 배워보긴 했지만, 백엔드를 배우다보니 프론트엔드에 대한 흥미도 생겼다. 어쩌면 내가 프론트엔드가 더 잘 맞을 수도 있을 것 ..