Devlog

이분탐색 알고리즘 공부를 어느정도 해봤다면 누구에게나 친숙한 알고리즘 입니다. 정렬된 배열에서 특정 값의 위치(인덱스 값)을 찾는 알고리즘이지요. 이분탐색을 구현하는 코드는 아래와 같습니다. 해당 값이 존재하면 그 값에 대한 인덱스 값을 출력하고, 없으면 -1을 출력합니다. int process_binary_search(vector& arr, int e) { int n = (int)arr.size(); int left = 0, right = n-1, mid; while(left > 1; if(arr[mid] == e) return mid; else if(arr[mid] > e) right = mid - 1; else left = mid + 1; } return -1; } 이분탐색의 알고리즘은 선택된 값(..

강한 연결 요소 (Strongly Connected Component) 시리즈 1. 코사라주 알고리즘 2. 타잔 알고리즘 3. 2-SAT 소개 지난 챕터 에서는 코사라주 알고리즘의 소개와 증명에 대해서 설명했습니다. 코사라주 알고리즘은 정방향/역방향 이렇게 DFS를 두번 돌려서 SCC를 구하는 방식으로, 구현은 간단하지만 DFS를 두번 돌려야 하고, 그렇기에 코드가 약간 긴 편입니다. 그러나 타잔 알고리즘은 DFS를 단 한번 실행함으로써 모든 존재하는 SCC를 구하게 됩니다. 비록 이해 난이도는 코사라주보다 조금 어렵지만, 코드량이 적은 편이라 응용 문제에서도 쉽게 활용할 수 있는 알고리즘 입니다. 코드는 아래 블로그를 참고해서 파이썬으로 옮겨적었습니다. 코사라주 때는 그냥 알고리즘만 보고 바로 코딩했는..

강한 연결 요소 (Strongly Connected Component) 시리즈 1. 코사라주 알고리즘 2. 타잔 알고리즘 3. 2-SAT 소개 강한 연결 요소(Strongly Connectioned Component)는 그렇게 잘 알려져 있는 알고리즘이 아니지만 제법 유용하게 쓰일 수 있는 알고리즘 입니다. 그래프에서 정점들 중 일부분이 서로 도달할 수 있는 정점들의 집합을 강하계 연결되었다. 라고 합니다. 강한 연결 요소 알고리즘이란 강하게 연결되어 있는 정점들의 집합의 정보를 구하는 알고리즘 입니다. 크게 코사라주 알고리즘과 타잔 알고리즘이 있습니다. 코사라주 알고리즘이 구현 난이도가 쉽기 때문에 이번 챕터에서는 코사라주 알고리즘 부터 설명합니다. 알고리즘 작동 방식 코사라주 알고리즘의 그래프이 간선..

개요 위상 정렬은 DAG에서 정점의 순서를 정하는 데 사용하는 알고리즘입니다. 이는 대학교 선수 과목으로 쉽게 비유를 할 수 있습니다. 일부 과목들은 앞의 몇 개의 선수과목을 이수해야 들을 수 있는 경우가 있는데, 이런 경우까지 전부 체크해서 1학년 부터 4학년 까지 들어야 하는 과목의 순서를 나열할 때, 이 알고리즘을 사용하면 해결이 가능합니다. 원리 위상 정렬의 원리는 부모 정점과 이어저 있는 간선의 갯수(차수)를 파악하는 것입니다. 어떤 정점에서 몇 개의 차수가 있다는 것은 해당 정점을 탐색하기 전에 몇 개의 다른 정점을 탐색해야 해당 정점을 탐색할 수 있다는 의미가 됩니다. 즉 만약에 어떤 정점을 탐색을 완료했다면, 해당 정점의 탐색을 완료했기 때문의 해당 정점과 연결되어 있는 다음 정점들은 해당..