https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 문제 설명 기본적인 조합 문제이다. 예제 1로 예를 들면 headgear라는 의상 종류에 hat, turban이라는 두 의상이 있고, eyewear에 suglasses라는 하나의 의상이 있다. 이 경우 {hat}, {turban}, {sunglasses},{hat, sunglasses}, {turban, ..

https://www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다 www.acmicpc.net 문제 설명 주어진 두 수의 최소공배수를 출력해야 한다. 입력값 범위를 고려해 long을 사용해야 한다. 풀이 방법 두 수의 최소공배수는 (두 수의 곱) / 최대공약수로 해결할 수 있다. 최대공약수는 유클리드 호제법을 활용하여 간단하게 구현할 수 있다. import java.io.*; class Main { public st..

이번엔 \(\varepsilon\)-전이가 없는 NFA를 DFA로 변환해보자. 변환 알고리즘은 다음과 같다. NFA에 의해 인식되는 언어를 L이라고 하면 L을 인식하는 DFA가 존재한다. L을 인식하는 NFA \(M = (Q, \sum , \delta , q_0, F\)라 하면 L을 인식하는 DFA \(M^\prime = (Q^\prime, \sum , \delta^\prime, q_0^\prime, F^\prime\)는 다음과 같이 구성된다. \(Q^\prime = 2^Q\), 즉 \(Q^\prime\)의 한 상태는 \([q_1, q_2, \cdots , q_i]\)의 형태로 나타낸다. 단, \(q_j \in Q(j=1, 2, \cdots , i\)이다. \(F^\prime=\{q \in Q^\prim..

NFA에서 DFA로 변환하기 전에 NFA와 DFA가 서로 동등해야만 변환의 의미가 있다. 다만 증명 부분은 생략한다. NFA와 DFA는 동등하다는 것만 알고 넘어가자. \(\varepsilon\)-전이가 있는 NFA를 DFA로 변환 \(\varepsilon\)-closure를 이용하여 변환하는데 NFA에서 의미가 같은 여러 개의 상태가 DFA에서 하나의 상태로 변환되는 것이다. 먼저 \(\varepsilon\)-closure(S)에 대한 정의부터 살펴보자. \(\varepsilon\)-closure(S) S가 하나의 상태일 경우 \(\varepsilon\)-closure(S)는 NFA의 상태 S와 상태 S로부터 \(\varepsilon\)-전이에 의해 도달될 수 있는 NFA의 모든 상태의 결합이다. 이 ..

https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 문제 설명 소수 A를 소수 B로 바꾸는 최소 단계를 구해야 한다. A를 B로 바꿀 때는 한 자릿수만 바꿀 수 있으며 바꾼 수 또한 소수여야 한다. 또한 네 자리 소수만 허용하므로 0039와 같은 수는 안 된다. 풀이 방법 이 문제는 소수 구하기와 BFS가 결합된 문제이다. 소수 구하기 에라토스테네스의 체를 활용해서 해결한다. import java.io.*; import java.util.*; class M..

1. 오토마타란? 디지털 컴퓨터의 추상적 모델로서 입력 자료를 읽는 입력장치, 출력을 하는 출력장치, 무한개의 기억 소자로 이루어진 임시 기억장치, 유한개의 내부 상태 중 하나의 상태를 항상 유지하는 제어장치로 구성된다. 글로 써놓으니 와닿지는 않는데 그냥 컴퓨터를 추상적으로 표현한 것과 같다. 오토마타는 결정적 오토마타와 비결정적 오토마타로 구분할 수 있다. 결정적 오토마타(deterministic automata) 한 상태에서 하나의 입력을 받았을 때 다음 상태가 유일하다. 비결정적 오토마타(non-deterministic automata) 한 상태에서 하나의 입력을 받았을 때 다음 상태가 두 개 이상인 것을 말한다. 지금은 무슨 뜻인지 몰라도 된다. 뒤에서 다시 나오니 이런 것이 있다 정도만 알고 ..