20230427 시험을 봤는데, 2번 3번 문제만 그나마 풀 수 있었다. 하지만 완성하지는 못했다. 2번 문제는 아파트 단지 묶음이 몇개인지만 셌고, 각 단지내의 칸의 개수 세는 것은 구현 못했다. 3번 문제는 바이러스의 확산이었는데, 여러 종류의 바이러스가 확산하는거라 일단 바이러스1의 확산만 구현했다. 그마저도 1이 확산되고 나서 2차원 리스트가 어떻게 변하는지 확인하는 것이 다이다. 다른 사람의 풀이를 보니 리스트에서 0이 아닌 원소를 추가하더라. DFS와 BFS로 2차원 이상인 리스트에서 원소간 연결 여부를 확인하는 방법을 익히지 못했다는 것을 느꼈다. 같은 값끼리 묶는 방법, 특정한 값 이상인 값끼리 묶는 방법 등 여러가지에 적용해야 할 것이다. 그리고 시험볼 때는 기업 코딩 테스트 볼 때 처럼 ChatGPT 사용은 지양해야겠다. 정확도가 떨어지는 편이지만, 시험 볼 때는 뭐를 보고 할 수 없기 때문이다. 공부할 때만 쓰다가, 아무리 썼다고 해도 단순히 코드가 어떻게 돌아가는지를 넘어서 그렇게 코드를 짜는 방법을 익혀야겠다. 그런데 사실 새 문제 푸느라도 시간이 없다고 느끼는데, 뭔가를 복습할 여유도 없다고 느낀다. 오늘부터 4주차다. 파이썬 알고리즘은 이번 주가 마지막이다. 여태껏 배워온 알고리즘의 정의랑 이론은 잘 이해해왔다고 느끼지만, 아직까지 상황에 따라 다르게 적용하는 방법을 모르겠다. 2주차에도 이진 탐색등에서도 응용이 힘들었는데, DFS, BFS도 응용이 쉽지 않다. 자꾸 솔루션을 보게 되고, ChatGPT의 도움을 받게 된다. 우선은 동적 프로그래밍을 이용하는 쉬운 문제인 피보나치 수와 01 타일 문제를 풀었다. 동적 프로그래밍은 초기 시점의 작은 문제를 먼저 해결한 다음에 그걸 이용해서 더 큰 문제를 푸는 방식이다. 예를 들어 피보나치 수열에서 첫 두 숫자가 0과 1이면 그 이후부터는 뒤의 2 숫자의 합을 더하면서 진행하면서 피보나치 수열을 완성시키면 된다. 01 타일 문제도 마찬가지였다. 패턴을 우선 파악하고 나니 피보나치 수열과 비슷했다. 출력이 옳게 나왔는데도 메모리 초과 문제가 계속 나와 할 수 없이 솔루션을 봤는데, 뜬금없이 15746으로 나눈 나머지를 구하길래 왜 그러나 했다. 그래서 문제를 다시 보니 15746으로 나눈 나머지를 출력하라고 하더라. 그래서 코드를 다시 깔끔하게 정리해서 풀었더니 정답이 나왔다. 이제부턴 문제를 꼼꼼히 읽어야겠다. 탐욕 알고리즘(greedy algorithm) 문제도 풀어봤다. 얼마 만큼의 돈을 화폐 최소 몇개로 나타낼 수 있는지를 알아내는 코드였다. 탐욕 알고리즘에 대해 잘 몰라서 어느 블로그를 찾아보다가 우연히 풀이가 있어 실수로 보고말았다. 주어진 돈 리스트들로 계속 나누면서 몫을 계속 축적하고, 입력 값을 돈으로 나눠서 얻은 나머지로 계속 업데이트 해나가는 된다고 한다. 하지만 처음에는 돈 리스트 중에서 가장 큰 금액부터 나눠야 한다는 것을 모르고 있었다. 이런식으로 머리로는 알고리즘이 짜져도 그것을 코드로 바로 구현하는데에 어려움을 느낀다. 이런것들은 할 수 없이 검색하거나 ChatGPT에 물어보게 된다..
20230428 탐욕 알고리즘을 이용하는 잃어버린 괄호 문제는 난이도가 ‘하’였는데, 아이디어 생각해내는 것이 쉽지 않았다. 식이 주어졌을 때 적당한 위치에 괄호를 삽입해서 결과를 최소로 만드는 문제였다. 예를 들어 ‘55-50+40’을 ‘55-(50+40)’으로 표현하면 ‘55-90=-35’가 나온다. 문자열로 입력된 계산식을 계산하는 함수인 eval()을 이용해보려 했는데, 어떻게 재구성해서 해야할지 정말 고민이었다. 특히 숫자가 0으로 시작하는 것들도 있어서 eval() 함수는 더욱 적용될 수 없었다. 아무리 생각해도 좋은 아이디어가 나지 않아 솔루션을 찾았더니 식을 ‘-’ 마다 분리하면 되는 것이었다. 그 다음에 ‘+’마다 분리한 숫자들을 더해서 얻은 값들과 따로 있던 숫자들을 모두 한 리스트에 담는 것이다. 그러고나면 그 리스트의 가장 첫 번째 숫자를 나머지 숫자들의 합으로 빼면 된다. 탐욕 알고리즘이라는게 현재 상태에서 가능한 최적의 선택지를 고르는 방식이라는데, 도대체 어떤게 최적이라는건지 잘 모르겠다.
20230429 LCS 문제를 풀었는데, 주어진 두 수열에서 모두의 부분 수열디 되는 수열 중 가장 긴 것을 찾는 문제였다. 처음에는 주어진 예제에서 첫 번째 수열의 각 원소를 그 인덱스에서 시작해서 두 번째 수열에서 찾는 방식을 택했다. 이 기능을 겨우 만들어냈다고 생각했는데, 막상 백준에 채점을 받아보니 오답이 나왔다. 다른 예제에 대해서는 다르게 적용되나보다. 그래서 결국 솔루션을 찾았더니 완전히 다른 방식으로 접근하고 있었다. 동적 프로그래밍으로 접근해야 하는건지, 이차원 리스트를 만들어서 진행을 하더라. 정말 생소한 접근 방식이다. 신입 사원 문제를 풀면서 손으로 풀 때는 어떻게 풀면 될지 알 수 있었다. 어느 지원자의 성적이 다른 직원의 성적보다 서류에서도 낮고, 면접에서도 낮으면 탈락 시키는 방식인데, 손으로 찾아내는건 쉽다. 하지만 이걸 코드로 표현하는 방법을 알 수 없었다. 어떻게 정렬해야 할지도 몰랐다. 동적 프로그래밍도 아니라 서로의 순위를 비교하는 표를 만들었는데도 조건을 만족시키지 못했다. 그래서 찾아봤더니 이런 방법을 제안하더라. 우선 서류 순위로 정렬한 다음에 면접 순위 기준으로 정리할 때 최소 알고리즘(minimum algorithm)이란 것을 이용하고 있었다. 다음과 같이 표현할 수 있다.
my_list = [3, 7, 1, 9, 2, 5]
min_val = float('inf')
for val in my_list:
if val < min_val:
min_val = val
print(min_val) # Output: 1
최소값을 저장할 변수에 무한대 값을 저장한 뒤, 리스트 원소와 비교했을 때 변수 값보다 작으면 그 원소 값을 변수에 저장한다. 그 다음에 다른 원소들과 비교하면서 더 작은 숫자를 입력하면서 최소값을 얻는다.
20230502 오늘 아침에는 ChatGPT의 도움을 받고 작성한 멀티탭 문제의 코드 과정과 개념을 이애하는데 시간을 보냈다. 이를 충분히 마치고 점프 문제로 넘어갔다. 점프 문제를 풀다가 예제 입력에 대해 정답을 얻는 방식을 손으로는 풀 수 있었다. 하지만 어떻게 최소 6번 점프해서 19번째 돌로 갈 수 있었는지 그 횟수에 맞춰 경우를 알아본거라 그것을 찾는 과정을 알아낸 것은 아니다. 따라서 동적 프로그래밍을 여기에 어떻게 적용해야 하는지도 막막해서 풀이를 볼 수 밖에 없었다. 나도 생각지도 못한 접근법이고, 동적 프로그래밍 또한 상황마다 어떻게 다르게 적용해야 하는지 아직도 모르겠다. 문제에서의 목적이 i번째 돌에 v만큼의 속도로 도착해야 하기 때문에 i-v 번째 돌에서 속도 v로 출발한다. 게다가 i위치에 따라 v 속도의 최대 값이 달라지는데, 너무 큰 숫자까지 찾는 경우를 방지하기 위해 등차수열의 합 공식을 이용해야 한다고 한다. 그리고 점프하기 전에 이전 돌의 점프 횟수를 기록해야 하므로 이차원 리스트를 만들어야 한다고 한다. 행은 돌의 위치, 열은 속도로 두고 말이다. 상상하지도 못한 것이다.
n(2a + (n-1)d)/2 여기서 a는 첫째항이므로 1이 되고, d는 공차(common difference)인데, 연속한 두 항에서 뒤 항에서 앞 항을 뺀 값이라고 한다. 1부터 N까지 1만큼 늘어나므로 여기서는 d값이 1이 된다. 따라서 아래와 같이 표현할 수 있다. n(2 + (n-1))/2 = n(n+1)/2 이 문제에서는 i위치에 가기 위한 최대의 v값을 결정해야 하기 때문에 n을 v로 표현하고, 최종식은 아래처럼 표현하면 된다고 한다. i = v(v+1)/2 = ((v^2) + v) / 2 → 2i = (v^2) + v 여기서 속도 중심으로 보기 위해 다음과 같이 표현하면 된다고 한다. v^2 = 2i - v → v = (2i - v)^0.5 더 간략하게 “v=(2i)^0.5”로 표현 가능하다고 하고, 속도의 범위를 1에서 (2i)^0.5 사이로 설정하면 된다고 한다. 이렇게 속도 v의 범위 설정과 점프한 기록을 이차원 배열로 설정해야 한다는 점을 생각해야 하는데에서 많이 힘들었다. 이 문제도 풀이 보고 직접 타이핑하면서 제출했다.
그런데 이 문제를 다룬 어느 블로그를 읽다가 마음에 와닿는 내용이 있었다. 작성자 본인이 글만 보면 정말 쉽게 풀었다는 생각이 들 수 있는데, 사실 문제를 풀면서는 자신이 생각한 풀이가 맞는지, 실수는 없는지 불확실해서 점점 산으로 가기도 하고, 생각이 혼란스러워 지기도 했다고 한다. 그리고 그 분 말고다 다른 블로거들도 시간을 길게 투자하고 작성했었을 수도 있다고 하였고, 난 오ㅙ 안될까 고민하느라 시간 낭비하지 말고 그냥 공부하면 된다고 한다. 전 주차에서도 느꼈지만 생소하고 익숙하지 않아 알고보면 잘 안풀리는게 당연한거다. 우린 천재도, 고수도 아니다. 누구든지 힘들었고 어려웠던 과정을 거쳤을 것이다.
이제 외판원 순회와 최장 공통 부분 문자열 문제만 남았지만, 알고보니 배운적 없는 알고리즘을 사용해야 하고, 찾아보니 나도 바로 이해하지 못하는 알고리즘이라 문제 풀기는 우선 포기하고, 이론 공부와 전에 풀었던 문제 다시 익히기에 집중하기로 했다.
20230503 오늘은 새 문제를 풀기보다는 복습과 교제 읽기에 집중하기로 한 날이다. 매 주차마다 현재 할일에 집중하는 것이 옳다. 그래서 나도 목요일에 시험을 마치고나면 바로 다음 주차 공부할 내용에 집중했다. 하지만 전 주차에서 제대로 집고 넘어가지 못한 것들이 있다고 느껴 이러다가는 이 크래프톤 정글에서 아무것도 얻고가지 못하지는 않을까 걱정이 되기 시작했다. 마침 점심 시간 이후에 김현수 코치님이 우리 반에 찾아오셔서 이에 대한 고민을 드렸더니 스스로 시간을 투자해야 한다고 하셨다. 이번 주차 이후에는 과제 중심으로 진행될텐데, 과제 중심으로 하다가 이 정글 과정을 마치고나서 코딩 테스트에서 제대로 하지 못하는 경우가 있어, 진행하는 도중에도 코딩 테스트를 위한 준비를 하는 것이 좋다고 하셨다. 이전 주차 문제 중 동적 프로그래밍을 다루는 동전 문제가 있어서 이번에 자신감을 가지고 풀어봤다. 처음엔 일부러 동적 프로그래밍 적용하지 않고 풀어서 예제 답도 잘 나왔지만, 오답이 나왔다. 그 다음에는 2차원 리스트를 이용한 동적 프로그래밍을 이용했다. 리스트의 맨 오른쪽마다 필요한 동전의 총 개수를 저장하도록 했고, 최소 개수를 알아내는 것이 불가능 하면 -1을 출력하도록도 했지만, 계속 오답만 나왔다. 할 수 없이 풀이를 볼 수 밖에 없었다. 그걸 보니 내 코드보다 훨씬 더 간결하고 DP 리스트도 만들어야 할 금액인 k길이인 1차원이었고, 각 원소를 문제에서의 최대 크기인 10001로 설정해놨다. 그래서 k번째 숫자가 10001이면 -1을 출력하도록 하더라. 이렇듯 내가 생각하지 못한 DP 방식이 여러가지가 있다. 쉬운것이 아니다..