Trivia 100 No.1 문제 : WkVkb2NHTXliSHBrTWtaNVlsZHNkVm96Vm5kalNFcDJXVzE0YkdKV lpIWmtSemt3WVVkV1QxcFlhREJWU0VwMldXMTRiR0pSUFQwPQ== trivia. isn't it? 문자열 맨 뒤에 Equal(=)이 몇 개 이어져 있다면 Base64 Encoding을 의심해 봐야 한다. Base64 Encoding은 모든 8비트 문자를 64개의 문자로 표시하기 위한 것이다. 64개의 문자를 표현하는 데에는 6비트가 필요하며, 64개의 문자는 다음과 같다. ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/= Base64의 Encoding 방법은 다음과 같다. 1. Encoding될 문자열을 6.. 더보기 Manhattan (2SAT) Manhattan 당신에게 임무가 주어졌다. 도시의 도로를 디자인 하는 것이다. 당신의 도시에는 수평으로 나있는 도로가 있고 수직으로 나있는 도로가 있어 격자를 이루고 있다. 디자인 한다는 것은 각각의 수평, 수직도로의 방향을 결정하는 것이다. 각 도로는 결정된 단 하나의 방향으로만 이동해야 한다. 또한 시민들은 당신에게 자신들의 요구사항을 말해줄 것이다. '요구'는 자신이 원하는 시작 위치에서 끝 위치까지 단순한 경로가 하나 이상 존재해야 한다는 것이다. 아래의 그림을 보도록 하자. 시민 한사람의 요구사항이 그림과 같을 때 a)는 불가능한 경로이다. 왜냐하면 도로의 방향대로 움직이지 않았기 때문이다. b)는 가능한 경로이긴 하지만 단순한 경로가 아니다. 단순한 경로는 정확히 한 번 굴절된 경로를 말한다.. 더보기 P vs NP (2) - 문제의 환원과 NP-완전성으로의 응용 0. 간단한 복습 먼저 P와 NP에 대한 간단한 복습으로부터 시작하자. P 문제는 '결정성 알고리즘으로 다항식 시간 내에 해결 가능한 결정형 문제'이다. '결정성 알고리즘', '다항식 시간', '해결 가능하다', '결정형 문제'와 같은 용어들은 모두 이미 친숙하리라고 가정하고 앞으로 설명할 것이다. P 문제들의 집합을 P 클래스라 한다. NP 문제는 '비결정성 알고리즘으로 다항식 시간 내에 해결 가능한 결정형 문제'이다. P 문제와 다른 점이라면 알고리즘이 결정성이냐 비결정성이냐의 차이이다. NP 문제들을 집합을 NP 클래스라 한다. 결정성 알고리즘은 비결정성 알고리즘에서 비결정도가 1인 특수한 경우이다. 그러므로 P 클래스가 NP 클래스에 포함됨은 명백하다. 역으로 NP클래스가 P클래스에 포함되는지는 .. 더보기 이전 1 2 3 4 ··· 15 다음
