같이 웹 프론트 스터디를 진행 중인 채원이랑 스터디 개인 발표를 끝내고 진도 체크를 한 뒤 같이 스ㅡ근하게 한문제 풀었다.
채원이는 꽤 쉽게(?) 해결했고 머리 쥐어뜯고 있는 나를 도와줬다. 끝까지 이해시키려..1시간? 정도 고군분투했는데 정말 너무 진심으로 고마웠다.
티어를 최대한 신경 안쓰려고 하고 의미도 없다고 생각하지만, 이게 어떻게 실버 2 란 말인가 알 듯 말 듯 모르겠고 맞을 듯 틀릴 듯 틀리는게 너무 빡쳐서 또 맥북을 뿌술 뻔 했다. 문제를 보자마자 했던 내 생각들 썼다 지웠다를 몇 번이고 반복한 코드의 결과물, 마지막 깔끔한 정답 코드까지 여기에 기록해둔다.
답지 보고 안풀고 채원이가 가르쳐준대로 이해하려고 하고 내 걸로 만들고자 최대한으로 노력했다. 상상을 초월할 정도의 삽질하는 시간이 문젠데... 오히려 이렇게 하니 다시 문제를 보고 풀이를 이해했을 때 더 이해가 잘되는? 느낌을 받았다. 속이 좀 후련했다. 맨손으로 땅 파다가 나중에 삽 하나 던져주는 기분이었다.
먼 훗날, 알고리즘이 더 이상 무섭지 않게 될 그 날, 웃으면서 재미로 알고리즘 문제를 풀 수 있는 그 날, 이걸 보고 웃을 수 있었으면 좋겠다.
예를 들어 3을 입력 받는다. 그럼 1 - 2 - 3 의 순서로(3이 제일 밑에) 스택처럼 쌓여있고 이를 그 순서 그대로 세 번째 라인에 옮기면 된다. 파이썬은 스택 자료구조가 따로 없으니 list(배열)로 풀이한다. 처음엔 다소 쉽게 풀릴거라 생각했다.
처음의 접근 방식은 그냥 배열 3개 만들어서 정해진 규칙에 따라 원소를 추가 삭제 하면 될거라 생각했다.
N = int(input())
list1 = []
list2 = []
list3 = []
def FuncA(startList, endList, tempList):
lastVal = startList[-1]
startList.pop()
endList.append(lastVal)
# 1->3
lastVal = startList[-1]
startList.pop()
tempList.append(lastVal)
# 1->2
lastVal = endList[-1]
endList.pop()
tempList.append(lastVal)
# 3->2
lastVal = startList[-1]
startList.pop()
endList.append(lastVal)
# 1->3
lastVal = tempList[-1]
tempList.pop()
startList.append(lastVal)
# 2->1
lastVal = tempList[-1]
tempList.pop()
endList.append(lastVal)
# 2->3
lastVal = startList[-1]
startList.pop()
endList.append(lastVal)
# 1->3
def FuncB():
lastVal = list1[-1]
list1.pop()
list3.append(lastVal)
# 1->3
def startFunc(N):
for i in range(N, 0, -1):
list1.append(i)
# print(list1)
def printFunc():
print("list1 = ", list1)
print("list2 = ", list2)
print("list3 = ", list3)
startFunc(N)
# FuncA()
FuncA(list1, list2, list3)
# 1->2
FuncB(list1, list3, list2)
# 1->3
FuncA(list2, list3, list1)
# 2->3
printFunc()
# FuncB()
# FuncA()
# printFunc()처음엔 대략 이런 생각을 했다.
"그냥 배열 3개 만든 다음에 기본 값 넣어주고 순서대로 원소 들어가고 나가고 하는거 보면 안되나?"
그래서 직접 그려봤는데, 바로 그 때 어느 정도 감? 틀?이 잡혔다. 재귀로 타고 타고 들어간다는 걸 이 때 알았다. (이게 시작한지 한 30분..?이 됐을 무렵....)
문제 풀 때 썼던 이면지이다. 나름의 내 생각이 정리되어있다. 지금 보면 눈물이 쏟아질 거 같다. 얼마나 많은 시간을 부어가며 삽질을 했단 말인가.....
여담이지만 패드가 없어서 정말 너무 아쉽고 서럽다. 지금은 학부과정도 그렇게 빡세지 않아서 평소엔 필요성을 잘 못느꼈는데 (종이에 필기하는게 오히려 더 편하기도 했다) 알고리즘 공부를 시작하니 아이패드의 필요성이 너무나 와닿고 있기만 하면 여기저기 잘 쓰일 것만 같은? 잘 쓸 수 있을 것 같은...
결론 : 아이패드 없어서 알고리즘 실력이 빨리 안느는 듯
현재 서지원은 카카오뱅크의 비상금 대출을 진지하게 알아보는 중이다.
전체적인 큰 틀은 다음과 같다.
- 5개를 옮겨야 한다고 가정했을 때 1번 칸에 있는 5개 중에서 위의 4개(1,2,3,4)를 2번 칸에다가 옮겨야 한다.
이때 상황을 그려보면 list1 = [5], list2 = [4,3,2,1], list3 = []
그리고 1번 칸의 젤 밑에 있던 5를 3번 칸으로 옮긴다.
list1 = [], list2 = [4,3,2,1], list3 = [5]
그러고나서 젤 마지막으로 2번 칸으로 옮겨뒀던 4개를 3번 칸으로 옮긴다.
list1 = [], list2 = [], list3 = [5,4,3,2,1]
그럼 최종 답이 완성이 된다. - 하지만 이 때 핵심은 4개를 2번 칸으로 옮기는 과정이다. 이것도 1번과 마찬가지로(4개가 아닌 3개라고 생각하면 된다) 3개를 다른 곳에 옮겨두고? 나머지 한개를 도착지에다가 옮기고 옮겨뒀던 3개를 다시 옮긴다.
이 두 과정이 핵심이다. 나는 이걸 A함수와 B함수라고 생각하고 계속 문제를 풀었다.
A 함수 : 여러 개짜리 묶음을 옮겨두는 함수
B 함수 : 1개짜리 밑 바닥 옮기는 함수
입력이 4일 때, 5일 때, 6일 때 등을 예시로 생각해보면 전체적인 흐름이 이해가 갈 것이다.
이걸 조금 더 예쁘게? 포장해보면
입력이 5라고 가정했을 때 우리가 해야 할 가장 최종적인 목표는 첫 번째 칸에 있는 5개를 세 번째 칸으로 다 옮기는 작업이고
이 때 4개를 먼저 두 번째 칸으로 옮기고 나머지 1개를 세 번째 칸으로 옮기고 마지막으로 4개를 다시 세 번째 칸으로 옮기는 작업
이렇게 A - B - A 의 작업이 재귀적으로? 계속 연속해서 안으로 파고 들며 개수가 줄어들어가는 방식인 것이다.
아주 조금 더 젠틀하게 표현을 해보면 입력이 5인 상황, 제일 처음 시작할 때의 상황에서 출발점이 start = 1 이고 목적지가 end = 3 이고 나머지 배열이 temp = 2 인 것이다.
채원이의 도움을 받아 이해를 완전히 했을 무렵의 코드를 살짝 보면
# N = int(input())
# list1 = []
# list2 = []
# list3 = []
def FuncA(start, end, temp, N):
# if N == 1000:
# startList = list1
# endList = list3
# tempList = list2
# lastVal = startList[-1]
# startList.pop()
# endList.append(lastVal)
# print("1 3")
# # 1->3
# lastVal = startList[-1]
# startList.pop()
# tempList.append(lastVal)
# print("1 2")
# # 1->2
# lastVal = endList[-1]
# endList.pop()
# tempList.append(lastVal)
# print("3 2")
# # 3->2
# lastVal = startList[-1]
# startList.pop()
# endList.append(lastVal)
# print("1 3")
# # 1->3
# lastVal = tempList[-1]
# tempList.pop()
# startList.append(lastVal)
# print("2 1")
# # 2->1
# lastVal = tempList[-1]
# tempList.pop()
# endList.append(lastVal)
# print("2 3")
# # 2->3
# lastVal = startList[-1]
# startList.pop()
# endList.append(lastVal)
# print("1 3")
# # 1->3
if N == 1:
print("1 3")
elif N == 2:
print("1 2")
print("1 3")
print("2 3")
elif N == 3:
print(start, end)
print(start, temp)
print(end, temp)
print(start, end)
print(temp, start)
print(temp, end)
print(start, end)
else:
FuncA(start, temp, end, N-1)
# 무조건 end(3)이 아닌 쪽으로 옮겨놔야 해
FuncB(start, end)
# print(start, end)
FuncA(temp, end, start, N-1)
# calFunc(N-1)
# startList = list1
# endList = list2
# tempList = list3
# # if startPoint == 1:
# # startList = list1
# # if endPoint == 2:
# # endList == list2
# # if tempPoint == 3:
# # tempList = list3
# lastVal = startList[-1]
# startList.pop()
# endList.append(lastVal)
# # 1->3
# lastVal = startList[-1]
# startList.pop()
# tempList.append(lastVal)
# # 1->2
# lastVal = endList[-1]
# endList.pop()
# tempList.append(lastVal)
# # 3->2
# lastVal = startList[-1]
# startList.pop()
# endList.append(lastVal)
# # 1->3
# lastVal = tempList[-1]
# tempList.pop()
# startList.append(lastVal)
# # 2->1
# lastVal = tempList[-1]
# tempList.pop()
# endList.append(lastVal)
# # 2->3
# lastVal = startList[-1]
# startList.pop()
# endList.append(lastVal)
def FuncB(start, end):
# lastVal = list1[-1]
# list1.pop()
# list3.append(lastVal)
print(start, end)
# def startFunc(N):
# for i in range(N, 0, -1):
# list1.append(i)
# def printFunc():
# print("list1 = ", list1)
# print("list2 = ", list2)
# print("list3 = ", list3)
# startFunc(N)
N = int(input())
print((1 << N)-1)
# print(2**N-1)
if N<=20 :
FuncA(1, 3, 2, N)
# 시작할 때만 무조건 1에서 3으로 옮기는 게 목표
# 안으로 들어가서는 계속 달라진다.마지막 줄의 FuncA를 보면 1, 3, 2, N 으로 고정이다. 이게 바로 우리가 해야할 궁극적인 목적이 첫 번째 칸에 있는걸 세 번째 칸으로 다 옮겨야 한다는 것을 의미한다. (start = 1, end = 3)
그리고 문제를 제대로 안읽은건지 푸는 방법을 몰랐던 건지 배열을 만들어서 하나하나 원소의 이동을 볼 필요가 없다. 출력은 어디서 어디로 이동하는지만 알면 되기 때문에 굳이 원소를 하나하나 옮겨가며 시뮬레이팅 해보지 않아도 되는 것이다.
A - B - A 에서 처음 나오는 FuncA는 목적지가 아닌 다른 한 곳(=temp)로 가는 것이므로 start에서 temp로, FuncB 함수는 출발점에서 목적지로 가기 위해 무조건 start 에서 end로, 마지막으로 temp에 있는 나머지? 것 들을 목적지로 다 옮겨주면 되므로 temp에서 end로
이렇게 함수만 짜주고 프린트만 찍어주면 엄청나게 간단하게 해결된다.
총 몇번의 이동이 있는지도 출력해야 하는데 이는 전역 변수로 cnt를 놔두고 이동마다 세어줘도 되고, 채원이가 가르쳐 준것 처럼 2^N - 1 로 계산해도 된다.
진짜 졸라 어려웠는데 그만큼 뿌듯했다. 그래도.. 매일 매일 이렇게 삽질 하는건 시간이 너무 아ㄲㅏㅂ...가 아니고 시간이 너무 부족하다. 리액트랑 자스랑.. 졸과 해야지 빨리..ㅠ
