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) 한 상태에서 하나의 입력을 받았을 때 다음 상태가 두 개 이상인 것을 말한다. 지금은 무슨 뜻인지 몰라도 된다. 뒤에서 다시 나오니 이런 것이 있다 정도만 알고 ..

https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 문제 설명 입력된 G값은 현재 몸무게의 제곱에서 기억하고 있던 몸무게의 제곱을 뺀 값이다. 현재 몸무게로 가능한 모든 수를 출력해야 한다. 풀이 방법 투 포인터를 활용해 간단하고 효율적으로 해결할 수 있다. 모든 수를 출력하는 것 외에 다른 제한이 따로 없어서 당황할 수 있는데 규칙을 찾으면 반복의 종료 조건을 찾을 수 있다. 예제 입력으로 흐름을 따라가보자. 먼저 기억하고 있던 몸무게를 left, 현재 몸무게..

대표적인 문법 표현 방법은 정규 표현, 구문 도표, BNF, EBNF가 있다. 1. 정규 표현 정규 표현(regular expression)은 정규 언어를 가장 잘 표현할 수 있는 방법이다. 정규 표현은 다음과 같이 재귀적으로 정의된다. 기본 단계 : 기본을 정의하는 세 가지 규칙이 있다. \(\varnothing\)는 공집합을 나타내는 정규 표현이다. \(\varepsilon \)은 공문자열을 나타내는 정규 표현이다. 터미널 기호인 a는 집합 {a}를 나타내는 정규 표현이다. 귀납 단계 : r과 s가 정규 언어 L(r)과 L(s)를 나타내는 정규 표현이라면 (r) + (s)는 L(r) \(\cup\) L(s)를 나타내는 정규 표현이다. (r) \(\cdot\) (s)는 L(r) \(\cdot\) L(s..

형식 문법은 크게 두 가지 방법으로 정의할 수 있다. 생성 규칙(Production Rule)만으로 표현 항목으로 정의 1. 형식 문법 형식 문법 \(G=(V_N,V_T,P,S)\) 는 다음과 같이 네 가지 항목으로 정의된다. \(V_N\): 논터미널 기호의 유한집합 \(V_T\): 터미널 기호의 유한집합 \(V_N\cap V_T=\varnothing ,V_N\cup V_T=V\) 터미널 기호와 논터미널 기호를 문법 기호(grammer symbol)라 하며 보통 \(V^{vocabulary}\)로 표시한다. \(P\): 생성 규칙의 유한집합 \(\alpha \to \beta, \alpha \in V^+, \beta \in V^*\) \(\alpha\)를 왼쪽 부분(left-hand side), \(\be..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 설명 주어진 조건대로 동작하는 시뮬레이션 문제이다. 문제를 잘 읽고 알고리즘을 구현해야 한다. 특별히 부연설명할 게 없어서 설명은 사이트를 참고하면 좋겠다. 풀이 방법 주어진 조건대로 구현하면 되는 심플한 문제이다. 대신 조건이 많아서 꼼꼼히 예외처리를 해줘야 한다. 필자는 큐를 활용해서 해결했다. BFS를 약간 변형했다. 코드를 읽어내려가면..