자.. 지금이 무슨 상황인고 하니, 자교 알고리즘 경진대회에 참여 후, 약 2시간이 지나지 않은 시점에서 쓰는 후기이다.
이번이 첫 오프라인 대회 참석이라 가벼운 마음으로 대회에 참여했다.
그런데 웬걸?! 문제가 이전 대회 기출보다 굉장히 쉽게 나와 풀만 했다.
결과적으로 2등을 했다!
그래서 커피와 에너지 음료에 절여져 흥분되어 있는 이 기분 좋은 여운이 가시기 전에 빠르게 후기를 작성하고자 오랜만에 도서관에 와 노트북을 켰다.
문제 등급별 분포
문제는 9문제가 나왔고 각 등급별 분포는 다음과 같았다
| 등급 | 개수 |
| A | 1문제 |
| B | 3문제 |
| C | 3문제 |
| D | 2문제 |
등급별로 문제 난이도가 올라가고, 등급 내 문제 난이도는 순서와 상관 없다.
(ex) B1은 A1보다 확실히 어렵다, 그러나 B2가 B1보다 어렵다는 보장은 없다)
나는 9문제 중 D1을 제외하고 8문제에서 AC를 받았다.
각 문제별 주관적인 체감 난이도
| 등급 | 문제 이름 | 체감 난이도 |
| A1 | 울타리 공사 | 브3 |
| B1 | 현권이와 신기한 수열 | 브1 |
| B2 | 새치기 | 실5 |
| B3 | 조커 찾기2 | 실5 |
| C1 | 컵 쌓기 | 실3 |
| C2 | 통신 시스템 성능 저하 | 골4 |
| C3 | 에어드롭 | 골5 |
| D1 | 용액2 | - |
| D2 | 이분탐색의 흔적 | 골3-4 |
문제 풀이
A1 : 울타리 공사
최소, 최대 x와 최소, 최대 y값을 기록하면서 둘레를 구하면 되는 문제다.
개인적으로 비슷한 브론즈 문제를 풀어봐서 큰 무리 없었다.
>> 풀이보기
import sys
input = lambda: sys.stdin.readline().strip('\n')
n= int(input())
minX= sys.maxsize
maxX = -sys.maxsize
minY = sys.maxsize
maxY = -sys.maxsize
for _ in range(n):
x1,y1,x2,y2 = map(int, input().split())
minX = min(minX, x1)
maxX= max(maxX, x1)
minY = min(minY, y1)
maxY = max(maxY, y1)
minX = min(minX, x2)
maxX = max(maxX, x2)
minY = min(minY, y2)
maxY = max(maxY, y2)
print((maxX-minX)*2 + (maxY- minY)*2)
B1 : 현권이와 신기한 수열
i-1차 항과 i항 간의 관계를 규정한 문제다. 단순 구현 문제라 크게 어려운 점이 없었다.
시간 복잡도를 줄이기 위해 이전에 나온 숫자들을 사전에 메모제이션 하는 것이 특징이다.
왜인지 모르겠는데 사소한 부분에서 계속 틀려 3트만에 성공했다.
이 때 몬스터 깠던 것 같다.
>> 풀이보기
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().strip('\n')
n = int(input())
check = defaultdict(int)
nums = [0]*(n+1)
check[0]=1
for i in range(1, n+1):
if(nums[i-1]- i <0 or check[nums[i-1]-i] ==1):
nums[i] = nums[i-1]+i
check[nums[i]] =1
continue
nums[i] = nums[i-1]-i
check[nums[i]] = 1
print(nums[n])
B2 : 새치기
애드 혹적인 사고가 필요하다.
만약 이전까지 최대 만족도를 dp[i-1]이라 가정하자
i번째 사람은 두가지 선택권이 있다.
첫째로 뒤에 서는 경우다.
이 경우에는 i번째 사람의 만족도는 0이 되어
dp[i] = dp[i-1]이 된다.
둘째로 앞에 서는 경우다
이 경우에는 기존 사람들을 모두 새치기 하게 된다.
i번째 사람의 만족도는 S(i)를 그대로 받게 된다.
그러나, 새치를 당한 이전까지 사람들의 만족도를 모두 합한 값인 total만큼 만족도가 차감된다.
즉, dp[i] = S(i) - total이 성립한다.
이를 가지고 매 순간에 관계식을 세워본다면
dp[i] = max(dp[i-1], s(i) -total) 이 된다.
사람의 수 만큼인 O(n)으로 답을 구할 수 있다.
>> 풀이 보기
import sys
input = lambda: sys.stdin.readline().strip('\n')
n= int(input())
s= [0] + list(map(int, input().split()))
dp=[0]*(n+1)
total=0
for i in range(1, n+1):
dp[i]= max(dp[i-1], s[i]-total)
total+=s[i]
print(dp[n])
B3 : 조커 찾기 2
시뮬레이션과 mod 연산이 키였던 문제였다.
처음에는 덱의 상태를 모두 저장해놓으려 했는데 메모리 초과가 우려되었다.
그래서 조커의 위치만을 turn이라는 dict에 저장해놓는 것으로 메모리를 아꼈다.
1번 동작은 조커의 위치를 i번 미루는 동작이다. (조커의 위치+=i)
2번 동작은 조커의 위치를 i번 앞으로 당기는 동작이다 (조커의 위치 -=i)
3번 동작은 turn[i] 번째의 조커의 위치로 초기화하는 동작이다. (조커의 위치 = i번째 턴의 조커의 위치)
이 때, 덱은 원형 큐 처럼 작동한다.
1번째에 조커가 있을 때 카드를 한장 앞으로 당기면 n번째로 이동하며
n번째에 조커가 있을 때 카드를 한장 뒤로 밀면 1번째로 이동한다.
이 작업을 mod 연산으로 구현가능하다
>> 문제풀이
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().strip('\n')
#덱에서 조커의 위치
n,m= map(int, input().split())
turn = defaultdict(int)
turn[0] = 1
def func(op, k, i):
if(op==1):
return (k+i)%n
if(op==2):
if(k-i<=0):
return n-(abs(k-i)%n)
return (k-i)
if(op==3):
return turn[i]
for i in range(1, m+1):
op, j= map(int, input().split())
turn[i] = func(op, turn[i-1], j)
#print(turn[i])
print(turn[m])
C1 : 컵 쌓기
문제를 보자마자 dp문제임을 직감했다.
처음에는 직관적으로 O(n^2)로 풀이를 작성했다.
그런데 TLE가 떠서 다른 방법을 모색했다.
그래서 찾은 방법이 컵의 높이별 순회이다.
먼저 높이별로 컵의 개수를 체크해준다.
즉 heights 배열이 [0,2,3] 이면
컵의 높이가 1인 컵은 2개, 컵의 높이가 2인 컵은 3개로 해석할 수 있다.
이제 높이가 i인 경우의 수 dp[i]를 계산해보자.
만약 컵의 높이가 3이라면
dp[i] = dp[i-3](3보다 작을 때의 경우의 수) * heights[3](높이가 3인 컵의 개수)이 된다.
이를 일반화 시켜본다면 컵의 높이가 ch일 때
dp[i] = dp[i-ch] * heights[ch] 로 정리된다.
이를 각 컵의 높이마다 순회하며 높이가 i일 때의 경우의 수 dp[i]를 구해주면 된다.
>> 문제 풀이
from collections import defaultdict
height =defaultdict(int)
n,h = map(int, input().split())
dp=[0]*(h+1)
cups = list(map(int, input().split()))
dp[0]=1
for c in cups:
height[c]+=1
for i in range(1, h+1):
temp=0
for ch in height.keys():
if i-ch <0:
continue
temp+= dp[i-ch] *height[ch]
dp[i] = temp%1000000007
#print(dp)
print(dp[h])
C2 : 통신 시스템 성능 저하
당시 대회장에서 유일하게 나만 풀었던 문제라 애정이 간다.
백트래킹 + 브루트 포스 문제였다.
그래프 문제를 많이 푼 효과가 나타났던 것 같다.
+) 파이썬의 combinations 라이브러리 때문에 나는 백트래킹을 할 필요가 없었음
또, 비슷한 아이디어의 문제인 연구소가 떠올라 2트만에 풀 수 있었다.
그런데 경진대회 이후 출제자의 출제 의도를 보니 낮에 활성화하는 node의 개수 k가 많기 때문에 활성되지 않는 n-k를 고르는 식으로 경우의 수를 줄이는 걸 의도했다고 말하셨다. 나는 라이브러리의 힘으로 간신히 시간복잡도를 통과한 행운아였다는 걸 뒤늦게 깨달았다.
내가 푼 풀이는 다음과 같다.
1. 활성화 가능한 node 들의 모든 경우의 수를 조합으로 찾아낸다.
2. 케이스별로 node를 활성화시키고 [기지국과의 거리합]과 [활성 노드를 포괄하는 최대 직사각형 넓이]를 찾아낸다.
3. 각 케이스 마다 나온 [기지국과의 거리 합] - [활성 노드 포괄 사각형 넓이]의 최대값을 구한다.
어쩌면 백트래킹 + 브루트 포스를 파이썬 라이브러리로 빠르게 구현해내서 당시 많은 참가자들이 힘들어하는 문제를 쉽게 대했던 것은 아닌가 싶다.
>> 문제 풀이
import sys
from itertools import combinations
def find_case(k):
if(k==0):
return 0
cases = list(combinations(indexs, k))
result = 0
for c in cases:
temp = [nodes[i] for i in c]
d=0
for node in temp:
d += distance(gijiguk, node)
u = square(temp)
result = max(result, d-u)
return result
def square(nodes):
minX = sys.maxsize
maxX = -sys.maxsize
minY = sys.maxsize
maxY = -sys.maxsize
for x,y in nodes:
minX = min(minX, x)
maxX = max(maxX, x)
minY = min(minY, y)
maxY = max(maxY, y)
return (maxX- minX+1)*(maxY-minY+1)
#거리 구하기
def distance(node1, node2):
return abs(node1[0]- node2[0]) + abs(node1[1]- node2[1])
n,m, k1, k2 = map(int, input().split())
data = [list(input()) for _ in range(n)]
gijiguk = -1 #기지국
nodes =[] # 노드들
for i in range(n):
for j in range(n):
if data[i][j] =="B":
gijiguk = (i,j)
if(data[i][j] =="N"):
nodes.append((i,j))
indexs = [i for i in range(m)]
print(find_case(k1))
print(find_case(k2))
C3 : 에어 드롭
유클리드 거리가 뭔지 몰라서 1트를 실패했다. 알고보니 그냥 우리가 수1때 배웠던 두 점 간의 거리 공식 이었음..
출제자는 union-find를 의도했다고 하지만 단순 bfs 방문 여부로도 풀 수 있었다.
1. 푸앙이를 시작으로 탐색가능한 친구들을 방문처리 한다.
- 이 때 이미 방문한 친구거나, 조건(버전 차이 / 거리차이)에 맞지 않는다면 건너 뛴다
2. 방문한 친구들 중 푸앙이와 사진을 찍었는지 확인해 답을 구한다.
>> 문제 풀이
import sys
import math
from collections import deque
from collections import defaultdict
input = lambda: sys.stdin.readline().strip('\n')
def distance(x1,y1, x2, y2):
return math.sqrt(abs(x1-x2) **2 + abs(y1-y2)**2)
take = defaultdict(int)
#친구의 수, 에어드롭의 최대 거리, 최대 휴대폰 버전 차이
n,k,t = map(int, input().split())
px,py, pv = map(int, input().split())
visited = [0]*(n)
friends = []
for i in range(n):
f = list(map(int, input().split()))
#사진 찍음
if(f[-1]==1):
take[i]=1
friends.append(f)
q=deque([(px, py, pv)])
while(q):
nx, ny, nv = q.popleft()
for i, f_node in enumerate(friends):
fx,fy,fv, ft= f_node
if (fx==nx and fy==ny) or visited[i]==1:
continue
if(distance(nx, ny, fx, fy) <=k and abs(nv-fv)<=t):
visited[i]=1
q.append((fx,fy,fv))
result=[]
for i in range(n):
if(visited[i]==1 and take[i]==1):
result.append(i+1)
if(len(result)==0):
print(0)
else:
print(*result)
D1 : 용액 2
이 문제를 처음 본 게 마감 24분 전이라 끝내 풀지 못했다.
집에 와서 다시 풀어보았는데도 아이디어 떠올리는 게 왜이리 힘든지... TLE를 받았다
기본적인 아이디어는 다음과 같다.
- (누적합, 인덱스 값) 형태로 누적값을 저장한다
- 누적합을 기준으로 정렬한다.
- 인접한 두 누적합의 차가 최소가 되는 지점이 답이 된다
여기서 인접한 두 누적합의 차가 최소가 되는 이유는 이미 정렬되어있기 때문에 더 먼 인덱스의 누적합을 고려해봤자 차이가 커지면 커졌지 작아지진 않기 때문이다.
따라서 예시 1번을 보면
4
1 2 -1 -1
# 누적합을 구한다
1 3 2 1
#(누적합, 인덱스)로 정렬한다
(1,1) (1,4) (2,3) (3,2)
# 인접한 누적합 차이 중 절대값이 가장 작은 값을 구한다
1,1 - 1,4=> 1-1 = 0
1,4 - 2,3=> 1-2 = -1
2,3 - 3,2=> 2-3 = -1
따라서 1,4 즉 2부터 4까지 더하는 연속합이 답이 된다.
그런데 여기서 끝인줄 알았는데 아니었다. 그냥 순수 누적합이 답이 될 수도 있다
예를 들어 용액이 2 하나만 있는 경우에는 (누적합 - 인덱스)가 (2,1)로 저장된다.
그럼 2 하나가 답이 된다.
따라서 인접한 누적합의 차이와 각 순수 누적합을 비교하며 result를 갱신시켜줄 필요가 있다.
>> 풀이
n = int(input())
nums = [0] + list(map(int, input().split()))
data=[]
for i in range(1, n+1):
nums[i]+= nums[i-1]
data.append((nums[i], i))
#(누적합 - 인덱스) 배열 정렬
data.sort()
result= data[0][0]
index= [0, data[0][1]]
for i in range(1, n):
left = data[i-1]
right = data[i]
#순수 누적합 data[i]
if abs(right[0]) < abs(result):
result = right[0]
index = [0, right[1]]
#인접한 누적합의 차이가 result 절대값보다 크다면 skip
if abs(right[0]- left[0]) >= abs(result):
continue
# 인접 누적합
if left[1]< right[1]:
result = right[0]- left[0]
index = [left[1], right[1]]
else:
result = left[0] - right[0]
index = [right[1], left[1]]
if result==0:
break
index[0]+=1
print(result)
print(*index)
D2 : 이분 탐색의 흔적
1시간 남짓 남았을 때 D1보다 쉬워보여서 접근해본 문제
단순 수학 문제라 풀만 했다.
먼저 이분탐색의 흔적을 따라 오름 차순으로 정렬된 index를 따라 숫자를 채워준다.
예를 들어 예시1이었던 3숫자 중 첫번째인 50은
x 50 x 으로 숫자를 채울 수 있다.
예시 2에서 5개의 숫자 중 이분탐색의 흔적인 48 21 31의 경우
21 31 48 x x 식으로 숫자를 채울 수 있다.
이제 100개의 숫자에서 해당 범위에 해당하는 경우의 수를 구해주면 된다.
예를 들어 x 50 x 에서
첫번째 x의 경우 50보다 작은 1-49가 들어갈 수 있다.
조합으로 나타내면 49개 중 1개(49 C 1)이다.
두번째 x의 경우 50보다 큰 51-100중 하나가 들어갈 수 있다.
조합으로 나타내면 50개 중 1개 (50 C 1) 이다.
따라서 49*50 = 2450이 나온다.
두번째 예시인 21 31 48 x x의 경우는 어떨까?
48보다 큰 49-100에서 2개의 숫자를 고르면 된다.
조합으로 나타내면 52개 중 2개 (52 C 2)가 된다.
따라서 답은 1326이 된다.
이처럼 각 구간에 알맞는 조합의 개수를 구해 계속 곱해나가면 된다.
예를 들어 다음과 같은 숫자 배열이 있다고 가정하면
x x 4 x x x 70 x x
첫번째 x x 구간은 1-3 중 2개를 고르는 조합이므로 3 C 2 ==> 3가지
두번째 x x x 구간은 5 - 69 중 3개를 고르는 조합이므로 65 C 3 ==> 43680 가지
세번째 xx 구간은 71 - 100 중 2개를 고르는 조합이므로 30 C 2 ==> 435 가지
=> (3 x 43680 x 435) %mod 가 답이 된다.
>> 풀이 보기
import math
import sys
input = lambda: sys.stdin.readline().strip('\n')
n,m= map(int, input().split())
nums= [-1]*(n) #숫자
left =0
right = n-1
#숫자 채우기
bi_nums = list(map(int, input().split()))
#초반 1개의 숫자
mid= (left + right)//2
nums[mid]=bi_nums[0]
before = bi_nums[0]
#뒤의 숫자들 채우기
for b in bi_nums[1:]:
if before <b:
left= mid+1
mid= (left+right)//2
nums[mid]=b
else:
right = mid-1
mid = (left + right) // 2
nums[mid] = b
before =b
s=0
answer = 1
cnt=0
mod = 1000000007
for i in nums:
# 숫자가 없으면 골라야 하는 cnt값 +1
if i==-1:
cnt+=1
continue
# 골라야 하는 조합의 개수가 없다면 더하지 않음
if(cnt!=0):
answer = (answer*math.comb(i-1-s,cnt))%mod
s=i
cnt=0
if(nums[-1]==-1):
answer = (answer*math.comb(100-s,cnt))%mod
print(answer)느낀 점
1. 다시 한번, 알고리즘
우테코에는 알고리즘 탑티어인 사람이 많다. 천상계들을 보며 알고리즘 풀이에 흥미를 잃어가던 찰나, 그래도 적당한 난이도(?)의 알고리즘 대회에 나와 다시한번 의지를 다지게 되었다. open contest를 보니 contest와 달리 문제가 D등급 이외에 E-F까지 있었고 내가 푼 8솔로는 10등권에도 들어가지 못했다. 나는 아직 우물 안 개구리일 뿐이다. 운이 좋아 상을 탄 것이니 자만하지 말자는 다짐도 되새겼다.
또, 지나가다 본 문제 중에서 꽤 생각나는 문제가 많았다. 매일 알고리즘을 풀며 '이걸 푼다고 내 실력이 올라갈까?' 라는 의구심이 들었는데 나름 생활근육이 붙은 것 같아 뿌듯했다. 다만 풀이 중간중간 상기된 문제들의 공통점은 내가 복기하며 고통을 되새김질한 문제들 이었다. 고통스러울지라도 풀이 중간중간에 강한 자극을 남기는 게 얼마나 기억에 오래 남는지 깨달았다.
2. 새롭고 신기한 오프라인 대회 경험
첫 대회다 보니 너무 재미있는게 많았다.
대회가 끝나고 등수를 발표할 때 알고리즘 학회 Chaos 회장님께서 스트릭 프리즈 이후 하나씩 등수 변동을 해설해주셨는데 1시간 전 2등으로 마감했던 나는 혹여나 1등할 수 있을까 쫄깃쫄깃했다. 결과적으로는 1등하신 분과 나 모두 한 문제씩 더 맞추어 순위는 그대로였다.
또 문제를 풀 때마다 깃발을 하나씩 꽂아주시는데 이게 진짜 쾌감이 미쳤다. 다른 참여자 깃발이 꽂힐 때는 초조해지면서도 또 내가 풀때마다 다른 색 깃발을 하나씩 꽂아주셨는데 개인적으로는 하얀색 깃발 꽂힐 때(오프라인 참여자 중 C2를 나만 풀어 유일하게 하얀색 깃발을 받을 수 있었다 ㅎㅎ) 어깨가 올라갔다 ^^
3. 포기하지 않기
솔직한 마음으로 24분이 남았을 때 D1문제를 조금 더 적극적으로 비벼볼걸 이라는 아쉬움이 남는다. 24분 내에 D 난이도를 풀 수 없으리라 생각했고 실패 횟수가 쌓이면 등수에 영향이 갈까 적극적으로 도전해보지 못했다. '과정은 치열하게, 결과는 초연하게'라는 마음가짐에 어울리지 않는 행동을 했다.
만약 다음에도 도전의 기회가 있다면 그 때는 스코어 보드와 무관하게 조금은 더 적극적으로 막판 스퍼트를 올려야 겠다고, 또 쉽게 포기하지 말아야 겠다고 생각했다.
'백준 문풀' 카테고리의 다른 글
| [Python] 7983. 내일 할거야(골5) / 그리디-정렬 (0) | 2024.05.05 |
|---|---|
| [Python] 1082. 방 번호(골3) / 그리디 + DP (0) | 2024.04.01 |
| [Python] 2538. 전구와 스위치 / 그리디 (0) | 2024.03.14 |
| [Python] 2872. 우리집엔 도서관이 있어(실2) / 그리디 (4) | 2024.02.28 |
| [Python] 1783. 병든 나이트(실3) /그리디 (0) | 2024.02.10 |