📜 사실 노션에서 쓰고 옮긴거라 노션이 더 가독성 좋아요.
https://yopark.notion.site/2-6d4edb0a4d7e4f4c9bbbad98879a5e54
쇼미더코드 (Show Me The Code) : 원티드 주관 코딩테스트 대회 ('22년 2회차) 링크
쇼미더코드는 2022년 올해 3, 6, 9, 12월 총 4회에 걸쳐 열릴 예정이라고 한다.
이번 2회차 대회는 07.02(토) 14~17시, 3시간 동안 진행되었다.
백준 환경과 완전히 동일하게 진행되니, 관심 있으신 분들은 9월에 열릴 3회차 대회에 참여해보시길 바란다.
1~2회차 모두 솔브닥 기준 난이도 Sliver I ~ Gold III 정도로 3문제가 출제되었으니 못 풀 정도는 아니다.
취업 목적 보단 재미삼아 참여해봤다가 A번 문제도 못 푼게 한이 돼서,
대회가 끝나고 백준에 문제가 올라왔길래 꼭 다 풀기로 결심했고, 결국 다행히도 다 풀었다.
💡 백준 홈페이지 - 문제 탭 - 문제 출처 - Contest로 들어가면 대회 출제 문제들을 만나볼 수 있다. 쇼미더코드 카테고리 링크
A. SHOW ME THE DUNGEON (Gold V)
B. Drop 7 (Gold V)
C. 수들의 합 8 (Gold III)
💡 이 포스팅을 읽고 계신 분들은, 이미 문제를 한 번 읽어보셨으리라 짐작되므로 문제는 간단하게 설명하고 넘어가겠다. 문제가 궁금하신 분들은 링크에 들어가 직접 보시길 바란다.
A. SHOW ME THE DUNGEON
문제 이해
체력 소모 부분이 한번에 이해 안 될 수 있다. 예시를 통해 이해해보자.
A = [100, 1, 50] 이라고 하자.
시루가 1→2→3번 마을 순으로 방문한다면, 다음의 체력이 소모된다.
- 1번 마을을 방문했을 때,
100의 체력 소모. - 2번 마을을 방문했을 때,
100+1=101의 체력 추가 소모. - 3번 마을을 방문했을 때,
100+1+50=151의 체력 추가 소모.
시루의 총 소모된 체력은 100+101+151=352이다.
당연하게도 방문한 순서에 따라 총 소모된 체력은 달라진다.
시루의 초기 체력이 K일 때,
체력을 최대 K만큼만 소모하면서 해방시킬 수 있는 주민의 최대 수를 구하는게 문제다.
Try #1. 배낭 문제(Knapsack Problem)로 접근, 틀렸습니다
대회 당시에는 알고리즘 분류를 볼 수가 없으니, 어떤 알고리즘을 쓸지도 본인이 생각해야 한다.
나는 이 문제가 과거 풀었던 12865번: 평범한 배낭 문제와 아주 비슷하다고 생각이 들었고, 배낭 문제로 구현하기 시작했다.
사실 이 문제의 알고리즘 분류는 백트래킹이었다.
import sys
input = lambda: sys.stdin.readline().rstrip()
# Knapsack
N, K = map(int, input().split())
A = [-1] + list(map(int, input().split()))
P = [-1] + list(map(int, input().split()))
# y축: 마을 번호, x축: '사용한' 체력
dp = [[0]*(K+1) for _ in range(N+1)]
for i in range(1, N+1):
attack, person = A[i], P[i]
for j in range(1, K+1):
dp[i][j] = dp[i-1][j]
k = 0
while j - attack - k >= 0:
dp[i][j] = max(dp[i][j], dp[i-1][j-attack-k] + person)
k += 1
print(max(dp[N]))예제 입출력도 모두 맞았고, 간단하게 만든 임시 테스트케이스도 정상적으로 나와서 제출했더니…
틀렸습니다를 받았다.
이러니 다른 문제를 건드릴 엄두가 안 났다.
배낭 문제로는 왜 못 푸는 건지..까지는 잘 모르겠지만, 백트래킹인 것만 알면 구현은 간단하다.
Try #2. 백트래킹으로 구현, 틀렸습니다
import sys
input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
A = list(map(int, input().split()))
P = list(map(int, input().split()))
def bt(used_hp, people):
global ans
if K-used_hp < 0:
return
ans = max(ans, people)
for i in range(N):
if visited[i]:
continue
visited[i] = True
bt(used_hp + used_hp + A[i], people + P[i])
visited[i] = False
visited = [False]*N
ans = 0
bt(0, 0)
print(ans)왜 틀렸을까요?
이 질문과 정확히 동일한 실수를 해버렸다.
위의 예시를 빌려 100, 1, 50 순으로 방문한다면,
총 사용한 체력은 100 + (100+1) + (100+1+50)이 되어야 하는데,
bt(used_hp + used_hp + A[i]) 를 사용하면 100 + (100+1) + (201+50) 이 되기 때문에 오류다.
이제까지 거쳐온 몬스터의 단순 공격력 합(path_sum)을 따로 저장해주어야 한다.
풀이
import sys
input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
A = list(map(int, input().split()))
P = list(map(int, input().split()))
def bt(used_hp, path_sum, people):
global ans
if K-used_hp < 0:
return
ans = max(ans, people)
for i in range(N):
if visited[i]:
continue
visited[i] = True
bt(used_hp + path_sum + A[i], path_sum + A[i], people + P[i])
visited[i] = False
visited = [False]*N
ans = 0
bt(0, 0, 0)
print(ans)B. Drop 7
요리봐도 조리봐도 구현, 시뮬레이션 문제다.
개인적으로 시뮬레이션 문제는 디버깅하기 쉬운 것 같다.
Try #1. 구현, 틀렸습니다
import sys
import copy
input = lambda: sys.stdin.readline().rstrip()
def fall(ball, x):
for y in range(7-1):
if grid[y+1][x]:
grid[y][x] = ball
return
grid[6][x] = ball
def get_disappear_list(grid):
ret = set()
for y in range(7):
cnt = 0
for x in range(7):
if grid[y][x]:
cnt += 1
if not cnt:
continue
for x in range(7):
if grid[y][x] == cnt:
ret.add((y, x))
for x in range(7):
cnt = 0
for y in range(7):
if grid[y][x]:
cnt += 1
if not cnt:
continue
for y in range(7):
if grid[y][x] == cnt:
ret.add((y, x))
return list(ret)
def gravity(grid, y, x):
while y != 0 and grid[y-1][x]:
grid[y][x] = grid[y-1][x]
grid[y-1][x] = 0
y -= 1
original_grid = []
for _ in range(7):
original_grid.append(list(map(int, input().split())))
ball = int(input())
ans = 49
for i in range(7):
grid = copy.deepcopy(original_grid)
fall(ball, i)
while True:
l = get_disappear_list(grid)
if not l:
break
for y, x in l:
grid[y][x] = 0
gravity(grid, y, x)
cnt = 0
for i in range(7):
for j in range(7):
if grid[i][j]:
cnt += 1
ans = min(ans, cnt)
print(ans)함수를 간단히 설명하자면,
fall(ball, i): ball 번호를 가진 공을 i번 열에 떨어트린다.get_disappear_list(grid): 7개의 행과 7개의 열을 순회하면서, 각 줄에서 사라질 공이 있는지 확인한 뒤, 사라질 공의(y, x)좌표를 리스트로 반환한다.gravity(grid, y, x):(y, x)의 값을 0으로 만든 직후 들어가는 함수로, 사라진 공의 빈 공간을 위에 있는 공으로 채운다.
예제 입력으로 디버깅한 결과 틀린 이유는, 공이 사라지는 조건을 잘못 이해해서 get_disappear_list 함수를 오작동하도록 짰기 때문이다.
가로 방향으로 연속해서 놓여있는 공들을 "가로 방향 그룹", 세로 방향으로 연속해서 놓여있는 공들을 "세로 방향 그룹"이라고 하자.
연속해서 놓여있는 것만 생각해야 되는데, 나는 단순히 그 줄에 있는 공의 개수를 셌다.
3 0 0 0 5 5 0 이런 건 3이 없어지는 경우가 아닌데, 없어지도록 구현했기 때문에 틀렸다.
Try #2. 맞왜틀? 틀렸습니다
import sys
import copy
input = lambda: sys.stdin.readline().rstrip()
def fall(ball, x):
for y in range(7-1):
if grid[y+1][x]:
grid[y][x] = ball
return
grid[6][x] = ball
def check(line):
ret = []
left = 0
while left < 7:
if not line[left]:
left += 1
continue
right = left+1
while right < 7 and line[right]:
right += 1 # 이제 line[left:right]에는 연속 수 리스트가 들어있음
cnt = right - left
i = left
while i < right:
if line[i] == cnt:
ret.append(i)
i += 1
left = right
return ret
def get_disappear_list(grid):
ret = set()
for y in range(7):
row = grid[y]
l = check(row)
for x in l:
ret.add((y, x))
for x in range(7):
col = []
for y in range(7):
col.append(grid[y][x])
l = check(col)
for y in l:
ret.add((y, x))
return list(ret)
def gravity(grid, y, x):
while y != 0 and grid[y-1][x]:
grid[y][x] = grid[y-1][x]
grid[y-1][x] = 0
y -= 1
original_grid = []
for _ in range(7):
original_grid.append(list(map(int, input().split())))
ball = int(input())
ans = 49
for i in range(7):
grid = copy.deepcopy(original_grid)
fall(ball, i)
while True:
l = get_disappear_list(grid)
if not l:
break
for y, x in l:
grid[y][x] = 0
gravity(grid, y, x)
cnt = 0
for i in range(7):
for j in range(7):
if grid[i][j]:
cnt += 1
ans = min(ans, cnt)
print(ans)get_disappear_list 함수 내에서만 사용하는 check 함수만 새로 생겼을 뿐, 나머지는 똑같다.
check(line) 에는 한 행이나 한 열이 들어온다.
def check(line):
ret = []
left = 0
while left < 7:
if not line[left]:
left += 1
continue
right = left+1
while right < 7 and line[right]:
right += 1 # 이제 line[left:right]에는 연속 수 리스트가 들어있음
cnt = right - left
i = left
while i < right:
if line[i] == cnt:
ret.append(i)
i += 1
left = right
return ret이렇게 짰는데도 틀려서 여러 가지 임시 테스트케이스를 만들어서 디버깅을 해보았다.
그 결과,
l = get_disappear_list(grid)
if not l:
break
for y, x in l:
grid[y][x] = 0
gravity(grid, y, x)이 부분이 문제라는 것을 깨달았다.
사라지는 (y, x) 점 리스트를 없앨 때 위에 있는 점부터 차근차근 없애야 되는데,
아래 점부터 없애버리면 위에 있던 사라지는 점의 위치가 변동하는 오류가 발생한다.
따라서 리스트를 순회하기 전에 l.sort()를 해주면 맞았습니다를 받을 수 있다.
C. 수들의 합 8
푸는데 가장 시간이 오래 걸렸던 문제다.
정작 코드는 짧다.
풀이부터 소개
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
counter = defaultdict(int)
counter[0] = 1
ans = 0
sA, sB = 0, 0
for nA, nB in zip(A, B):
sA += nA
sB += nB
ans += counter[sA-sB]
counter[sA-sB] += 1
print(ans)sA,sB는 우리가 부분합 문제에서 밥먹듯이 사용하는 Prefix Sum(누적 합) 배열의 각 요소를 나타낸 것 뿐이다. 전체 배열을 저장해둘 필요가 없어서 저렇게 표현했다.- 전체 배열을 저장해 둘 필요가 없었다는 말은 즉슨, 이 알고리즘은
O(n)이라는 뜻이다!
Try #1. 평상시 방법. O(n^2), 시간 초과
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))
for i in range(1, N+1):
A[i] += A[i-1]
B[i] += B[i-1]
ans = 0
for i in range(N+1):
for j in range(i+1, N+1):
if A[j] - A[i] == B[j] - B[i]:
ans += 1
print(ans)코드가 이보다 편안할 수 없다.
하지만 C번 문제를 이렇게 내서 맞을리가 없었다.
구간 합에서 세그먼트 트리를 활용하기도 하지만, 배열의 갱신이 없는 이번 문제에서는 큰 소용이 없었다.
sum(A[i:j+1]) == sum(B[i:j+1]) 인 경우의 수를 구하는 데 어떻게 O(n^2)을 안 쓸 수 있단 말인가.
유사문제 : 백준 2015. 수들의 합 4
도저히 안 풀려서 비슷한 문제를 찾기 시작했다.
이 문제가 수들의 합 시리즈 중 알고리즘 분류가 같아서 풀어보았는데, 잘 얻어걸렸다.
문제의 내용은 다음과 같다.
N과 A[1], A[2], ..., A[N]이 주어졌을 때, 부분합 중 합이 K인 것이 몇 개나 있는지를 구하라.
얘도 단순 생각으로는 O(n^2)이어야만 풀리는 문제다.
풀이는 다음과 같다. (이 링크의 풀이를 가독성 있게 변경했다.)
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
A = list(map(int, input().split()))
counter = defaultdict(int)
counter[0] = 1 # s = K일 때, ans += 1
ans = 0
s = 0
for n in A:
s += n
ans += counter[s-K]
counter[s] += 1
print(ans)와! O(n^2) 문제를 O(n) 으로 풀었다!
(Python 딕셔너리는 해시 테이블이라서 탐색이 O(1)에 진행된다.)
이왜진?
예제 입출력을 돌려보면서 함께 작동원리를 이해해보자.
예제 입력
6 5
1 2 3 4 5 0
예제 출력
32+3, 5, 5+0으로 총 3개다.
임의의 a, b에 대하여 부분합 [a,b] 는 부분합 [0, b] - 부분합 [0, a-1] 의 문제로 환원할 수 있다.
💡 중요한 알고리즘입니다! 집중해주세요
b를 돌면서, b보다 작은 a에 대하여 부분합 [a, b]를 검사하는데,
부분합 [0, a-1]를 일일이 순회할 필요 없이,
b로 거쳐갈 때마다 counter[s]를 1 더해줌으로써 O(1)에 끝내버리는 것이다!
나중에 부분합이 K인 걸 찾고 싶다면,
counter[s-K] 연산 한 번으로 몇 개의 경우의 수가 나오는지 알아낼 수 있다.
왜냐하면…
부분합 [0, b] - 부분합 [0, a-1] = K 는 부분합 [0, b] - K = 부분합 [0, a-1] 와 동치다.
부분합 [0, b] 는 s에 대응되며, b보다 작은 a에 대하여 나올 수 있는 모든 부분합 [0, a-1]의 경우의 수는 counter[s-K] 에 대응된다!!!
그래서 된다.
본 문제로 돌아와서…
# 유사 문제
s = 0
for n in A:
s += n
ans += counter[s-K]
counter[s] += 1
# 본 문제
sA, sB = 0, 0
for nA, nB in zip(A, B):
sA += nA
sB += nB
ans += counter[sA-sB]
counter[sA-sB] += 1유사 문제와 본 문제를 diff 해보았다.
구현 시에 가장 생각해내기 힘들었던 부분이 바로 맨 아래 두 줄이었다.
ans += counter[sA-sB]
counter[sA-sB] += 1- sA와 sB는 각각 배열 A, B의
부분합 [0, b]를 나타내므로 꼭 같을 필요 없다. - 다만, 같은 sA-sB의 값이 과거 배열 A, B의
부분합 [0, a-1]에서도 나온 적이 있어야
그 둘을 뺀A의 부분합 [a, b]와B의 부분합 [a, b]가 같다는 결과가 도출된다.
예를 들어, 과거 sA가 4, sB가 11인 적이 있었다고 해보자.
이후 sA가 0, sB가 7인 케이스가 등장한다면,
sA가 4, sB가 11이었던 인덱스를 a-1로 두고 그 사이의 부분합 [a, b]를 계산하면 둘다 4라는 걸 이해할 수 있다.
