20230413 오늘 시험 중 첫 번째 문제는 운이 좋게 예전에 이미 풀었던 문제였다. 2, 3번 문제를 볼 때 처음에 당황스러웠지만, 관련 개념을 검색해보면서 차근차근 풀어갔다. 2번 문제는 재귀였지만, 알고보니 비교적 간단한 재귀라 복잡하게 생각할 필요가 없는 것이었다. 3번 문제는 iteration 모듈의 combination 함수를 사용해야 하는 문제였다. 처음에 이걸 무시하고 풀었더니 오답이 나왔다. 시험을 마치고 깃허브에 올려야 했는데, 내 리뷰워에게 요청 보내는데에서 애를 좀 먹었다. 그리고 각 문제마다 한 명이 나와서 문제를 어떻게 풀었는지 설명하는 시간을 가졌는데, 첫 번째 문제는 내가 맡았다. 일의 자리 숫자면 앞에 0을 붙이고 하라 했는데, 나는 그냥 정수로 진행했다. 10으로 나눈 몫이 어차피 0인 점을 이용했고, 10으로 나눈 나머지 만을 이용했다. 그리고 while 반복문을 이용해서 진행했다. 나는 다 간신히 풀 수 있었지만, 그랬다고 해서 자만해서는 안된다고 한다. 나중에 더 어려운 문제를 맞이할 수 있기 때문이다. 오늘부터 2주차인데, 이진 검색, 분할 정복, 스택, 큐, 우선순위 큐 등을 배우게 될 것이다. 하지만 아직까지 원형 큐와 힙 정렬을 사용하는 우선순위 큐의 정의랑 과정이 이해되지 않는다.

20230414 오늘은 어제에 이어 스택 및 큐에 관한 문제를 마저 풀기로 했고, 막히는 문제가 아직 있어, 개념을 더 정리한 다음에 풀어보기로 했다. 해싱(hashing)에 대해서도 알게 되었다. 이번 주차 문제에는 없지만, 매우 중요한 개념이라 적어도 정의랑 어떻게 작동하는지는 알아야한다고 한다. 우선 공부한대로 해싱의 정의를 말하자면, 데이터를 저장할 위치(인덱스)를 연산을 통해 구하는 방법이며, key와 value를 mapping하는 방법이라고 설명할 수도 있겠다. 이렇게 구한 해시값을 인덱스로 해서 해시 테이블에 저장한다. 해시 충돌이란 어떤 값을 해시 테이블에 넣어야 하는데, 들어가야 할 인덱스에 이미 값이 들어있어 저장할 송간이 중복되는 현상을 말한다. 이를 해결하기 위한 방법이 여러가지가 있는데, 교제에서는 체인법과 오픈 주소법만을 얘기한다. 그리고 책이나 인터넷을 통해 정의를 잘 익혔어도 응용하고 다르게 적용하는게 아직 어렵다. 예를들어 이분 탐색의 경우 양끝의 인덱스에서 시작해서 가운데 인덱스 기준으로 진행해야 한다는 틀에 박혀있었는데, 아무리해도 응용이 되지 않아 솔루션을 찾았다. 알고보니 가운데 값은 신경쓰지 않고, 왼쪽과 오른쪽 인덱스만 이용해서 서로 위치가 엇갈릴 때만 고려하면 된다고 했다. 이런식으로 thinking-outside-the-box 연습이 필요할 듯 하다. 게다가 어떤 용어의 정의는 알겠는데, 응용을 도대체 어떻게 해야할지 모르는 것들도 있다. 분할 정복이 그렇다. 작동 원리가 아직도 이해가 힘든 것들도 있다. 원형 큐가 그렇다.

20230415 오늘은 난이도 상인 스택 문제 두개 푸는데에 시간을 많이 보낸 듯 하다. 그나마 이해하기 쉽고, 어느정도 알고리즘을 만드는게 가능했기 때문이었다. 어쨌든 오늘 이렇게 스택 문제들을 마무리했다. 괄호의 값 문제는 기존의 괄호 조합 문제와 다른점이 많았고, 나도 손으로 알고리즘을 짜보면서 나름 노력해서 덧셈 구현은 구현할 수 있었지만, 괄호 내부를 이용해서 곱셈 연산을 하는 데에는 많이 힘들었다. 그래서 할 수 없이 풀이를 봤는데, 내가 푼것과 다른 방식으로 접근한 것을 볼 수 있었다. 2(2+3*3)+2(3) 식에서 곱셈 및 괄호 내의 숫자를 먼저 처리하려는 방식을 택하려 했지만, 그건 코드로는 구현이 거의 불가능에 가까웠고, 4+18+6의 방식으로 접근했다. 그리고 괄호를 완성시킬 때 서로 짝을 만나서 상쇄하는 것을 넘어 인덱스 값도 바로 앞일 경우에만 더하기나 곱하기 연산하는 방식을 고려했어야 했다. 게다가 연산을 위한 변수를 두개 만들어서 나중에 전체 연산을 통합할 변수에 집어넣는 것 까지는 해냈지만, 그것도 곱셉 연산만을 포함해야 하는 방식이었다. 일단 곱한 값들을 더한 뒤에 나중에 크기가 커지는 것을 막기 위해 방금 더한만큼 나눠야 했다. 어쨌든 생각이 넓힐 수 있는 기회였다고 생각한다. 그 다음 문제는 그래도 내 스스로 알고리즘을 성공적으로 구현하고 정답을 낼 수는 있었다. 하지만 막판에 옥에 티가 있었다. 앞서 스택에 입력한 값이 이번에 입력될 값보다 작으면 그 숫자를 빼내는 알고리즘을 구현했는데, 문제는 그 앞에있는 다른 작은 숫자들도 뽑아내야 한다는 것이었다. 그리고 제거할 숫자의 개수를 초기에 설정해야 했기 때문에 더 까다로웠다. 그래서 이번건 ChatGPT의 도움을 받았다. 그리고 처음에는 정수로 입력한 값을 스트링으로 변환하는 과정을 취했는데, 오히려 이게 처리 시간만 낭비하는 쓸데없는 짓이었다. 그냥 아예 스트링으로 입력하도록 하니 정답 처리되었다. 아직까지 시간 초과 문제를 해결하는 것에 약하다. 방법이 제안되어있기는 하지만, 그걸 넘어 더 효율적으로 코드를 짜는 법을 알아야 한다. 나도 아직 모르는 함수도 많으니 그런 듯 하다.

20230417 백준 10000번 문제 원 영역 문제를 풀어보기로 했다. 좌표와 반지름이 주어진 원들이 영역 몇개를 형성하는지 알아내는 문제였다. 아무리 해도 코드로는 어떻게 구현해야 할지 몰라서 결국 검색을 했더니 전혀 생각하지 못했던 방식으로 접근을 하고, 내가 전에 써보지 않은 기능을 사용해야 한다는 것을 알게되었다. 그것도 스택으로 어떻게 구현해야 할지 막막했는데, 원 하나를 괄호 하나를 완성해서 형성하는 방식으로 접근하고 있었다. 그리고 원끼리 접하지 않으면 괄호 사이에도 공간을 마련해야 했다는 점이 더 충격이었다. 일단 이 문제는 놔두기로 했다. 그리고 백준에 놀란 점이 하나 있었다. Numpy 모듈을 제공하지 않아 리스트를 넘파이 배열로 변환할 수 없어 행렬 문제(10830) 푸는데에 애를 많이 먹었다. 행렬 곱셈 용 함수를 따로 준비하라는 의도로 보이는데, 머리를 하도 많이 쓴 나머지 인터넷과 ChatGPT의 도움을 받으면서 진행했다. 처음으로 재귀 함수를 어떤 때 써야하는지 감이 느껴져서 뿌듯했지만, 찬물을 끼얹은 듯 하다.

20230418 오늘은 가장 긴 증가하는 부분 수열(11053번) 문제와 사냥꾼(8983번) 문제를 풀었다. 사냥꾼 문제는 알고리즘 구현하는 것은 어렵지 않았다. 다만, 시간 제한이 있어 이진 탐색 알고리즘을 적용해야만 하는 문제라 애를 먹었다. 이진 탐색이 시작점, 중간점, 종점을 잡아서 탐색할 범위를 줄여가는 방식이라는 것은 잘 알겠지만, 문제마다 다른 방식으로 적용하기 때문에 어떻게 응용해야 할지를 도무지 모르겠다. 할 수 없이 남의 풀이를 보고 디버깅하고 노트에 기록해가면서 어떻게 흘러가는지 이해하면서 공부하고 있다. 심지어는 가장 긴 증가하는 부분 수열 문제는 중점을 잡는 것도 아니고 주어진 리스트에서 범위를 잡고 또 그 범위 안에서 숫자들을 비교하는 방식이었다. 찾아보니 Longest Increasing Subsequence라는 유명한 알고리즘 문제라고 한다. 할 수 없이 솔루션을 찾고 풀 수 밖에 없었다.

20230419 뱀 문제와 원 문제를 풀었다. 뱀 문제는 어제 같이 개념 이해 강의를 들으면서 감을 약간 잡았고, 풀이에서 말한거와 다르게 구현해보려 했지만, 쉽지 않았다. 풀이에선 뱀의 방향을 x, y 좌표 설정으로 했지만, 나는 리스트를 상하좌우 리스트를 만들어 하려 했다. 최대한 풀이랑 스타일을 맞추려 했지만, 머리만 지끈지끈거렸다. 할 수 없이 이건 포기했지만, ChatGPT의 도움을 계속 받으면서 겨우 해냈다. 원 문제는 푸는 방식이 내가 생각하지도 못한 방식이었다. 스택을 이용해서 풀라고 적혀있었지만, 괄호 완성을 응용할줄은 전혀 생각지도 못했다. 원의 왼쪽이 접하는 여부를 따지는 문제였다. 이번 두 개는 풀이 보며 풀었다. 새로운 사고 방식을 알게되어 기쁘지만, 정신적으로 피폐하게 하는 문제였다.