WEEK02 알고리즘 2주차 후기

아무래도 1주차는 거의 기본 구현문제였는데 2주차 돼서 여러 이론도 나오고 플래티넘 문제도 섞이다 보니 문제 수는 줄어도 시간은 훨씬 오래 걸렸다. 정답 코드 안 보고 혼자서 풀려니 골드-플래 문제는 한 문제에 하루씩 걸림;;; 막판에는 시간이 모자라서 어쩔 수 없이 정답 로직을 좀 봤다. 로직만 아는 상태로 코드는 내 힘으로 짜려고 했는데 그것조차 쉽지 않음;

1. 수 찾기
   • 아무 생각 없이 찾아야 하는 수 배열 돌면서 주어진 배열 안에 있는지 if ㅇㅇ in ㅇ 했더니 당연히 시간 초과ㅋㅋㅋ 알고리즘 분류 보고 이분탐색으로 바꿨는데 재귀로 구현했더니 또 시간초과가 났다. 재귀보다는 for문이나 while문으로 돌리는 게 훨씬 빠르고 안전하다. 재귀는 입력값이 커지면 depth가 기하급수적으로 커지기 때문에 recursion error가 날 확률도 높다.
   • 이분탐색 돌릴 때 기존 배열을 slicing해서 넘기는 것보단 어디부터 어디까지 자를지 start랑 end 인덱스를 업데이트하는게 낫다. 파이썬에서 list[start:end+1]로 하는 슬라이싱은 리스트를 전체 순회하면서 start와 end에서 자르기 때문에 O(n)의 시간이 들게 된다.
2. 큐 2
   • 스택은 그냥 배열로 구현할 수 있지만 큐는 선입선출할 때 remove()나 pop(0)으로 꺼내면 O(n)의 시간이 들어 시간초과가 날 확률이 아주 높아진다. 기존의 원소를 직접 지우기보다는 front와 rear 포인터를 움직이면서 '지운 것 처럼' 보이게 하는 방법을 사용할 줄 알아야 한다.
   • 그냥 파이썬 내에서 여러 변수랑 함수로 큐를 구현해도 되지만, 클래스로 만들어두면 여러 곳에서 두고두고 사용하기 좋다. 그걸 위해서 파이썬으로 클래스 제작하는 법을 알아야 하는데, 나머지는 자바스크립트랑 비슷한데 [ 메서드는 self를 매개변수로 받아야 하는 것, 내부 변수를 사용할 때는 self.변수명으로 사용하는 것, __init__ 메서드를 정의하면 인스턴스 생성할 때 넘겨받은 변수로 초기화할 수 있다는 것 ] 정도가 달랐다.
3. 나무 자르기
   • 이분 탐색을 시작할 때 start 인덱스가 1인지 0인지를 잘 챙겨야 한다. 아무 생각 없이 자르는 길이가 0이 될 수는 없지! 하고 1로 설정하고 시작했는데 생각해보니 나무는 0부터 자를 수 있다. (몽땅 잘라버리기!)
   • start와 end가 같을 수도 있으니까 while문의 조건은 start <= end여야 한다. 등호가 빠지면 탐색 구간이 한 칸인 경우는 포함되지 않아 틀리게 된다.
   • 반례 찾을 때는 답이 0이 될 때나 입력값이 모두 같을 때를 생각해보자.
   • '적어도 M미터의 나무를 가져가야 한다'고 했으니까 잘라서 얻은 길이와 원하는 길이가 딱 맞아 떨어지지 않을 경우도 고려해야 한다. 나무가 5, 3, 3이고 원하는 길이가 3일때는 3미터로 잘라서는 2미터밖에 얻을 수 없고 2미터로 자르면 5미터를 얻게 된다. 어찌됐든 최소 3미터는 얻어야 하므로 답은 2미터가 되게 된다.
4. 제로
   • 별건 아닌데 sum을 변수명으로 썼다가 'int' object is not callable 에러가 나버렸다. 처음에는 내가 sum 함수를 잘못 사용했는 줄 알고 공식 문서 찾아봤는데 문제가 없어서 당황했는데 그게 아니었음. 예약어는 변수명으로 쓰지 말자!
5. 공유기 설치
   • 내가 처음 시도했던 방식은 무조건 양 끝에 하나씩 설치해놓고 그 두개를 제외하고 거리가 최소가 되는 집을 찾는 것이었다. 그러나 양 끝에 공유기를 설치하는데에 집중한 것이 문제였다. 첫 집과 끝 집 사이의 거리를 남은 공유기의 개수로 나눠서 최적의 거리를 정해두고 첫 집(0)에서부터 최적의 거리(@)를 더해가면서(0+@, 0+2@, ..) 최소 타겟 거리 이상인 집을 찾았다(0+@보다 먼 집). 그런데 이렇게 하면 설치하기로 한 집들이 최적의 거리보다 조금씩 오른쪽으로 밀려서 마지막 집이 너무 오른쪽으로 치우치면 이미 설치해뒀던 끝 집과는 최적의 거리를 유지할 수 없다.
   • 그게 아니라 최적의 거리를 이분탐색하면서 찾아야 했다. 이렇게 하면 제일 마지막에 설치한 집이 제일 끝집이 아닐 수 있는데, 그건 사실 상관 없다. '가장 인접한' 집 사이 거리가 최소가 되어야 하므로 마지막으로 설치한 집과 그냥 존재하는 마지막 집 사이에 거리가 어느정도 남아도 설정했던 최적 거리보다만 작으면 상관이 없어진다.
   • 이분탐색은 탐색해야 할 타겟이 1차원일 때 좌우로 움직이면서 찾는거라 집이 1차원에 있다는 것에 집중한거였는데, 정해야 하는 목표가 여러개가 아니라 하나여야 한다는 것을 명심하자.
6. 두 용액
   • 이것도 처음 시도했던건 값에 따라 양수와 음수로 배열을 나눠서 절댓값이 작은 것들에 포인터를 각각 두개 두고 두 포인터값을 더한 값이 양수면 음수 포인터의 절댓값을 키우고 음수면 양수 포인터의 절댓값을 키우기였다. 결론적으로는 맞긴 한데 양수/음수를 나눠서 진행하면 양수 두개가 답이 될 때나 음수 두개가 답이 될 때는 틀리게 된다.(ex. [-100, 1, 2])
   • 다음으로 고쳐본건 양수/음수 배열 둘 다 따로 이분탐색 하기였다. 그런데 합이 음수일 때 양수를 큰쪽으로 탐색해야 하는지 음수를 큰 쪽으로 탐색해야 하는지 알 길이 없었다
   • 마지막으로는 첫번째 용액은 루프로 돌면서 고정해놓고, 이분탐색으로 합이 제일 0에 가까운 두번째 용액을 찾기였다. 뭐, 무식한 방법이라 답이 틀렸을 것 같진 않은데 루프 도는게 n, 이분탐색이 logn으로 총 O(nlogn)이 돼서 시간 초과가 났다.
   • 결론은 투포인터! 처음 시도했던거랑 방식이 같긴 한데 양수/음수 나누지 않고 해야 했다. 일반적으로는 start와 end 모두 맨 처음에서 시작해서 합이 0보다 크면 end를 오른쪽으로, 0보다 작으면 start 오른쪽으로 옮겨서 합을 키우거나 줄이는 방식이다. 그러나 모두 양수인 배열은 end를 오른쪽으로 옮기는 걸로 합을 키우고 start를 오른쪽으로 옮기는 걸로 줄여서 조절할 수 있는데, 지금처럼 양수/음수 둘 다 있으면 그게 안된다(ex. [-10, -3, -1, 3, 5, 100]). 여기서의 투포인터는 포인터를 양쪽 끝에서 시작해서 합이 0보다 크면 end를 왼쪽으로, 0보다 작으면 start를 오른쪽으로 옮기는게 핵심이다!
   • start, end, min(max) 정할 때 잘 생각해야 한다. 내가 넣은 값이 정말 최대인지, 정말 최소인지. 이번에는 end를 levels[-1]로 했었는데, levels[-1]+k이 맞아서 디버깅을 좀 했다.
7. 곱셈
   • 결과값이 너무 커서 '나눈 나머지'를 내라고 하는 문제는 마지막에 나머지를 구하면 이미 중간 숫자가 너무 커진 상태이기 때문에 안된다. 중간중간에 나머지를 구하면서 정답까지 가야 하는데 이 때 모듈러 분배법칙을 활용해야 한다.
     (A*B) % p = ((A % p) * (B % p)) % p (a와 b의 관계가 나눗셈만 아니면 다른 연산자도 가능하다.)
8. 탑
   • 주어진 배열을 순회 돌면서 해당 차수 탑보다 왼쪽에 있는 것들을 순회 돌면 O(n^2)이라 시간초과가 날 수밖에 없다. 스택에 해결 안된(정답 안 나온) 탑만 넣어 놓고 그것보다 큰 값이 나와서 정답을 얻게 되면 스택에서 빼버리는 방식이 필요하다. 이런 방식으로 하면 전체를 다 순회 돌 필요 없이 해당 차수에서 아직 정답이 나오지 않은 원소만 검토하면 된다. 스택의 기본은 맨 마지막 원소 말고는 보이지 않는 것이기 때문에 직전 원소만 탐색하게 된다. 그리고 탐색 완료되면 스택에서 제거하는 방식 -> 사실 괄호찾기랑 로직이 거의 똑같다.
9. 크게 만들기
   • 탑이랑 똑같이 스택 쓰는 문제인데 예외 생각을 잘 못했다. 계속해서 '앞자리수>=뒷자리수'여서 while문이 안 끝난다던가, 최소로는 1이 아니라 0이 들어갈 수 있다던가 하는 것들 말이다.
   • slicing도 제대로 못했다. 슬라이싱에 -쓸 때 arr[:i-1] = arr[:0]이 되면 빈 배열이 되니까 조심하자.
10. 가운데를 말해요
    • 입력받을 때 마다 중간값을 위해 정렬하면 너무 오래 걸린다. 최소힙에 중간값보다 큰 애들을 넣고 최대힙에 중간값보다 작은 애들을 넣으면 1,2,...5-6,.....9,10같이 중간값이 힙의 루트에 모여서 금방 알 수 있게 된다.
11. 카드 정렬하기
    • 힙은 넣기만 하면 순서대로 정렬되는게 아니다. 그냥 0번째 인덱스 값이 항상 최솟값일 뿐! 그 뒤의 원소는 크기대로 정렬되지 않는다.
    • 입력값 중 같은 값이 있을 때도 테스트케이스로 고려하자.
12. 철로
    • 정렬을 위해 우선순위큐를 썼는데, 여기서 중요한 건 처음 리스트를 정렬할 때 시작값이 아니라 끝값을 기준으로 정렬하는 것!!이다. 범위에서 벗어나서 제외하는건 l_start 값을 벗어날 때니까 시작점을 기준으로 판단하는게 맞는데, 범위 안에 포함되기 시작하는 건 l_end 값 안에 들어오느냐이니까 끝값이 l_end 이내에 들어오는지 판단하기 위해 끝값 기준으로 정렬해야 놓치지 않을 수 있다.
      예를 들어, [(1,4), (1,4), (2,5), (3,4)]일 때 시작값을 기준으로 큐에 넣다 보면 l이 2~5일 때 (1,4)(1,4) 두개를 큐에서 빼고 나서 (2,5)에서 막히기 때문에 (3,4)는 놓치게 된다.
      큐에 넣을 때 보는 기준은 끝값이 l_end보다 작거나 같냐니까 원래 배열은 끝값 기준으로 최소힙을 만들고, 큐에 넣는건 시작값이 l_start보다 작거나 같냐니까 시작값 기준으로 최소힙을 만들자.
    • 위에서 알 수 있듯이 시작값과 끝값은 완전히 별개로 보기 때문에 큐에 넣을 때 끝값 없이 시작값만 넣어도 된다.
    • 답안이랑 진짜 똑같이 했는데 틀렸대서 세시간을 넘게 고민했는데 문제가 그게 아니었다.. 입력받은 데이터들을 힙에 넣고 시작했는데 시작~끝 거리가 d 이상인 원소들을 미리 지우려고 list comprehension으로 필터링을 했더니 더이상 힙이 아니게 된 것!!! 힙은 내부에 나름의 규칙(2k, 2k+1 어쩌구 인덱싱...)을 가지고 있는데 그걸 내 마음대로 섞어버리니 힙이 아니게 된다. 필터링 한 배열을 다시 heapify로 힙으로 만들어줬더니 제대로 작동했다.
13. 가장 가까운 두 점
    역시나 문제가 너무 간단 심플한 것들은 풀이가 어렵다... 냅다 가까운 점 구하라는 한 줄 뿐이라 도저히 모르겠어서 정답 로직을 좀 봤다.
    • list slicing과 list comprehension은 리스트를 완전히 돌면서 진행하는 메서드라 O(n)이므로 오래 걸린다. 차라리 원래 배열을 그대로 주고 시작 인덱스와 끝 인덱스를 정해줘서 거기서부터 돌게 하자. (list[idx: ]보다는 range(idx, len(list))로 해서 list[i] 하게)
    • 비슷하게, 나는 왼쪽 영역과 오른쪽 영역을 나눌 때 list comprehension으로 만들어서 왼쪽 오른쪽 따로 두번을 돌아야 했지만 그냥 for문 돌면서 조건에 맞는걸 새로운 배열에 추가하면 한번만 돌아도 된다.
    • 그룹을 나누는 데에 순회가 너무 많이 들어갈 바에는 차라리 나누지 않고 돌리는 게 시간면에서 더 이득일지도 모른다. 형인님 코드와 내 코드는 left_close_points를 한번 sort하는 시간밖에 차이가 나지 않지만 입력이 워낙 커서 그런가 미묘한 차이로 시간초과가 나버린다...ㅠ 파이썬의 시간초과 세계는 어렵군.
14. 히스토그램에서 가장 큰 직사각형
    뭔가 코테 보면서 많이 봤던 문제인 것 같은데 의외로 어려운 문제였구나! 난 그동안 노가다로 때려박고 맞는지 확인도 안해서 몰랐나보다.ㅋㅋㅋㅋ
    • 나는 분할한 뒤 합쳐서 분할됐었던 부분의 넓이 구할 때, 기준선 왼/오른쪽 중 낮은 높이로의 최대 넓이를 구했더니 [2, 1, 4, 5, 3, 3, 3] 같은 반례에서는 분할됐을 때 왼/오른쪽에서 구했던 max가 합쳐지면서 연장돼서 더 커질 수도 있다(3*5)는 예외가 생겼었다.
    • 그러면 분할을 리턴할 때, 최대 넓이랑 그 넓이를 만들어낸 높이를 같이 리턴하자고 했더니 [4, 2]처럼 최대 넓이를 만들어낼 수 있는 높이가 여러개일 때는 어떡할 지 알 수 없게 되어버렸다.
    • 원소가 두개일 때는 작은쪽의 높이를 리턴하고, 그보다 클 때는 중복 생각 안하고 리턴했더니 백준의 예제1에서 4~6번째 히스토그램 분할한 걸 리턴할 때 넓이 6 높이 3을 리턴해버렸다. 그런데 그걸 0~3번째랑 합칠 때는 리턴한 높이 3이 왼쪽의 1에 막혀서 아무 소용이 없어진다.
    • 정답은 기준선을 중심으로 왼쪽/오른쪽 중 더 높은 쪽으로 한칸씩 확장하면서 그 때 넓이가 최댓값이면 업데이트하는 것. 분할정복이라고 해서 모든 과정을 분할해야 한다고 생각했는데 그건 아니고 어느 정도 분할하고 나머지는 완탐때려도 된다는 걸 몰랐다. 생각해보면 가까운 두 점도 마찬가지 방식이었다. 기준선 중심으로 나눈 뒤 중심부는 완탐으로 구했는데.