[Week2] WIL - 백트래킹의 늪에 빠지다

알고리즘 주차가 시작되고 오랜만에 평화롭게 혼자 공부를 할 수 있었다.

학교를 다닐때도 알고리즘 공부를 열심히 하지는 않았어서 이번 기회에 감을 잡고 개발 역량을 길러보기로 했다.

먼저, 주차를 시작할 때 세워뒀던 목표들을 보며 얼마나 달성했는지를 체크해봤다.

역량	달성도	목표
문제해결	80%	백준 실버3~4 수준의 문제를 AI, 구글링 도움 없이 풀 수 있음.
특정 지식을 요구하는 브론즈1~실버4 문제를 제외하고는 무난하게 해결할 수 있었다.
설계	70%	최대한 효율적인 코드(시간 복잡도/공간 복잡도 고려)를 짜는 것을 목표로 한다.
최대한 시간 복잡도를 낮추는 방식으로 코드를 짜려고 노력했다.
구현	60%	문제당 실패 횟수를 3회 이하로 한다.
문제 조건을 똑바로 확인하지 않아 여러번 틀린 문제들이 있었다.
유지보수	40%	주석을 통해 명확한 풀이를 기록한다.
당시에 이해한 내용을 잘 정리하지 못한 것 같다.
협업	60%	코어타임 뿐만 아니라 팀원들과 적극적인 교류를 한다.
코어타임 시간 외에도 코드리뷰를 같이하려고 했지만 적극적으로 시도하지는 못한 것 같다.
태도	75%	모르겠는 문제에 대해 절대 AI를 사용한 코드 생성을 하지 않는다.
최대한 개념 학습을 할 때만 도움을 받았고, 코드 생성은 최대한 하지 않으려고 노력했다.
AI 활용	75%	맞힌 문제라도 AI에 코드 리뷰를 맡겨 더 최적화된 방법이 있는지를 모색한다.
문제를 해결했어도, 더 좋은 방법이 있는지 AI에게 코드리뷰를 맡겨보았다.
학습 민첩성	0%	특정 문제에 대해 이미 최적화된 구현 방법이 있다면 찾아보고 학습한다.
목표를 잘못 세웠다고 생각해여 이행하지 않았다. 문제 해결법을 먼저 학습하고 관련 문제만 푸는것은 응용력을 기르는데 도움이 되지 않을 것 같다고 생각했다.

 

목표를 세워두고 이를 이행하려는 노력이 부족했던 것 같다. 실제로 세워둔 목표를 어느 순간 까먹고 자유롭게 공부하여 효율이 떨어졌을 수도 있겠다는 생각이 들었다. 다음주차에서는 좀 더 확실하게 목표를 세우고 이를 이행하기 위해 노력해보자!

---

이번주 주요 ISSUE

Week2 basic 문제들을 풀면서 잊고 있던 개발 감각을 다시금 익힐 수 있었다. 난이도 중 문제를 모두 해결하는 것이 목표였는데 아쉽게도 목표를 이루지는 못했다. 백트래킹 문제에 익숙하지 않아서 설계를 하는것 부터가 어려웠고 결국 백트래킹 개념공부부터 다시 시작하게 되었다.

 

 백트래킹(Backtracking)

일단 해보고, 안 되면 돌아와서 다른 길을 시도하는 방식이다.

 

모든 경우의 수를 탐색하는 완전 탐색과 달리, 불가능한 경우의 수는 사전에 배제하는 방식이다.

주로

• 순열
• 조합
• N-Queen
• 미로 찾기
• 부분집합
• 스도쿠

문제를 해결할때 사용된다.

 

백트래킹을 사용하는 문제들은 공통적으로 3단계를 거쳐 탐색을 진행한다.

1. 선택: 현재 가능한 것 중 하나를 고른다.

2. 탐색: 그 선택을 한 상태로 다음 단계로 들어간다.

3. 취소: 방금 했던 선택을 되돌리고, 다른 경우를 시도한다.

 

하지만 방식을 안다고해도, 언제 선택을 되돌릴 것이고 무엇을 다음 탐색의 인자로 넘길지 판별하는 것이 처음에는 쉽게 되지 않았다. 재귀의 흐름을 완벽히 알아야 인자나 범위 설정을 할 수 있을텐데 재귀의 개념에 약한 나에게는 굉장히 어려운 과제였다.

그 중 인상깊게 풀었던 문제 하나를 다시 설명하며 백트래킹 개념을 다시금 머리속에 각인시켜보려고 한다.

---

외판원 순회

 

https://www.acmicpc.net/problem/10971

도시 i에서 도시 j로 가기 위한 비용을 W[i][j] 형태로 두고, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 문제이다.

 

0. 문제 해결 방식 정의

외판원의 최소 순회 여행 경로를 구해야하기 때문에, 갈 수 있는 모든 경우의 수를 시도해야 한다. 하지만 현재 저장된 최소 경로보다 길어질 것 같으면 그 순회는 조기 탐색 종료를 하면 되기 때문에 백트래킹 개념을 사용하면 효율적으로 해결 할 수 있다.

 

1. 종료 조건 정의

탐색을 언제 종료해야되는지를 설정하는 것은 백트래킹에서 정말 중요하다. 탐색을 마치고 이전 재귀로 돌아가며, 탐색을 마쳤을때 수행해야하는 로직을 정해둬야 모든 경로를 안전하게 탐색할 수 있다. 이 문제에서 나는 종료조건을 다음과 같이 정의하였다.

• 재귀로 넘겨받은 cost가 현재 최소 경로보다 클때
• 현재 위치에서 처음위치로 돌아가는 cost가 0일때

만약 위 조건들을 만족하지 않는다면 갈 수 있는 행선지이기 때문에 탐색을 시작한다.

 

2. 선택 조건 정의

이 문제에서 선택하는 것은 다음 행선지 위치이다. 갈 수 있는 도시들을 모두 반복 탐색하며 1. 이미 방문한 도시인지, 2. 해당 도시로 가는 비용이 0인지(갈 수 없는지)를 판별한다. 만약 두 조건을 모두 충족시키지 않으면 갈 수 있는 도시라는 것이기 때문에 방문했다는 표시를 남기고 탐색을 떠난다. 나는 visits 라는 리스트를 만들어 해당 도시를 방문 유무를 bool값으로 저장했다.

 

3. 탐색 조건 정의

선택을 마치고 해당 마을로 탐색을 떠나는 단계이다. 나는 인자로 총 3개를 넘기는 방식을 채택했다.

1. next: 다음 행선지 위치이다. W[i][j] 이런식으로 접근하기 때문에 next로 넘기면 해당 depth의 탐색에서 W[next][~] 이런식으로 접근한다.
2. index: 현재 몇번째 도시를 탐색중인지를 index로 표기하고 있다. 따라서 인자를 넘길때는 index + 1로 넘겨서 depth를 추가한다.
3. cost: 종료조건에서 현재 소비한 cost가 저장된 최소 경로보다 길어지면 바로 가지치기를 하기 때문에 필요하다. 현재까지의 cost에 W[current][next] 를 더하여 다음 탐색 행선지까지 드는 cost를 인자로 더하면서 넘긴다.

4. 취소 조건 정의

재귀를 하고 return으로 돌아오면 해당 경로의 탐색을 마쳤다는 뜻이기 때문에, 해당 도시의 방문 표시를 다시 돌려놔야한다. 따라서 재귀 직전에 True로 바꿔놨던 vistis[ ] 배열에 접근하여 다시 False로 바꿔주어야 한다.

 

5. 순회의 정의를 통한 도착도시 고정

순회는 어떤 도시에서 출발해도 결국 전체를 보면 같은 순서로 이동하는 것이라는 것을 알 수 있다. 예를들어,

[ 0 -> 1 -> 2 -> 3 -> 0]
[ 1 -> 2 -> 3 -> 0 -> 1]

 

이 2개의 순열은 얼핏보면 달라보이지만 사실은 같은 순서로 돌고있는 순회이다. 따라서 시작 도시를 0번째 도시라고 가정하고 시작하면, 도착지점을 고정시킬 수 있다는 아이디어를 활용했다.

 

위 아이디어를 설계하면서 백트래킹 인자와 조건들을 어떤식으로 설정해야되는지 조금이나마 감 잡을 수 있었고, 이후 word search나 다이얼 문자조합 같은 문제들도 풀 수 있게 되었다. 비록 지금은 풀다 실패했지만 N-Queen 문제도 풀 수 있을 정도로 성장해보겠다!

 

---

수요 코딩회

OpenAI 워크샵을 마치고 1박 2일 동안 Codex라는 AI Agent를 이용하여 자유주제로 웹 서비스를 제작해보는 프로젝트를 진행하였다. 나는 개념 학습보다는 AI와의 협업으로 어느 정도까지 개발을 할 수 있는지 척도를 세우는 것을 목표로 참여하였다.

 

커뮤니티 기능을 탑재한 2D 메타버스 웹 서비스 'Cyber Jungle'

 

실시간으로 다른 사람과 채팅하고, 파티를 맺을 수 있는 2D 메타버스 서비스를 기획하고 제작하였다. 사실 이전에는 AI에게 받은 답변을 참고해서 코드를 짜는 수준에 그쳤지만, AI Agent를 사용하면 배포까지 자동으로 해준다는 것에 놀랐다. 내 git 레포만 알려주면 자동으로 커밋과 머지같은 작업들을 자동으로 수행하였고, 프론트나 백, socket 등을 자동으로 연결하여 결과물을 배포해주었다. 비록 음성으로 웹상의 사람과 대화하는 기능을 구현하는것은 결국 실패했지만 오로지 AI만 이용해서 웹 서비스를 제작하고 배포해보는 경험을 통해 AI Agent 사용법을 익힐 수 있는 좋은 경험이었다. 

 

이참에 발표공포증을 고치기 위해 일부러 발표를 자원하여 진행하였다. 오랜만에 하는 발표라 두서없이 막 말한 것 같지만, 그래도 발표에 대한 공포가 조금은 줄어들은 것 같다. 다음주도 파이팅..!