728x90
코테로 나온 4문제는 다풀었고, 보통 내가 풀려고 했던 문제까지 완성해서 제출하면 보통 후기를 쓰지 않지만 이번 4번 문제는 좀 획기적인 알고리즘 방법을 복습하고자 후기를 써본다.
문제는 이렇다.
자연수 n이 주어질 때 자연수 n을 만들 수 있는 합의 값은 여러가지가 있다.
n = 8일경우, 1+1+1+1+1+1+1+1, 2+1+1+1+1+1+1,... 등 많다.
이 자연수 n을 합의 종류를 만들고 그이후 여러가지 과정을 거치지만 그부분은 스킵하고 자연수 n만들기만 설명해보려고 합니다. 애초에 유명한 알고리즘이 있습니다.
# 풀이 절차 과정(함수 makePlusNums에 대한 설명)
1. 맨 처음 하나의 수를 리스트에 넣음.
2. 스택에 수를 꺼내면서 꺼낸 수 x가 1이 아니면 x-1를 스택에 넣음
2-1. 만약 x가 1이라면 스택에 1이 아닌 값이 나올때까지 계속 꺼내면서 (꺼낸 수들 1들의 합은 저장) 그러다가 1이 아닌수가 나오면 1이 아닌수를 y-1을 저장하고, 지금까지 합친 1의 합을 다시 리스트에 넣는다
3. 이를 모든 리스트들이 1로만 이루어질때까지 반복합니다.
이 풀이 과정의 근본적인 원리는 무엇일까요?
자연수 n = 8이 들어올때 값을 꺼내면서 -1을 해주면서 쪼개면서 합들의 합을 구하는 방식입니다.
개인적으로 풀이 절차 과정을 보시고 코드를 보신다음 이 코드 부분은 왜있는거지 라는 의문이 들면 그림을 참고해보시는 것을 추천드립니다.
def makePlusNums(n):
number = [n]
ans = []
while True:
ans.append(number.copy())
tmp = number.pop()
if tmp != 1:
number.append(tmp - 1)
number.append(1)
else:
base = 2
for _ in range(len(number)):
if number and number[-1] == 1:
base += 1
number.pop()
if not number:
break
pivot = number.pop() - 1
number.append(pivot)
while base > pivot:
number.append(pivot)
base -= pivot
number.append(base)
return ans
n = 5
print(makePlusNums(n))
# [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
후기
재밌는 알고리즘 풀이를 알게되서 재밌었다.
728x90
'Test' 카테고리의 다른 글
sql문제를 코테에서 처음 풀이 성공함 (0) | 2022.07.03 |
---|---|
dev matching - skt 텔레콤 코테 후기 (0) | 2022.06.14 |
코테 후기 -2, 3 번 후기 (0) | 2022.05.31 |
22년도 어떤 시험 코테 - 2번째 문제 2차 후기 (0) | 2022.05.30 |
22년도 어떤 인턴 코테 시험 - 2번째 문제 후기 (0) | 2022.05.28 |