PS/Algorithm

어떤 그래프에서 정점을 제거했을 때, 그래프가 분리되어버리는 경우가 있습니다. 또는 간선을 제거 했을 때 분리되는 경우도 있습니다. 각각의 정점과 간선을 "단절점", "단절선"이라고 합니다. 1. 단절점의 특징단절점과 단절선이 갖는 중요한 특징이 있습니다. 하나의 연결그래프를 dfs로 탐색하면 탐색 경로가 트리의 형태로 남게 됩니다. 여기서 어떤 정점 n을 탐색했을 때 그 정점으로부터 탐색된 하위 정점들에서 n의 상위 정점으로 돌아가는 경로가 하나도 없다면 n은 단절점이 됩니다. 그러니까, n을 제거하면 그보다 하위에 있는 모든 정점들은 n보다 상위 정점에서 분리되어버립니다. 돌아가는 길이 없으니까요. 이거 뭔가 지난 번에 정리한 SCC와 비슷한 느낌인데, 단절점을 찾는 과정이 SCC의 일부이기 때문입니..

어떤 자연수 n이 소수인지 판별하는 좋은 방법이 여러 가지 있습니다. 우선 가장 근본인 2부터 n - 1까지의 수로 n을 나누어보는 방법이 있습니다. 약수가 1과 n 말고 또 있는지 확실히 알 수 있습니다. 그런데 n이 만약 1,000,000,007 같은 수라면, 혹은 2136279841-1처럼 답도 없이 큰 소수에 대해서는 실행 가능성이 좀 낮거나 아예 없습니다. 그리고 구현하기 쉽고 성능도 확실한 "에라토스테네스의 체"가 있습니다. 근데 이건 특정한 소수 하나를 판별하기 보다 N까지의 소수를 모두 구하는데 좋은 방법입니다. n까지의 모든 소수를 빠짐 없이 확실하게 구할 수 있는 결정론적인 성질이 있습니다. 하지만 역시 자릿수가 좀 커진다 싶으면 매우 느려지는 단점이 있습니다. 가장 최적화된 에라토스테..

1. 충족가능성 문제(Boolean satisfiability problem, SAT)여러 변수로 논리 값들이 주어졌을 때, 그 논리 값들로 이루어진 식이 참이 되는 논리 값의 상태가 존재하는가에 대한 문제입니다. 이거 약간 뭐랑 비슷하냐면 대학교 시간표 짜는 거랑 비슷합니다. 작년 연구부장 역임했던 바로 생각해보면 전담 시간표 짜는게 딱 이 SAT 문제 입니다. 제가 일반 종합대학을 다녀본 경험이 없으니 그냥 교육대학교에서 만났던 과목으로 생각해봅시다. (제가 다녔던 대학교는 사실 수강신청이랄 것도 없긴 했습니다. 그냥 예시 만들기 어려우니까 그런갑다 해봅시다.) 개설되는 다음 4개의 과목을 조건에 맞게 수강할 수 있는 방법이 있을까요?교육심리(A)와 교육철학(B) 중 한 과목은 반드시 수강해야 한다...

1. 강한 연결 요소강한 연결 요소는 그래프에 존재하는 서브 그래프입니다. 각각의 SCC는 하나의 사이클을 이룹니다. 그러므로 하나의 SCC내의 정점 u와 정점 v를 어떤 방법으로 선택해도 u에서 v로 이동하는 경로가 반드시 존재합니다. 그리고 각각의 SCC는 최대한 크게 구성되어야 합니다. 그러니까 하나의 그래프에 여러 SCC가 있을 때 서로 다른 SCC에 포함되는 두 정점간에는 단방향 경로가 존재할 수 있어도 사이클이 존재하는 경우가 하나도 없어야 합니다.이 그림의 유향그래프에서 여러 사이클을 찾아볼 수 있습니다. {a, d, b}와 {c, f}등이 있습니다. 하지만 이 중 SCC는 없습니다. {a, d, b} 사이클에서 d - b 사이에 e - f를 추가할 수 있습니다. {a, d, e, f, b}..

1. 문자열의 효율적인 탐색 방법문자열 탐색의 가장 직관적인 방법은 직접 비교해보는 것이다. 한 글자씩 대조해보고 아니면 패스 하는 식. 그러나 이 탐색 방법은 한 가지 하자가 있는데 바로... 일대다 매칭(여러 후보 중에 특정 값과 매칭이 되는 값 찾기)에서는 답 없는 탐색 속도를 갖고 있다는 것. 문자열의 집합 S가 있다. 이 안에 어떤 문자열 T가 존재하는지 확인하고 싶다. S가 반 친구들 이름 정도의 규모라면 금방 확인 가능하겠지만 브리태니커 백과사전이라면? 하루 종일 찾아도 못찾을 수 있다. 문자열의 집합 S를 하나로 합쳐버릴 방법이 있다면 어떨까? S 안에 있는 무수한 문자들을 하나하나 대조하는 것이 아니라 하나로 합쳐진 S를 한번 훑어보는 것 만으로 T가 포함되는지 아닌지 확인 가능하다면? ..

1. 오토마타 이론문제를 해결하는 과정 중 한 시점을 "상태(state)"라고 하면 유한한 상태로 해결할 수 있는 문제들과 그렇지 않은 문제로 나눌 수 있다. 이 때 유한한 상태를 갖고 입력에 따라 한 상태에서 다른 상태로 전이되며 최초 상태(S0)에서 최종 상태(F)까지 이어져 출력을 내놓는 것을 유한 상태 기계(FSM, Finite-State Machine), 유한 오토마타(Automata)라고 부른다. 좀 더 쉽게 이해해보면 우리가 풀고 있는 거의 모든 PS의 문제들이 오토마타 문제로 분류될 수 있다. 오토마타는 순서도와도 매우 비슷하다. 순서도에서도 표현하는 방식이 있듯이 오토마타도 표현 방법이 정해져있다.M: 오토마타( M = {Q, ∑, δ, S0, F} )Q: 상태의 집합(Q ≠ { })∑:..

이전 숫자에서 k개의 연속된 숫자를 외칠 수 있고 n을 외치면 승리하는 조건에서,n+1 길이의 dp를 생성하고, 필승패를 1로 표기, 나머지는 0으로 표기한다. [cpp]// 최선의 수를 둘 때 선공이 승리할 수 있으면 True#include using namespace std;bool NIM(int n, int k) { vector dp(n + 1, 0); for (int i = n; i > 0; i--) { for (int j = i + 1; j  [python]# 최선의 수를 둘 때 선공이 승리할 수 있으면 Truedef NIM(n, k): dp = [0] * (n + 1) for i in range(n, 0, -1): for j in range..

[자료구조]- 강한 연결 요소(SCC)- 트라이(Trie) [정수론]- 밀러-라빈 소수판별법 [기하]- 두 직사각형의 겹치는 영역 넓이 구하기 [동적계획법]- 님게임, 돌게임, 배스킨라빈스 31 게임 류