다익스트라 알고리즘이란? 다익스트라 알고리즘은 DP를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 인공위성, GPS 등 현실 세계에서 굉장히 많이 사용되며, 다음과 같은 특징들이 있다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 음의 간선을 포함할 수 없다 (이 경우 벨만 포드 알고리즘 사용) $O(NlogN)$의 시간 복잡도를 가진다. 동작 단계 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 현재 위치한 노드의 인접 노드 중 아직 방문하지 않았고, 거리가 가장 짧은 노드를 선택한다. 4. 선택된 노드를 방문처리한다. 5. 해당 노드를 거쳐 다른 노드로 넘어가는 간선의 가중치를 통해 최단 거리 테이블을 업데이트한다. 6. 3~5 과정을 반복한다. 최..

소수를 판별하는 알고리즘 중에는 굉장히 유명한 에라토스테네스의 체라는 알고리즘이 존재한다. 소수 판별 문제는 대부분 이 알고리즘으로 풀기 때문에 잘 익혀두면 큰 도움이 된다. 오늘 풀어볼 문제인 boj 1929 번 문제다. 💡에라토스테네스의 체란? 배열을 원하는 범위만큼 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. 이때, 자기 자신은 지우지 않고, 이미 지워진 수인 경우 건너뛴다. 지워지지 않은 테이블이 소수로 판별된 테이블이다. 위 예시는 2의 배수를 모두 지우고, 3의 배수를 지우는 과정이다. 이런 식으로 $N/2$까지 진행하고 남은 테이블을 확인한다. ❓에라토스테네스의 체의 시간복잡도 naive한 방법으로는, 일반적으로 어떤 정수의 소수를 판별할때는 2부터 판..

2023.05.15 - [PS] - [강한 연결 요소 SCC] - BOJ_2150 : Strongly Connected Component [강한 연결 요소 SCC] - BOJ_2150 : Strongly Connected Component 오늘은 SCC 알고리즘에 대해 공부하였다. 강한 연결요소인 SCC를 구하는 문제였다. 2-sat을 풀기전 사전 준비로 풀었는데, 어려웠다.. 💡SCC 알고리즘이란? scc란 쉽게 말하면 전체 노드 집합 속에서, kangmanjoo.tistory.com 저번 SCC 공부는 사실 이번 2-SAT 풀이를 위해서 진행했었다. 2-SAT 풀이를 보기전, SCC에 대한 기본 지식이 없다면 위 글을 먼저 읽어볼 것. 오늘 풀어볼 문제인, 백준 11280번이다. 일단 2-SAT에 대..

오늘은 SCC 알고리즘에 대해 공부하였다. 강한 연결요소인 SCC를 구하는 문제였다. 2-sat을 풀기전 사전 준비로 풀었는데, 어려웠다.. 💡SCC 알고리즘이란? scc란 쉽게 말하면 전체 노드 집합 속에서, 서로 사이클을 이루는 노드들의 집합이다. 이런 형태의 노드 집합이 있으면 전체 집합을 이렇게 3개의 scc집합 (사이클) 로 나누는 것이다. scc를 구할때는 코사라주 알고리즘과 타잔 알고리즘 두가지 종류가 있는데, 타잔알고리즘이 구현이 어려운 대신 범용성이 넓기에 타잔 알고리즘을 사용해 풀었다. 🐒타잔 알고리즘이란? 타잔 알고리즘이란 SCC를 구하는 기법중 하나로, DFS 탐색을 들어갈 때 나의 부모노드를 기록하면서 가는 것이다. 스택에 방문한 노드들을 넣으면서 DFS를 돌다가 나 자신이 부모노..

티스토리로 블로그를 이전한 뒤, 기념비적인 첫 글이다. 요즈음도 알고리즘을 공부하다보면, 금새 잊곤 하기 때문에 이렇게 하나 하나 글을 써보려 한다. 오늘 공부한 알고리즘은, 바로 "게임 이론" 알고리즘 분류만 보면 상당히 귀엽고 재밌어 보이지만, 상당히 악랄하다. 우선 오늘의 문제를 소개해보겠다. 처음 문제를 보았을 때는, 상당히 간단해 보인다. 그냥 항상 최선의 경우를 고르면 되는거 아님? 아니다 바로 다음과 같은 상황이 야기될 수 있다. 전체 게임 결과를 보았을 때, 최선의 선택을 해야하고, 상대 또한 최선의 선택을 하기에 내가 처음에 2를 뽑으면, 상대에게 5를 내주기 때문에 점수가 더 낮아지게 된다. 따라서 이 경우에서의 "최선의 수"란 다음과 같다. 물론 우리가 보기에는 , 그렇게 어렵지 않다..