WEEK04 알고리즘 4주차 후기

알고리즘의 꽃이라고 하는 dp의 주..... 헬이었다ㅋㅋㅋ
dp라고 해봤자 반복되는 문제의 정답을 메모이제이션 하는 것밖에 없는데 문제는 뭘 메모하냐고?!?!?! 메모야... 아무거나 저장하면 메모 아닌가요.....
근데 비슷한 유형을 여러개 풀다보니까 어느 정도는 메모하는 형식이라던가 방법이 한정되어 있는 것 같긴 하다. 방법을 알겠는건 아니고 정해져있다는 감만 생겼음..ㅎ

1. 피보나치 수2
   • 딕셔너리에 메모이제이션 해놓고 if not memo.get(x-2) 했는데 memo[0]=0이라 not이 붙으면 True가 돼버려서 무한 루프에 빠진다... while 쓸 때 갖가지 조건으로 무한루프에 꽤나 많이 걸리는데 웬만하면 while 쓰지 말자ㅋ
2. 01타일
   • dp에서 입력이 너무 클 때는 top-down(큰 수를 구해야되는데 작은수로 쪼개가면서 재귀로 내려가는 것)은 안된다. recursion error남. for문으로 돌면서 작은 수부터 구해서 위로 올라오자.
3. 동전
   • 이것도 top-down으로 하려고 했더니 겹치는 거 못 빼고 난리가 났다. 그냥 밑에서부터 차근차근 세자.
   • 나는 2, 4원으로 f(8)을 만들려고 f(6)+f(4)를 하려 했는데 그러면 중복이 생긴다. 배열에는 이미 2원과 4원으로 만들 수 있는 갯수가 저장돼 있기 때문에 f(6)도 2원과 4원으로 만들 수 있는 갯수고 f(4)도 2원과 4원으로 만들 수 있는 갯수이기 때문이다. 이전까지는 이미 가진 동전을 전부 써서 만들 수 있는 갯수가 저장돼있으므로 거기에다가 지금 동전만으로 만들 수 있는 경우의 수를 더해야 한다. 그냥 f(x-price)면 안되고 지금 동전에서의 f(x-price)여야 하는 것!
   • top-down으로 풀려면 마지막 동전 빼고 x원을 만들 수 있는 수 + 마지막 동전 포함해서 (x-아까 뺀 동전금액)원을 만들 수 있는 수여야 한다. 결국 탑다운이어도 점화식은 똑같네. 저장하는 방식만 sum값으로 1차원 배열에 저장하냐 누적합처럼 2차원 배열에 저장하냐인 것. 핵심은 "a,b,c원으로 x원을 만들고 싶으면 c 없이 a,b만으로 x원을 만든 개수+무조건 c를 하나 미리 배정해두고 x-c원을 만들 수있는 개수"를 구하면 되는 것. [탑다운 코드]
4. lcs
   • 다시 한번 재귀보단 반복문!
   • 최장부분수열 유명하니까 방법 잘 알아놓자. 매번 외울순 없다. 제일 끝자리 비교해서 같은지 다른지에 따라 끝자리 제거하는거랑, 그걸 2차원 배열로 저장하는 것.
5. 행렬곱
   • 내가 생각한 로직이 틀렸다. 두개를 곱했을 때의 결과값이 제일 작은것부터 골라서 곱하는 걸로 생각했는데 반례를 찾아버렸다: (1,1)(1,1)(1,2)
   • 이차원 인덱스 지정하는게 어렵네..
6. 가장 긴 증가하는 부분 수열
   • ㅈㄴ 열심히 햇는데 정답 풀이 세줄임....... 허무,, 앞으로 적당히 해보고 안 풀리면 그냥 답 보자... 다들 나보다 똑똑하다..
7. 회의실
   • 그리디는 보통 정렬이랑 같이 간다. 지금 당장의 문제를 해결해나가면 전체 문제가 해결되어야 하는데 그러려면 순서대로 봐야하기 때문!
8. 점프
   • 도저히 내 머리로는 생각해 낼 수 없었던 문제.. 2차원 배열에 각 돌마다 도착 속도별 점프 횟수를 저장해놓기. 그리고 다음 돌에서 속도 x로 도착할 때의 점프 횟수는 지금 돌에서 x만큼 이전 돌에서 속도가 x-1, x, x+1이었을 때이다. 이걸 어케알아ㅠ0ㅠ 심지어 최대 속도는 속도가 1씩 계속 증가해서 N에 도달했을 때의 속도를 구해야해서 등차수열 식을 써야 한다. 구하면 N어쩌구-k어쩌구가 나오는데 k가 최대속도니까 이 식이 결국 N어쩌구보다는 작거나 같다는 결론이 남... 근데 그걸 이제 처음 2차원 배열 만들때에는 n에 도달했을 때지만 각 돌마다 가능한 최대 속도는 돌 번호를 넣어서 구해야 하는... 하 시바 이거 생각해서 푸는 사람이 있다고??? 난 알고리즘 2년을 해도 못 풀듯 ㅈㄴ자괴감 지린다..
9. 외판원 순회
   • dp+dfs+비트마스킹의 총집합체... 이긴 한데 dp테이블에 뭘 저장할지만 알면 구현은 어렵지 않았다. 다들 답을 보고도 이해하길 포기했다고 하길래 지레 겁 먹고 있었는데 디버깅도 별로 안하고 맞췄다. 근데 "도착지점별 visited에 따른 최소비용"을 저장할지 어떻게 아냐고????? ....... 많이 풀다보면 감이 생기려나

실력 테스트

전 날 외판원 혼자서 금방 풀고 오ㅎ 혹시 나 개천재??!? 했는데 응 아니었다..ㅎ dp 테이블에 뭘 저장할지만 알면 된다니 그걸 생각해내지 못하면 어차피 0점인걸!! 맨날 아이디어 참고만 하고 구현은 스스로 했다고 풀었다고 생각하는데 그건 푼게 아니다. 실제 시험에서는 아이디어를 생각해내지 못하면 말짱꽝인데 뭐가 푼거야.. 내가 지금 두문제 풀었다고 좋아하고 잘한다고 생각할 때가 아니다 너도 0점이나 마찬가지야....... 제일 쉬운 게임판에 dp 테이블 쓸 생각도 안하고 while문으로 했을 때는 시간초과 났었잖아...
3주차도 찬스 없었으면 1문제, 4주차는 0문제다... 아이디어 떠올리는 것도 시간초과 해결하는 것도 실력이다. 겸손해지자 채림아!!

1. 점프
   • dp 테이블을 쓸 때는 재귀나 스택 쓸 생각하지 말고 for문 돌면서 한 칸씩 채워가는게 시간상을 제일 유리하다. 그리고 사실상 나는 처음에 dp 쓸 생각도 안하고 dfs로 풀고있었음..
   • 채림아.... 스택 쓸 때는 경계값 확인해야 무한루프 돌아서 시간초과 나는 일 없다니까..... 칸에 적혀있는 수가 0부터 가능한데 지금 있는 칸에 적힌 수만큼 오른쪽/아래쪽으로 움직여서 스택에 넣으니까 계속 같은 값이 들어가서 안끝남.
   • 내 눈으로 계산하는 시간복잡도는 똑같더라도 메모이제이션으로 배열에 저장하고 불러오는 것 보다 큐에 넣고 빼는게 오래 걸리니까 시간이 더 걸림. 그래서 dp가 더 빠르다!!
2. 강의실
   • 제일 일찍 끝나는 강의실을 찾아야 하는데 나는 for문 돌면서 계속 갱신해서 시간초과. 작은거니까 우선순위 큐를 생각했어야 한다. 이거 말고는 정렬 순서만 문제였다. 일찍 끝나는지는 이미 우선순위 큐로 해결됐으니 시작시간으로 정렬했어야 함.
3. 판다
   • 뭐야...? 쥐언니 코드 보고 이 언니 개천재인가 싶음... visited 배열이랑 dp 배열을 하나로 합쳐버렸네.. 방문 안한건 -1 방문했으면 0 나머지 dp는 자연수로......... 미쳤다 이게 재능이라는 걸까 배워서 아는건가.. 갑자기 자괴감 오지고 지리는 밤. 이게 코치님이 말한 그런거구나 ..........
   • 처음에 방문처리할 때 1을 넣어주고 dfs를 도는게 아니라 0을 넣고 dfs 돈 다음에 1을 더하는 이유는 처음부터 1을 넣어주면 max값 비교하면서 그 넣은 1이 날라가기 때문. 이 칸은 무조건 갈 수 있어서 호출된거니까 dfs 부른거에서도 1이 추가되어야 한다. dfs 부르고 나서 +1 추가해주면 해결됨!!!