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

2023.05.09 - [PS] - [스프라그 그런디 정리] - BOJ_11868 : 님 게임 2 어제 푼 님 게임2에이어서 님 게임3. 님 게임 2에서는 단순히 xor로 그런디 수를 파악하여 게임의 승패만을 예측하는 것이었다면, 이 문제에서는 승리할 수 있는 경우의 수를 세는 것이 목적이다. 간단한 아이디어로 생각을 해보자. xor를 하였을때, 1이 남는 비트들이 존재할 것이다. 첫번째 예시로 생각을 해보면, $15=1111_2$ $11=1011_2$ $8 = 1000_2$ 이고, 이를 xor하면 $1100_2$ 가 된다. 이때, 1인 비트중 최상위 비트는 $2^3$ 비트에 위치한 1이다. 이 때, 님게임 2에서 증명했듯이 현재 xor을 한 후 1인 최상위 비트를 가진 그런디 수들은, 값이 변경되었을 ..

저번 포스팅에 이어, 이번에도 게임 이론에 대해 공부해보겠다. 2023.05.09 - [PS] - [게임 이론] - BOJ_11062 : 카드 게임 이번에는 boj 11868번을 풀면서 스프라그 그런디 정리에 대해 배워보자. 문제의 아이디어 자체는 길지 않다. 여러개의 돌 무더기가 있고, 두 사람은 돌 무더기중 하나를 선택해, 그 돌무더기에서 하나 이상의 돌을 제거할 수 있다. 그리고 전체 돌 더미에서 마지막 돌을 가져가는 사람이 승리하는 것이 게임 조건이다. 이 문제 역시 게임 이론을 근거로 하기에, 두 사람 모두 최적의 플레이를 한다고 가정한다. 즉, 승자가 정해져 있는것이다. 이 문제에서는 스프라그 그런디 정리라는 알고리즘을 알고 있어야한다. 💡스프라그-그런디 정리란? 게임판의 상태를 각각 하나의 ..

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