[BOJ] 16기 SW마에스트로 1차 코테대비

Coding Test Study 2025 Soma1

💻20250116~31 (실3~골2)

1. 모든 순열 (실3) 10974

백트래킹

• answer의 길이가 N이 되면 출력

• 1부터 N까지 돌리면서 answer에 추가와 제거를 반복하면 된다.

2. 단어 뒤집기 2 (실3) 17413

문자열, 스택

• "<"이면 stack에 넣고 word가 있다면 뒤집어서 출력한다.

• stack이 있으면 문자열을 그대로 출력한다.

• stack이 비어 있고 공백이면 뒤집어서 출력하고, 글자이면 word에 추가한다.

• ">"이면 stack을 비운다.

3. 카잉 달력 (실1) 6064

수학

• 마지막 해는 M과 N의 최소공배수이다.

• i를 0부터 하나씩 늘려가면서 mod로 x와 y에 해당하는 값을 찾을 수 있다.

• M*i+x가 최소공배수가 커도 -1을 출력해야 한다.

1. 여행 가자 (골4) 1976

DFS

• 유니온 파인드로도 풀 수 있는 문제이다.

• 여행 계획 도시 정보를 [1, 2, 3, 2, 3]으로 입력했다면 set_order에는 {(1, 2), (2, 3)}만 저장된다. [1-2, 2-3, 3-2, 2-3]에서 중복되는 것을 제거했다.

1. 욕심쟁이 판다 (골3) 1937

DFS+DP

• 한 번 갔던 경로는 중복이므로 DP에 그 지점부터 갈 수 있는 최대 칸 수를 저장하여 풀 수 있다.

• 예를 들어 2→3→4→5 경로를 계산한 후 그 다음 1→2로 갔다면 2에서 갈 수 있는 최대 칸 수를 다시 계산하지 않아도 된다.

시작 지점과 dp 테이블 출력 결과

시작 지점: 0 0
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

시작 지점: 0 1
1 3 1 0
0 2 0 0
0 1 0 0
0 0 0 0

시작 지점: 0 3
1 3 1 2
0 2 0 0
0 1 0 0
0 0 0 0

시작 지점: 1 0
1 3 1 2
3 2 0 0
2 1 0 0
0 0 0 0

시작 지점: 1 2
1 3 1 2
3 2 3 0
2 1 0 0
0 0 0 0

시작 지점: 1 3
1 3 1 2
3 2 3 4
2 1 0 1
0 0 0 0

시작 지점: 2 2
1 3 1 2
3 2 3 4
2 1 4 1
0 0 1 0

시작 지점: 3 0
1 3 1 2
3 2 3 4
2 1 4 1
3 0 1 0

시작 지점: 3 1
1 3 1 2
3 2 3 4
2 1 4 1
3 4 1 0

시작 지점: 3 3
1 3 1 2
3 2 3 4
2 1 4 1
3 4 1 2

1. 빵집 (골2) 3109

그리디+DFS

• 그리디인 이유는 [-1, 0, 1]으로 탐색해야 하기 때문이다. 그 외의 이유는 없어 보인다.

• 다음으로 갈 수 있으면 "x"로 변경한 후 dfs를 돌린다. 이때 dfs가 마지막 지점에 도달해서 True이면 더이상 dfs를 할 필요가 없고, 다시 루트까지 True를 반환하게 해야 하므로 16, 17줄 조건문을 추가해준다.

[예제 입력 1] 어떤 행이 도착 지점까지 가는지 확인
※ 실제 코드에서는 숫자가 아니라 “.”으로 변경한다.

0 x x . 0
. 0 x 0 .
. . 0 . .
. . . x .
. . . x .

0 x x . 0
1 0 x 0 1
. 1 0 1 .
. . 1 x .
. . . x .

0 x x . 0
1 0 x 0 1
2 1 0 1 .
. 2 1 x .
. . 2 x .

0 x x . 0
1 0 x 0 1
2 1 0 1 .
3 2 1 x .
. 3 2 x .

0 x x . 0
1 0 x 0 1
2 1 0 1 .
3 2 1 x .
4 3 2 x .

1. 공항 (골2) 10775

그리디

• visited에는 그 게이트에 비행기가 도킹되어 있는지 여부만 담고, result에 해당 비행기가 도킹할 수 있는 최댓값을 담는다.

• 4 비행기가 4에 도킹했다면 result는 3이 되고 다음 4 비행기는 3에 도킹할 수 있는 것이다.

[예제 입력 2] visited와 result 출력 결과

2
visited [0, 0, 1, 0, 0]
result [0, 1, 1, 3, 4]

2
visited [0, 1, 1, 0, 0]
result [0, 1, 0, 3, 4]

3
visited [0, 1, 1, 1, 0]
result [0, 1, 0, 2, 4]

1. 탈출 (골4) 3055

BFS

• "다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다." 라는 조건이 있기 때문에 물을 먼저 채운 다음 고슴도치를 이동시킨다.

• 물을 한 번 채우고 고슴도치를 이동시키기 때문에 미리 큐의 길이를 저장해두고 그 길이만큼만 반복문을 돌렸다.

• 물은 "S"와 "."일 때 채울 수 있고, 고슴도치는 "."일 때 이동할 수 있다.

[예제 입력 1] arr 변화

D * *
. S *
S S S

D * *
S * *
S S *

3

[예제 입력 2] arr 변화

D * *
. . *
. S S

D * *
. * *
S S *

D * *
* * *
S * *

KAKTUS

1. 배 (골5) 1092

그리디

• 크레인과 박스를 모두 내림차순 정렬한다.

• 크레인의 가장 큰 값이 박스의 가장 큰 값보다 작으면 결국엔 못 옮기는 박스가 생기므로 -1을 출력하고 끝낸다.

• 현재 박스 중 가장 작은 값이 현재 크레인보다 크면 다음 크레인으로 넘어간다.

• 현재 크레인보다 작거나 같은 박스를 발견하면 그 박스를 배열에서 제거한 후 다음 크레인으로 넘어간다.

1. 스위치 켜고 끄기 (실4) 1244

구현

• 남자면 mod로 바꿀 스위치를 찾는다.

• 여자면 현재 위치로부터 -i, +i가 다를 때까지 혹은 범위를 벗어날 때까지 스위치를 계속 바꾼다.

2. 풍선 터뜨리기 (실3) 2346

구현

• num은 현재 위치에 적힌 숫자다. num만큼 이동해야 한다.

• 풍선이 터졌으므로 현재 위치를 0으로 초기화해준다.

• num이 음수면 터진 풍선을 발견했을 때 더 왼쪽으로 가야하므로 방향(d)을 정해준다.

• cnt가 num이 될 때까지 반복하는데 1과 N이 연결되어 있으므로 N보다 커지면 1로 이동하고, 1보다 작아지면 N으로 이동한다.

• 터진 풍선을 발견하지 않았을 때 cnt를 하나 늘려준다.

💡 마지막 풍선까지 0으로 바꾼 후에 while문으로 들어가면 무한 루프가 생긴다. 그 전(14, 15줄)에 for문을 탈출하자

3. 음식물 피하기 (실1) 1743

DFS

• 기본적인 dfs 문제이다.

• 음식물의 위치를 1로 지정한 graph를 만든다.

• 현재 위치가 1이면 dfs를 호출한다. dfs 함수는 음식물 크기를 세면서 1을 0으로 바꾸는 작업을 한다.

1. 미로 탈출하기 (골3) 17090

DFS

• dp 값은 세 가지이다. 0: 방문x, 1: 탈출 가능, 2: 탈출 불가능

• dp가 0이면 아직 계산을 안 한 것이므로 dfs를 호출한다.

• 처음 값은 2로 초기화한다.

• 다음으로 갈 수 있다면 dfs를 재귀 호출하고, 다음 위치가 1이라면 현재 위치는 탈출 가능하므로 1로 갱신한다.

• dp가 0이 아니라면 이미 탈출 가능 여부를 알고 있는 것이므로 바로 리턴한다.

• 예를 들어 2x2인 곳에서 (0, 0)->(1, 0)->(2, 0)이면 (2, 0)에서 1을 반환하고 그 1이 dp[1][0]의 값이 되는 것이다.

1. 가르침 (골4) 1062

집합+조합

• 파이썬에서 조합을 백트래킹으로 구현하면 너무 느리기 때문에 내장 함수를 썼다.

• word를 집합으로 바꿔서 넣는다. 추후에 단어 조합도 집합이기 때문에 이 두 개를 비교하려면 둘 다 집합인 것이 편리하다.

• alpha 집합은 현재 쓰이는 모든 단어들이다.

• alpha에서 "antic"을 뺀 나머지 단어들이 K-5보다 작거나 같으면 무조건 N개를 다 읽을 수 있기 때문에 바로 출력한다. 또 뒤에서 조합을 사용하는데 result의 길이가 K-5보다 작으면 조합이 빈 값을 뱉어내기 때문에 무조건 처리를 해주어야 한다.

• 만든 조합으로 comb_set을 만들어서 단어를 만들 수 있는지 확인한다. w가 comb_set의 부분 집합인지 확인하는 방법은 "<=" 연산자이다.

1. 앱 (골3) 7579

DP

• 이차원 dp를 사용하면 앞에서부터 계산해도 되지만, 일차원 dp를 사용하면 dp[j-c] 과정에서 앞에 결과가 반영되기 때문에 뒤에서부터 계산하여 이차원 결과값이 저장되어 있는 효과를 가져가야 한다.

• dp[j]는 선택을 안 했을 때이다.

• dp[j-c]+m은 현재 앱을 선택했을 때이다.

• 계산 도중 dp[j]가 M보다 크거나 같으면 answer를 갱신하다.

dp 변화

[0, 0, 0, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30]
[10, 10, 10, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40]
[10, 10, 10, 40, 40, 40, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60]
[10, 10, 10, 40, 40, 45, 60, 60, 75, 75, 75, 95, 95, 95, 95, 95]
[10, 10, 10, 40, 50, 50, 60, 80, 80, 85, 100, 100, 115, 115, 115, 135]

1. 암호코드 (골5) 2011

DP

• 0일 때 처리를 잘 해야 한다.

01234 -> 불가능(첫 번째 숫자가 0)

00 -> 불가능(0 두 번 연속)

30 -> 불가능(1~26 숫자만 가능)

• 피보나치의 규칙을 가지고 있지만 26보다 큰 숫자나 0이 나왔을 때 잘 끊어주면서 계산해야 한다.

dp 출력 결과

25114
[1, 2, 2, 4, 6]

1111111111
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

121074110
[1, 1, 2, 3, 2, 2, 2, 2, 4, 2]

1. 트리 (골5) 1068

DFS

• 자식으로만 가니까 단방향 그래프로 그리면 된다.

• 그래프 그릴 때 없애는 노드의 부모와 자식 노드를 없애면 그 노드로 절대 갈 수 없다.

💡 루트가 꼭 0이 아닐 수도 있다. 그래프 만들면서 -1일 때 루트를 설정해준다.

💡 루트 노드를 삭제하면 0이 나와야 하므로 19, 20줄을 추가해준다. 이 처리를 안 하면 루트 노드를 바로 리프 노드로 인식한다.

1. 물병 (골5) 1052

그리디

• 2의 제곱수들로 N을 만든다.

• 예제 3으로 보면 2^19, 2^18, 2^17, 2^16, 2^14, 2^9, 2^6으로 1000000을 만들 수 있다.

• 이때 물의 양이 다 다르기 때문에 물병은 7개가 필요하다. K개에 맞추려면 물병을 더 사서 다른 물과 양을 동일하게 만들어 합쳐야 한다.

• 물병을 최소로 사야하므로 2^9와 2^6에 물병을 더 사서 2^14에 맞추는 게 최적해다.

• 만약 문제가 4 2이면 2^2 하나로 물병 하나를 만들 수 있기 때문에 arr 배열 길이가 K보다 작아서 정답은 0이 된다.

arr 배열 출력 결과

3 1
arr: [1, 0]
// 2-1 = 1

13 2
arr: [3, 2, 0]
// 4-1 = 3

1000000 5
arr: [19, 18, 17, 16, 14, 9, 6]
// 2^14-2^9-2^6 = 15808

4 2
arr: [2]
// 0

1. 토너먼트 (실4) 1057

브루트포스

• 각 라운드의 가장 큰 수로 계속 바꿔준다.

• 1이 1라운드 때는 2, 2라운드 때는 4, 3라운드 때는 8 이런 식으로 계속 변경해주면서 a와 b가 같을 때를 찾으면 된다.

• 홀수이거나 부전승일 때도 토너먼트가 완전한 개수가 있다고 가정하고 푼다.

💡 한수와 지민이가 안 만나는 경우는 없다. -> -1 출력 X

계속 부전승일 때 예시
9까지 밖에 없지만 16개가 다 있다고 가정하고 푼다.

9 9 7
10 8
12 8
16 8
16 16
4

2. 팰린드롬 만들기 (실3) 1213

구현

• 각 알파벳의 개수를 다 세준다.

• 현재 알파벳 개수가 짝수면 answer에 절반만큼 추가한다.

• 현재 알파벳 개수가 홀수인데 이미 홀수인 알파벳이 존재한다면 문구를 추가하고 종료한다.

• 홀수인 알파벳이 없다면 절반만큼 answer에 추가하고 odd에 해당 알파벳을 저장한다.

• "answer+홀수개 알파벳(가운데)+answer 뒤집은 것"으로 팰린드롬을 구한다.

3. 참외밭 (실2) 2477

구현

• 각 길이의 개수를 세준다. cnt가 1이라면 긴 변이고, 2라면 짧은 변이다.

• [긴, 긴, 짧, 짧, 짧, 짧] 순서대로 있을 때 짧 4개 중 중간 2개가 내가 찾으려는 변이다. (그림을 그려보면 안다. 긴 변들의 대각선 변들을 구해야 하기 때문이다.)

• 하지만 [짧, 짧, 긴, 긴, 짧, 짧]이 되면 답을 구하기가 어려워지므로 첫 번째 "긴"의 인덱스를 start로 고정해두고 배열을 돌리면 다시 [긴, 긴, 짧, 짧, 짧, 짧] 이런 형태로 배열을 탐색할 수 있다.

💡 첫 번째 "긴"이 start가 아니어도 된다. "짧" 4개가 연속으로 붙어있는 형태로 배열을 탐색할 수 있으면 된다. ([긴, 짧, 짧, 짧, 짧, 긴]도 가능)

• cnt가 1이면 long 배열에 추가하고 cnt가 2이면 short 배열에 추가한다.

• 그럼 long은 [긴, 긴], short는 [짧, 짧, 짧, 짧]이 될 것이다.

• 중간 2개의 짧이 내가 구하는 변들이므로 "short[1]*short[2]"를 빼준다.

💻20250201~15 (실3~골5)

1. 나의 인생에는 수학과 함께 (골5) 17265

DFS

💡 maxDp는 0이 아니라 -INF로 초기화해야 한다.

• arr[x][y]가 숫자면 이전 숫자와 연산자로 계산한 후 dp를 갱신하고 빈 op를 인자로 dfs를 재귀 호출한다.

• arr[x][y]가 연산자면 op 인자에 arr[x][y]를 넣고 dfs를 재귀 호출한다.

1. 수리공 항승 (실3) 1449

정렬&그리디

• 오름차순 정렬 후에 테이프를 붙일 수 있다면 테이프 마지막 지점을 갱신한다.

• 현재 물이 새는 곳에 테이프가 붙여져 있다면 넘어간다.

1. 집합의 표현 (골5) 1717

유니온 파인드

• 두 집합을 합치는 걸 유니온 파인드로 하면 된다.

• 부모를 계속 갱신해주고 a와 b의 부모가 같으면 YES를 출력한다.

1. 국회의원 선거 (실5) 1417

힙

• 최대힙으로 구현해서 h[0]을 하나 감소하고 다솜이(D)를 하나 증가시킨다.

• 그 후 h[0]을 다시 힙에 넣는다.

1. 퇴사 2 (골5) 15486

DP

• 뒤에서부터 계산한다. T는 미래에 영향을 끼치기 때문이다.

• i+T가 N보다 작거나 같으면 "현재 상담하기" vs "이전 값 그대로 가기" 중에 큰 걸 고른다.

• i+T가 N보다 크면 이전 값을 현재 dp에 넣는다.

[예제 입력 1] dp 변화

[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 15, 0, 0, 0]
[0, 0, 0, 35, 15, 0, 0, 0]
[0, 0, 45, 35, 15, 0, 0, 0]
[0, 45, 45, 35, 15, 0, 0, 0]
[45, 45, 45, 35, 15, 0, 0, 0]

[예제 입력 4] dp 변화

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 30, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 30, 30, 0, 0, 0]
[0, 0, 0, 0, 0, 40, 30, 30, 0, 0, 0]
[0, 0, 0, 0, 50, 40, 30, 30, 0, 0, 0]
[0, 0, 0, 60, 50, 40, 30, 30, 0, 0, 0]
[0, 0, 70, 60, 50, 40, 30, 30, 0, 0, 0]
[0, 80, 70, 60, 50, 40, 30, 30, 0, 0, 0]
[90, 80, 70, 60, 50, 40, 30, 30, 0, 0, 0]

1. 주사위 (골5) 1041

구현

• 1일 때는 5개 면이 보이므로 제일 큰 값을 빼고 종료한다.

• 주사위 형태로 볼 수 있는 것은 꼭짓점(3면), 변(2면), 중앙(1면)이다. 각각 최솟값을 구해준다.

• 맨 윗층과 나머지 층이 노출되는 면이 다르다. "꼭대기층 + 나머지*(N-1)"로 답을 구한다.(아래 참고)

ex) 5x5일 때

꼭대기층(top)
3 2 2 2 3
2 1 1 1 2
2 1 1 1 2
2 1 1 1 2
3 2 2 2 3
규칙: 4개는 3면, (N-2)*4는 2면, (N-2)*(N-2)는 1면

나머지층(rest)
2 1 1 1 2
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
2 1 1 1 2
규칙: 4개는 2면 (N-2)*4는 1면

1. 합분해 (골5) 1041

DP

K와 N에 따라 답이 다르기 때문에 dp는 KxN인 2차원 배열이 된다.

K=1) 0씩 증가한다.(1, 1, 1, 1, ···)

K=2) 1씩 증가한다.(1, 2, 3, 4, ···)

K=3) 2, 3, 4, ···씩 증가한다. (1, 3, 6, 10, ···)

K=4) 3, 6, 10, ···씩 증가한다. (1, 4, 10, 20, ···)

이 규칙은 "행 하나 직전 값+열 하나 직전 값"이다.

[예제 입력 2] dp 출력 결과

6 4
0 0 0 0 0 0 0
1 1 1 1 1 1 1
1 2 3 4 5 6 7
1 3 6 10 15 21 28
1 4 10 20 35 56 84
84

💻20250216~28 (골2)

1. 트리의 지름 (골2) 1167

DFS

아무 노드에서 시작해서 가장 먼 노드를 찾는다. 이 노드가 지름을 이루는 두 노드 중 하나다.

그 노드에서 다시 DFS를 실행해서 가장 먼 거리를 구한다. 이 거리가 "트리의 지름"이다.

1. 가장 긴 바이토닉 부분 수열 (골4) 11054

DP

앞에서부터 LIS 구하고, 뒤에서부터 LIS를 구한다.

특정 지점에서 dp1과 dp2의 합이 가장 크면 그 부분이 정답이다.

[예제 입력 1] dp1과 dp2 출력 결과

10
1 5 2 1 4 3 4 5 2 1
dp1: [1, 2, 2, 1, 3, 3, 4, 5, 2, 1]
dp2: [1, 5, 2, 1, 4, 3, 3, 3, 2, 1]

1. 친구 네트워크 (골2) 4195

유니온 파인드

원래 유니온 파인드는 루트 노드를 저장한다.

이 문제는 각 집합에 있는 노드 개수를 알아야 하므로 부모 노드와 집합 개수를 둘다 parent 배열에 저장해야 한다.

따라서 음수이면 루트로 판단하고 개수의 음수를 저장한다. 루트가 아니면 부모 노드를 저장한다.

[예제 입력 1]

[예제 입력 2]

1. 게임 개발 (골3) 1516

DP

3중 for문으로 풀었지만 위상 정렬+그래프로도 풀 수 있는 것 같다.

각 행에 [i]를 추가하여 node를 넣는다. 마지막에 노드 순서대로 dp값을 출력하기 위함이다.

각 행을 돌면서 "이전 건물" dp가 0보다 작으면 계산을 멈춘다.

모든 "이전 건물" dp가 0보다 크면 건물이 다 지어져 있다는 뜻이므로 최댓값을 계산한다.