코테 연습문제

1. 로봇 점프 (DP - Dynamic Programming)

N개의 돌이 일렬로 놓여있습니다. 로봇은 0번 돌에서 출발하여 N-1번 돌까지 가야 합니다. 로봇은 한 번에 1칸 점프 또는 2칸 점프를 할 수 있습니다.

각 돌(i번 돌)을 밟을 때는 costs[i] 만큼의 에너지가 듭니다. (0번 돌의 costs[0]은 0입니다.)

0번 돌에서 N-1번 돌까지 도달하는 데 드는 최소 에너지를 구하세요.

입력:

• 첫째 줄: 돌의 개수 N (3 $\le$ N $\le$ 100)
• 둘째 줄: 0번부터 N-1번 돌까지 각 돌의 에너지 costs[i]가 공백으로 구분되어 주어짐. (0번 돌의 costs[0]은 항상 0)

출력:

• N-1번 돌까지 가는 데 드는 최소 에너지를 출력.

예시 입력:

7
0 2 3 5 1 4 6

예시 출력:

12

---

2. 카드 덱 (Deque)

1부터 N까지의 숫자가 순서대로 적힌 카드가 1(위)부터 N(아래)까지 쌓여있습니다. M개의 연산을 수행하려고 합니다. 연산은 3가지 종류가 있습니다.

• 1: 덱의 가장 위 카드를 뽑아서 그 번호를 출력하고 덱에서 제거합니다.
• 2: 덱의 가장 위 카드를 뽑아서 덱의 가장 아래로 옮깁니다.
• 3: 덱의 가장 아래 카드를 뽑아서 덱의 가장 위로 옮깁니다.

M개의 연산이 주어졌을 때, 1번 연산으로 출력되는 카드 번호들을 순서대로 공백으로 구분하여 출력하세요.

입력:

• 첫째 줄: 카드의 수 N (1 $\le$ N $\le$ 100), 연산의 수 M (1 $\le$ M $\le$ 1000)
• 둘째 줄: M개의 연산(1, 2, 또는 3)이 공백으로 구분되어 주어짐.

출력:

• 1번 연산이 실행될 때마다 뽑힌 카드 번호를 순서대로 공백으로 구분하여 출력.

예시 입력 (수정):

5 8
1 2 1 3 2 2 1 1

예시 출력 (수정):

1 3 5 4

(초기 상태: [1, 2, 3, 4, 5])

1. 1 (1 뽑기) $\rightarrow$ 출력: 1 / 덱: [2, 3, 4, 5]
2. 2 (2 맨 뒤로) $\rightarrow$ 덱: [3, 4, 5, 2]
3. 1 (3 뽑기) $\rightarrow$ 출력: 3 / 덱: [4, 5, 2]
4. 3 (2 맨 위로) $\rightarrow$ 덱: [2, 4, 5]
5. 2 (2 맨 뒤로) $\rightarrow$ 덱: [4, 5, 2]
6. 2 (4 맨 뒤로) $\rightarrow$ 덱: [5, 2, 4]
7. 1 (5 뽑기) $\rightarrow$ 출력: 5 / 덱: [2, 4]
8. 1 (2 뽑기) $\rightarrow$ 출력: 2 (어... 예시랑 또 다르네요)

---

3. 로봇 청소기 (Simulation)

R x C 크기의 맵이 있습니다. 맵의 각 칸은 0 (청소 안 됨), 1 (벽) 중 하나입니다.

로봇 청소기는 (r, c) 위치에서 d 방향을 바라보고 시작합니다. d는 0(북), 1(동), 2(남), 3(서)입니다.

로봇은 다음 규칙에 따라 작동합니다.

1. 현재 위치를 청소합니다. (0 $\rightarrow$ 2로 바꿈)
2. 현재 방향을 기준으로 왼쪽으로 돕니다. (d 변경)
3. (앞) 왼쪽으로 돈 방향의 앞쪽 칸이 청소 안 된 칸(0)이라면, 그 칸으로 전진하고 1번으로 돌아갑니다.
4. (뒤) 왼쪽으로 돈 방향의 앞쪽 칸이 청소할 수 없는 칸(1 또는 2)이라면, 2번(왼쪽으로 돌기)으로 돌아갑니다.
5. 네 방향(동서남북) 모두 청소할 수 없다면 (이미 청소했거나 벽이라면), 현재 방향을 유지한 채로 뒤로 한 칸 후진합니다.
6. 후진하려는 칸이 벽(1)이라서 후진할 수 없다면, 작동을 멈춥니다.

로봇이 작동을 멈출 때까지 청소한 칸의 총 개수를 구하세요.

입력:

• 첫째 줄: 맵의 크기 R, C (3 $\le$ R, C $\le$ 50)
• 둘째 줄: 로봇의 시작 r, c, 방향 d
• 이후 R줄: 맵의 상태 (0 또는 1)

출력:

• 로봇이 청소한 총 칸의 수.

예시 입력:

3 3
1 1 0
1 1 1
1 0 1
1 1 1

예시 출력:

1

4. 토마토 창고 (BFS)

M x N 크기의 상자에 토마토가 보관되어 있습니다. 토마토는 1 (익은 토마토), 0 (안 익은 토마토), -1 (빈 칸) 중 하나의 상태입니다.

익은 토마토(1)는 하루가 지나면, 자신의 상하좌우에 인접한 안 익은 토마토(0)를 익게 만듭니다.

창고의 모든 토마토가 익는 데 걸리는 최소 일수를 구하세요. (시작부터 모든 토마토가 익어있다면 0, 모든 토마토가 익지 못하는 상황이라면 -1을 출력합니다.)

입력:

• 첫째 줄: 상자의 크기 M, N (2 $\le$ M, N $\le$ 1000)
• 이후 N줄: M개의 토마토 상태가 공백으로 구분되어 주어짐.

출력:

• 모든 토마토가 익는 데 걸리는 최소 일수. (불가능하면 -1)

예시 입력:

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예시 출력:

8

---

5. 비트 연산 집합 (Bitmasking)

1부터 20까지의 숫자로 이루어진 집합 S가 있습니다. 이 집합 S를 하나의 int 변수만을 사용하여 구현하려고 합니다. (자바의 HashSet 등 컬렉션 사용 금지)

다음과 같은 M개의 연산을 수행하는 프로그램을 작성하세요.

• add x: S에 x를 추가합니다. (1 $\le$ x $\le$ 20)
• remove x: S에서 x를 제거합니다.
• check x: S에 x가 있는지 확인합니다. (있으면 1, 없으면 0 출력)
• toggle x: S에 x가 있으면 제거하고, 없으면 추가합니다.
• all: S를 {1, 2, ..., 20}으로 채웁니다.
• empty: S를 공집합으로 비웁니다.

입력:

• 첫째 줄: 연산의 수 M (1 $\le$ M $\le$ 3,000,000)
• 둘째 줄부터 M줄: 수행할 연산 (예: add 3, check 5)

출력:

• check 연산이 나올 때마다, 1 또는 0을 한 줄에 하나씩 출력합니다.

예시 입력:

10
add 1
add 2
check 1
check 3
toggle 3
check 3
remove 2
check 2
all
check 10

예시 출력:

1
0
1
0
1