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 게임 류

직사각형의 위치를 다음과 같이 두 점의 좌표로 표현하자.두 직사각형 (x1, y1), (x2, y2)와 (x3, y3), (x4, y4)가 있다.(x1 두 직사각형이 겹치는 영역은 다음과 같이 표현할 수 있다. [cpp]int area = max(min(x2, x4) - max(x1, x3), 0) * max(min(y2, y4) - max(y1, y3), 0); [python]area = max(min(x2, x4) - max(x1, x3), 0) * max(min(y2, y4) - max(y1, y3), 0)

1. 모듈러 기본 연산모듈러 연산은 나머지를 구한다. 파이썬에서는 산술 연산자 %와 같다. 10 mod 3 = 10 % 3 = 1. 두 수 a, b에 대해 어떤 수로 모듈러 연산을 했을 때 결과가 같다면 a, b는 모듈러 합동이라고 한다. 합동 기호를 똑같이 사용하고 예를 들어 이런 식으로 표기한다.13 mod 4 = 1 (13을 4로 나눈 나머지는 1이고)9 mod 4 = 1 (9를 4로 나눈 나머지도 1이다.)13 ≡ 9 mod 4 ()보통 0 이상의 정수에만 모듈러를 사용하는 경우가 많다. 실제로 나머지가 있는 나눗셈은 초등학교 수준의 수학에서만 다루고 있다. 하지만 괴물같은 수학자들이 이런 연산을 0 이상의 정수에만 사용하게 냅둘리가 있나. 모듈러는 음수에도 적용할 수 있다. 음수로 확장된 모듈..

1. 정점이 용량을 갖는 유량 그래프최대유량 문제에서는 간선으로 용량 정보가 주어진다. 근데 만약 정점에 용량이 있다면? 음의 유량 처리 과정에 문제가 생긴다. 포드 풀커슨의 방법에서 가장 핵심적인 아이디어는 음의 유량을 만들어 기존 유량을 우회시키는 테크닉이다.정점 중심으로 생각해보면 정점 3은 나가는 방향의 간선 용량의 총합인 3의 용량을 갖는다고 할 수 있다. 1→3의 유량 2를 우회시키면 s-2-3-5-t에 2의 유량을 흘려보낼 수 있다. 여기서 유량 우회가 가능한 이유는 유량을 간선 정보로 관리하고 있기 때문이다. u-v 간선 용량을 capa[u][v], u-v 간선의 현재 유량을 flow[u][v] 라고 표현하면 그래프 자체에서 u와 v의 순서로 간선의 방향 정보를 모두 관리하고 있는 셈이다...