WEEK01 알고리즘 1주차 후기

3일 미니 프로젝트 발표하자 마자 단 1분도 쉬지 않고 냅다 일주일 알고리즘 40문제 카운트다운이 시작돼버림;;.. 역시 험난한 정글. 그치만 프로젝트 끝난 날은 회식이라 오랜만에 2까지 부어라 마셔라 재밌었다^_^

백준에서 난이도별로 정해진 문제를 푸는 건데, 이번주가 첫 주차라서 초반 40문제 정도는 금방금방 풀었다. Hello World같은거라서.. 근데 뒤로 가서 난이도가 하-상, 중 정도 올라가니까 하루에 두 문제 푸는 것도 감지덕지ㅠㅠ 그나마 챗GPT랑 무려 백준 플래이신 팀원분의 도움을 받아 어찌저찌 마감날에 40문제를 다 풀었다. 다음주부터는 하-하 문제도 없고 난이도 확 올라갈 것 같은데 어째 다 푸냐ㅠ

풀면서 새롭게 알게되는 파이썬 문법 같은건 노션에 정리했고, 여기는 알고리즘을 풀 때 주의해야 할 사항들을 정리해봤다.

1. 하노이 탑

• 파이썬만 그런지 모르겠는데 저장해야 할 내용을 string에 담아서 += 하는건 시간 상 아주 비효율적이다. 하노이 다 풀어놓고 이것 때문에 시간초과 계속 나서 몇시간 고민함. array에 넣어서 .append() 하는 게 훨씬 빠르다.

2. 외판원

• 일방향이 아니라 "순환"이기 때문에 시작점은 고정해놓고 시작해도 된다. 0→1→2→3→0이나 1→2→3→0→1이나 똑같은 루트이다. 시작점 하나를 빼놓고 조합을 만들면 조합 경우의 수가 훨씬 줄어들고, 그래야 시간초과가 나지 않는다.
• 자바스크립트와 다르게 파이썬은 함수 밖에서 선언한 전역변수를 함수 내에서 쓰려면 그냥 써서는 에러나고 함수 내에 global 변수 선언을 해줘야 한다.
• cost를 input으로 받았는데, cost가 0이면 비용이 0으로 싸게 갈 수 있는 길이 아니라 못 가는 길임을 생각해야 한다. 아니면 최소 비용에 못 가는 길이 자꾸 포함돼서 틀림.
• 나는 위에서 말한 cost 0 문제에서 고려하지 못한게 하나 더 있었는데, index out of range 문제 때문에 for루프 밖에서 별도로 n-1번째에서 0번째 갈 때에 대한 비용을 처리했는데 여기에서도 n-1→0의 cost가 0일때를 고려줘야 한다는 걸 못 챙겼다.
• 최대 입력값이 '가중치 100만 * 도시 10개'라서 최대값이 10^7인데 최댓값 초기화를 이것보다 작게 하면 제대로 나오지 않는다. 이럴 경우에는 그냥 float(inf)로 하는 것도 방법이다.

3. 차이를 최대로

• 문제를 보고 규칙 이해를 직관적으로 못했다. 수식은 거창하게 쓰여있지만 결국은 배열에서 원소 간 차이값을 절대값으로 더하라는 건데 처음에는 아예 잘못 읽었다가 제대로 읽고 나서도 무슨 뜻인지는 모르고 일일이 수식에 대입해서 풀었다. 팀원한테 반례 찾아달라고 물어봤다가 암산으로 푸는 거 보고 충격받았는데 내가 바보인거였음.
• 예제 보고 대입해서 이런건가..? 일단 코드 짜보자! 하지 말고 정확하게 수학적 규칙을 찾은 뒤에 그걸 코드로 옮겨야 한다. 그렇게 되면 예제만 맞고 나머지는 다 틀리는 엉터리 코드가 될 수 있음. 반례도, 이건 될 것 같은데..? 하지 말고 꼼꼼하게 최소값/최대값/경계값/값이 없을 때/1일 때 같은거 다 입력해보기.

4. 수 정렬하기

• .sort() 안됨->퀵소트 안됨->머지소트 안됨->카운팅소트로 해결했다ㅋㅋㅋ 이 경우에는 입력값이 최대 '만 * 천만개'로 너무너무 커서 이걸 array에 다 저장하면 메모리가 못 버티기 때문에 저장하지 않고도 정렬할 수 있는 카운팅소트가 정답이었다. 이번에 처음 알게 된 정렬 방식인데, 누적 도수분포표를 만들어서 해당 등급 내에 몇개가 있는지를 이용해 빈 배열에 채워넣기! 항상 구현하는데 급급해서 입력 최댓값은 한 번도 신경 써 본 적이 없는데 신박한 문제였다.

5. 연산자 끼워넣기

• set() 안에는 string, number, tuple만 넣을 수 있다. 원칙적으로는 이터러블이 들어가면 되는 거라 일반 list 정도는 넣어서 만들 수 있긴 한데, 이중 list 넣어서 중복 제거하려면 set(map(tuple,list)) 혹은 set([tuple(i) for i in arr]로 튜플로 형변환 해서 넣어줘야 한다.
• 재귀 쓸 때에는 메모이제이션(=dp) 써서 메모이제이션 해 놓은게 있다면 그걸 리턴하는 방식으로(if n in dict: return dict[n]) 해야 시간초과가 나지 않는다. 그리고 여기서 arr를 dict의 key값으로 쓰려면 arr 그대로는 안되고 tuple로 만들어야 한다.(tuple(arr))
• combination을 꼭 직접 구현해야만 하는 상황이 아니라면 import itertools, itertools.combinations 같이 가져다 쓰는 게 훨씬 빠르다. 굳이굳이 힘들게 구현했는데 더 오래걸리는 바보같은 짓은 하지 말자...

6. Z

• 개 오바쌈바였던 문제.... 규칙은 간단해서 금방 할 수 있을 줄 알고 이것만 풀고 들어가자! 했는데 반례 하나가 뒤지게 안풀려서 새벽 4시반까지 하고도 해결 못하고 걍 들어감... 챗GPT 바보같은 샛기도 못 찾아냄 근데 다음 날 아침에 좀 개운해진 머리로 보니까 한 번에 보이는 걸 보면 안 풀리는 문제는 계속 붙들고 있지 말고 좀 쉬었다 해야되는 것 같다. 원인은 사분면 나누는 경계 조건의 부등호에서 어느 쪽에 등호가 붙는지였다.
• 계산 안해도 되는 부분은 생략할 수 있다면 생략하자. 나는 재귀로 푸는걸 좋아하고 이 문제도 재귀로 푸는 문제였는데, 모든 경우의 수를 재귀로 다 구하려고 하면 시간초과 날 확률이 상당히 높다. 이 문제는 4분면에서 타겟 지점이 속하기 전의 사분면(ex. 3사분면에 타겟이 있다면 1,2사분면)은 굳이 단계를 다 구해서 카운트를 올리지 않고 사분면에 속하는 칸의 개수만 변의 길이^2으로 더해주면 아주 빠른 속도로 재귀 호출을 끝낼 수 있다. 재귀는 확실히 깊이가 깊어지면 에러가 잘 나기 때문에 종료 조건과 예외 처리가 중요한 것 같다.

7. N퀸

• 도저히 시작 지점조차 가늠이 안 가서 책 보고 푼 문제ㅜ. 조합 구하기=분기, 예외 처리=한정이라서 내가 자주 하는 조합 다 구하는 거에서 예외 처리만 제대로 해주면 상당히 효율적인 분기한정법(branch and bouncing)이 될 수 있다.
• 마지막 퀸 배치라서 카운트 올리고 break 하기 전에 w=True, diag=True로 플래그 값을 변경해버리면 count++ 하고나서 그 전 배치(n-2번째)로 돌아갔을 때 플래그에 n-1번째에 변경한 True 값이 그대로 저장돼 있고, 이미 그 호출을 빠져나왔기 때문에 n-1번째를 선택하기 전으로 되돌릴 방법이 없다. 따라서 break 하고 나서 플래그 True값 주고, i+1번째 호출 끝나면 다시 False 값으로 되돌리기.