20230420 오늘 시험은 Moo 게임, PPAP, 그리고 스카이라인 문제였다. 첫 두 문제는 그래도 패턴을 이해해서 코드를 짤 수는 있었다. 예제에 대한 답은 잘 나왔지만, 에러가 떴다. 그래도 2번 문제는 나중에 코드를 정교하게 정리하기 위해 ChatGPT의 도움을 받고 정답이 나왔지만, Moo 문제는 재귀 함수를 이용해서 문자 길이가 너무 길어지다보니 RecursionError를 계속 마주하여 결국 완성하지는 못했다. 3번 문제는 건드릴 여유도 없었다. 다들 어려워했지만 나는 2번 문제는 어떻게든 풀어서 문제 풀이 시간 때 발표하러 나섰다. 오늘 부터는 트리에 대해 배울 것이다. 교제 및 SWexpertacademy 동영상 강의를 보면서 개념은 완벽히 익혔다. 하지만 코드 문제 풀이에서 구현하는 것이 잘 안된다. 일단은 풀이를 보면서 접근하면서 충분히 익힐 수밖에 없어 보인다. 1주차부터 조금씩 힘들어진다는 것을 느꼈지만, 이번에 전보다 더욱 힘들다는 것을 느끼기 시작한다. 앞으로도 이 강도가 더 세질 듯 하다. 걱정이 커진다.

20230421 이번주차 부터는 트리를 이용하는 코드 문제를 푸는데, 어제까지 개념은 충분히 익혔지만, 파이썬으로 어떻게 표현해야 할지가 막막했다. https://cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html 위 링크가 되게 깔끔하게 정리되어 있는데, 클래스로 복잡하게 짜는 대신 딕셔너리를 이용해 각 부모 노드를 key로 두고, 자식 노드들을 value로 두고 있었다. 그리고 저 블로그 주인의 DFS와 BFS 구현 코드를 보면서 왜 이렇게 짜였는지 이해하는데 집중했다. 알고보니 DFS는 스택을 쓰고, BFS는 큐를 사용한다. 이렇게 배운 내용을 응용해 바이러스 문제를 풀었다. 컴퓨터 1과 연결된 컴퓨터의 개수를 새는 문제였는데, 자세히보면 후손(descendent) 노드 개수를 새는 문제다. DFS와 BFS로 루트 노드를 정하고, 그 기준으로 방문한 노드 리스트를 확인하는 점을 이용해 방문한 노드 개수의 리스트 길이를 구하는 방식으로 바꿔 진행했더니 정답이 나왔다. 드디어 트리 관련 문제를 풀이 보지 않고 찾아 뿌듯했다. 하지만 다른 문제들은 입력 방식도 다를거라 개념을 알아도 새로운 접근법을 연구하거나 찾아봐야 할 듯 하다. 그거 하나 스스로 풀었다고 해서 아직은 자만할 수 없다. 실제로 이진검색트리 문제에서 전위순회로 입력한 값을 후위순회로 변환하는 과정을 나타내는데에도 막막했고, 풀이를 봤는데도 대부분이 비슷하게 작성했고, 그냥 봐서도 왜 그렇게 짰는지 이해도 잘 안됐다. 우리 조원과 얘기하면서 공부하니 겨우 이해가 되었다. 전체적으로 완전 생소한 개념이라 단번에 이해되지 않는다. 난이도가 하인데도 쉽지 않다. 앞으로가 더 걱정되기 시작한다.

20230422 BFS를 이용한 특정 거리의 도시 찾기 문제를 풀었다. 기존에 사용하던 BFS 함수를 그대로 쓰려 애쓰다보니 뭔가 잘 안 맞았다. 반환하는 변수가 달라서 그렇다고 느낀다. 역시 특정 개념을 적용한다 해도 유연성이 있어야 한다는 것을 다시 느꼈다. 특히 특정 노드에서 다른 노드까지의 거리를 어떻게 구해야할지 막막했는데, 다른 사람의 솔루션을 참고해야 했다. 우선 딕셔너리로 트리를 구성한 뒤에, 거리 정보를 담기 위한 리스트를 만들어서 시작 노드에 해당하는 인덱스 부분은 0으로 설정하고 나머지 방문하지 않은 부분은 -1로 초기화 한다. 그 다음에 트리 딕셔너리의 key마다 value를 보고 각 value에 해당하는 거리 리스트의 위치를 현재 노드의 값에 1을 더한 값으로 업데이트 한다. 그렇게 진행하다보면 구하고 싶은 거리가 있는지 확인되면 그 위치들을 출력하는 것이다. 해당하는 위치가 없다면 -1을 출력한다. 솔루션을 통해서 이렇게 아이디어만 얻고 내가 직접 짜봤다. 다른 사람들은 도시 정보를 담은 트리를 리스트로 구현했지만, 나는 딕셔너리를 고집했다. 이렇게해야 내 지식이 될 것 같다.

20220424 이분 그래프 문제 푸는데에 초반에 시간을 많이 썼다. 기존에 짜놓은 DFS 함수와 트리 만드는 코드의 흐름을 이용해 이분 그래프가 아닌 예제를 통해서만 하려다가 결국 잘못됐음을 깨닳았다. 처음에는 방문한 노드 리스트를 보고 현재 노드가 이미 들어있는지 여부만 따졌다. 각 노드의 색상을 확인하는 리스트를 만들어서 시작 노드의 색상 값을 1로 설정하고, 인접 노드가 방문되지 않았으면 -1을 곱해줘야 하는 방식이었다. 진행하다가 어떤 노드와 인접 노드의 색상이 같으면 이분 그래프가 아니라고 판단하면 되는 것이었다. ChatGPT 도움을 받으면서 했다.

20220425 고슴도치 문제와 토마토 문제는 서로 비슷한 점이 있다. 고슴도치 문제에서는 물이 매번 이웃한 지점으로 퍼지고, 토마토 문제에서는 익은 토마토가 근처의 덜익은 토마토도 익게한다는 것이다. 서로 2차원, 3차원이라는 것만 다르다는 것이다. 고슴도치 문제 풀때 고슴도치의 움직임은 미로 문제를 응용하기만 하면 되는거라 쉬웠다. 물론 아직 외우지는 못해 보고 풀었다. 다만 시작점과 도착점을 개별적으로 설정해줘야 한다는 점이 있었다. 그래서 입력된 지도 리스트에서 특정 문자를 가진 위치들을 반환하는 함수를 만들어서 고슴도치와 물의 위치를 저장하도록 했고, BFS 함수에 입력했다. 특정 값이 한 칸에서 다른 칸으로 움직이는 것이 아니라 근처로 퍼지도록 하는 개념이 정말 생소하고 힘들었는데, ChatGPT의 도움을 받았다. 처음에는 고슴도치용 BFS 함수, 물용 BFS함수를 따로 준비하려 했지만, 깔끔하게 한 함수에 물의 퍼짐 여부도 포함해줬고, 고슴도치의 움직임을 파악해주기 위해 지도와 크기가 같은 2차원 리스트도 따로 만들어줬다. 토마토 문제는 고슴도치 문제에서 물이 퍼져나가는 개념을 이용해서 풀었다. 물과 다르게 토마토용 큐를 만들어야 했다는 점이 다른 점이었다. 그래도 한번에 풀리지는 않아서 ChatGPT의 도움을 받았다. 일단 이 문제는 토마토가 담긴 상자의 개수도 반영이되고, 층으로 쌓기 때문에 3차원 리스트를 이용해야 했다. 이것도 똑같이 한칸 움직였을 때의 위치의 값이 0이면 1로 바꿔주는 방식으로 풀었고, 토마토 변수 값을 계속 업데이트 했다. 다른 점은 익은 토마토 정보를 담기 위한 큐를 만들었다는 것이다. 근처 위치 중에서 값이 0인 것만 1로 업데이트 해주면 되는 것이었기에 굳이 빈 공간을 뜻하는 값이 -1인 경우를 고려하지는 않았다. 어차피 빈 공간에 둘러쌓여 있는 덜 익은 토마토(0)가 있으면 영향을 받지 않기 때문에 과정을 마치고 나서 0인 값이 하나라도 존재하면 “-1”을 출력하도록 했다. 게다가 토마토 큐에 익은 토마토의 위치 값을 입력하고 나서 이웃하는 덜 익은 토마토의 값을 업데이트시키고 이 위치 값들을 담기 위한 리스트를 만들어서 기존의 토마토 큐를 업데이트한다. 업데이트 될 때마다 값을 증가시키는데, 우리가 보기에는 전부 익었지만, 루프는 계속 돌아가기 때문에 쓸데없이 1이 더 늘어난다. 따라서 이를 위해 1을 하나 뺀 값을 반환하도록 작성 되었다. 요즘 ChatGPT랑 풀이에 너무 의존하는건 아닌가 생각도 든다. 그런데 현재로서는 어쩔 수 없다는 생각도 들고는 한다. 어느정도 내 방식을 생각하다가 그걸 구현하는 방법을 ChatGPT에 부탁하는 방식으로 진행한다. 생각해보면 막히는걸 가지고 계속 낑낑거리다가는 시간만 낭비할 것 같다.

20230426 오늘은 문제 2개를 풀었다. 하나는 위상 정렬을 이용하는 장난감 조립 문제였고, 또 다른 문제는 DFS를 이용하는 연산자 끼워넣기 문제였다. 둘 다 내 스스로 접근하기 힘들어 풀이를 보고 풀었다. 장난감 조립 문제는 위상 정렬을 꼬아놓고 필요한 부품을 축적하고 축적하는 방식이라 더욱 힘들었다. 그리고 연산자 끼워넣기 문제는 DFS를 이용하기 위해 스택을 어떻게 적용해야 하는지 계속 고민했는데, 알고보니 재귀로 구현하는 것이었다. 여태껏 스택만 사용하는줄 알았는데, 재귀도 사용할 수 있다는 것은 오늘 알았다. 점점 풀이나 ChatGPT에 의존해야 하는 일이 많아져 걱정이 커져간다. 그 다음에는 빙산 문제에 도전해보려 했다. ChatGPT로 특정한 칸의 빙산 녹이는 함수 구현까지는 해결했다. 그리고 이걸 이용해서 현재의 빙산을 녹이는 한 페이즈 구현까지도 해냈다. 문제는 빙산들이 서로 갈라졌을 때를 구현하는 것이었다. DFS나 BFS를 이용해서 전체 개수에 비해 연결된 것에서 개수가 비교적 부족할 때를 이용하면 된다고 하는데, 아직 힘들다. 결국 피곤해서 이 부분은 아직 해결하지 못했다.