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

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