my devlog;

슬라이딩 윈도우 알고리즘이란? 고정된 사이즈의 윈도우를 이동시키면서 윈도우 내의 데이터를 이용해 문제를 푸는 알고리즘. 특정 범위 내의 값들을 비교할 때 사용할 수 있다. 유사한 알고리즘으로는 투 포인터가 있는데, 투 포인터는 대개 정렬된 배열에 이용되며 부분 범위의 사이즈가 고정되어 있지 않다는 점에서 슬라이딩 윈도우와 다르다. 글로만 봐서는 쉽게 이해하기 힘들 수 있기에 (나같은 경우에는 슬라이딩 윈도우 구현 코드를 보고도 한 번에 이해하기가 힘들었다.) 수월한 이해를 돕기 위해 구체적인 예시 문제를 가져와서 설명해보겠다. 예제: Leetcode 3. Longest Substring Without Repeating Characters 이 문제는 제목에서도 알 수 있듯이, string이 주어지면, 중복..

플로이드의 순환 찾기 알고리즘은 포인터 두 개를 이용해 트리 내에 존재하는 사이클을 빠르게 찾을 수 있는 알고리즘이다. 개념 1. slow와 fast라는 이름을 가진 포인터 두 개를 사용해 각각 한 칸, 두 칸씩 이동시킨다. 2. 둘 중 어느 것도 null값에 도달하기 전까지 반복해서 이동시키면서 두 포인터가 만나는 지점이 있는지 매번 확인한다. 이때 만약 사이클이 없다면, 각자 다른 간격으로 이동하는 두 포인터는 만나지 않고 리스트의 끝에 도달한다. 그러나 만약 사이클이 있다면, 리스트의 끝에 도달할 수 없기 때문에 반복해서 돌다가 특정 지점에서 만나게 된다. 구현 코드 //관련 문제: https://leetcode.com/problems/linked-list-cycle/ /** * Definition..

탐색 : 여러 개의 자료 중에서 원하는 자료를 찾는 작업. 탐색 키로 항목을 서로 구별. 배열, 연결 리스트, 트리, 그래프, 해시 테이블 등을 사용 ① 순차 탐색 ▷ 아이디어 : 처음부터 마지막까지 하나씩 순차적으로 확인 ▷ 프로그램 int sequential_search(int key, int low, int high){ for(int i = low; i high) return -1; int middle = (low+high)/2; if (key == list[middle]) return middle; else if (key < list[middle]) return search_binary(key, low, middle-1); else return search_binary(key, middle+1, ..

참고 : 선택 정렬, 삽입 정렬, 버블 정렬https://hyunah-home.tistory.com/entry/%EA%B8%B0%EB%B3%B8-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%84%A0%ED%83%9D%EC%A0%95%EB%A0%AC-%EC%82%BD%EC%9E%85%EC%A0%95%EB%A0%AC-%EB%B2%84%EB%B8%94%EC%A0%95%EB%A0%AC 기본 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬 정렬 : 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것. 단순하지만 비효율적인 방법의 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬 ① 선택 정렬 ▷ 아이디어 : 정렬된 리스트와 hyunah-home.t..

정렬 : 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것. 단순하지만 비효율적인 방법의 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬 ① 선택 정렬 ▷ 아이디어 : 정렬된 리스트와 정렬 안 된 리스트를 가정함. 정렬 안 된 리스트에서 최소값이나 최대값을 선택해 한쪽으로 몰아넣음. ▷ 알고리즘 ; 오름차순 정렬 기준 1. 오른쪽 리스트에서 최소값의 인덱스 선택 2. 오른쪽 리스트의 첫번째 수의 값과 최소값을 교환 3. 왼쪽 리스트 크기 1 증가, 오른쪽 리스트 크기 1 감소 4. 오른쪽 리스트가 소진될 때까지 1~3 과정 반복 ▷ 프로그램 void selection_sort(int list[], int n){ int least, temp; for (int i = 0; i < n-1; i++) {..

DAG(Directed Acyclic Graph) : 사이클이 없는 방향 그래프. DAG에서 에지 가 있다면 정점 u는 정점 v를 선행함. 위상 정렬(topological sort) : 방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 순서대로 나열하는 것. 선행관계가 없는 것은 뭐가 먼저 나오든지 상관이 없기 때문에 위상 정렬 결과는 여러 가지가 존재할 수 있음. ▷ 알고리즘 1. 진입차수가 0인 임의의 정점(선행자가 없는 정점)을 큐(혹은 스택)에 삽입 2. 정점 개수만큼 시행하는 반복문 생성 3. 반복문 내부에서는, 큐에서 정점을 하나씩 꺼내어 출력하고 출력한 정점에 붙어있는 에지들을 제거하여 진입차수 재계산 4. 진입차수를 재계산하여 진입차수가 0이 된 것은 큐에 삽입 위상정렬이 불..

최단 경로 : 그래프에서 정점 u로부터 정점 v로 가는 경로 중에서 에지들의 가중치 합이 최소가 되는 경로. 혹은 에지의 개수가 가장 적은 경로. 다익스트라 알고리즘 (Dijkstra Algorithm) : 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾을 수 있는 알고리즘. ▷ 아이디어 : 방문하지 않은 정점 중에서 가장 비용이 적은 에지로 연결된 정점을 방문. 시작 정점으로부터 해당 정점을 경유지로 하여 다른 정점을 방문하는 비용이 더 작다면, 최단 경로값을 갱신. 위의 그림에서 distance[u]가 distance[w]값보다 작아서 가장 비용이 적은 에지로 연결된 정점 u가 새롭게 추가되었다면(방문되었다면), 시작 정점 v로부터 해당 정점 u를 거쳐서 다른 정점인 w로 가는 비용을 계산한다..

스패닝 트리 (Spanning Tree) -> 연결 그래프 G의 스패닝(신장) 트리란, G의 모든 정점을 포함하는 부분 그래프로서의 트리. 모든 정점들이 연결되어 있어야 하며 사이클이 존재해서는 안 됨. n개의 정점을 갖는 스패닝 트리는 반드시 n-1개의 에지를 가짐. 최소 스패닝 트리(최소 신장 트리) -> 가중치 그래프의 스패닝 트리들 중에서 에지들의 가중치 합이 최소인 스패닝 트리. ▷ Prim의 MST 알고리즘 ○ 아이디어 : 스패닝 트리 집합의 인접 정점 중 최소 가중치로 연결된 정점을 추가하며 스패닝 트리 집합을 점진적으로 확장해 나가자! ○ 알고리즘 1. 임의의 시작 정점에서 출발. (대개 인덱스가 가장 작은 정점) 시작 정점을 스패닝 트리 집합(MST)에 추가. 2. MST에 인접한 정점 ..

▷ 개념 ○ 강한 연결 방향그래프(Strongly Connected Digraph) -> 어떤 두 정점을 잡든 간에 서로 연결이 되어 있는, 방향 경로가 존재하는 그래프. ○ 강한 연결 요소(Strongly Connected Component) -> 어떤 두 정점을 잡든 서로 도달할 수 있는 경로가 있는 부분 방향 그래프. 같은 강한 연결 요소에 속하는 정점들은 서로 이동할 수 있는 방향 경로가 반드시 존재함. 사이클이 발생한다면 무조건 SCC에 해당하며 강한 연결 방향 그래프는 강한 연결 요소가 오직 하나. SCC를 하나의 정점으로 고려하여 각 SCC를 위상 정렬할 수 있음. ▷ 알고리즘 ○ 타잔 알고리즘(Tarjan's Algorithm) · 개념 : 모든 정점에 대해 DFS를 수행하여 SCC를 찾는..

그래프 탐색 : 그래프의 기본 연산 중 하나. 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문. 특정 정점에서 특정 정점까지 갈 수 있는지 없는지를 탐색 1. 깊이우선 탐색(DFS) ○ 개념 : 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 방향으로 다시 탐색을 진행. 갈림길로 다시 돌아가는 과정에서는 스택을 사용하거나 재귀 함수 호출을 이용. ○ 알고리즘 : 정점 v를 방문한 후 해당 정점이 방문되었다고 표시하고 v의 모든 인접 정점에 대해 방문되지 않은 정점이라면 재귀 함수 호출. ○ 프로그램 int visited[8]; vector adj_list[8]; //adj_list[i]에는 i의 인접 정점들의 리스..