이모저모

처음 문제를 봤을 때, 맨 앞자리가 큰 것을 우선 앞에 가져와야겠다 라는 것은 단순하게 생각할 수 있는데, 그 다음을 비교하는 과정이 잘 안 그려졌다. 고민을 하다가, 그래 한 번에 다 해결하지 못한다면, 작게 시도할 수 있는 첫 작업이라도 먼저 해보자 싶었다. 그래서 우선 "앞자리가 큰 아이들부터 앞쪽에 다 모여!" 이런 식으로 해놓았다. 그러고 나니, 이제는 앞에 자리가 큰 친구들끼리는 서로 앞 뒤를 바꾸어 조합해보면서 더 큰 경우가 되도록 스왑해주면 되겠다고 생각했다. 그래서 결국 나는 두 번의 정렬을 사용하게 되었는데, 사실 문제를 푸는 데 첫 번째 정렬은 꼭 필요하지는 않다. 그래도 문제가 복잡하게 느껴지던 차에 조금 더 도움을 준 친구니까 나에게는 살짝 고마운 단계였다...!ㅎㅎㅎ 그래도 불필..

# bottom-up n = 7 dy = [0] * (n+2) dy[1] = 1 dy[2] = 0 for i in range(3, n+2): if i == 5: dy[i] = 0 else: dy[i] = dy[i-1] + dy[i-2] print(dy[n+1]) # top-down visited = [0]*(n+2) # for memoization def DFS(nth: int): if nth == 1: return 1 if nth == 2: return 0 if nth == 5: return 0 else: if visited[nth] != 0: return visited[nth] else: visited[nth] = DFS(nth - 1) + DFS(nth - 2) return visited[nth] ..

이렇게 풀어볼까 했던 생각 t인 시점에, t보다 작거나 같은 요청시점을 가진 작업 중에서, 소요시간이 짧은 것부터 정렬하자 - 였다. 어차피 자신의 소요시간만큼은 자신의 대기시간에 추가될텐데, 그 피해를 다른 작업에게 최소화하기 위해서는, 그나마 소요시간이 짧은 아이들이 앞서서 처리되는 게 좋겠다고 생각했다. 문제 풀이를 위한 말-계획 # 이전 작업의 종료시점을 정한다.(초기에는 0) # 그 종료시점보다 작거나 같은 요청시간을 가진 작업들을 불러온다. # 그 작업들을, 소요시간(job[1])을 기준으로 heap에 넣는다. # 소요시간이 작은 것부터 꺼내서 # 작업 상황을 업데이트 하는데 => 이 때 할 일들에는 # 1) 이전 작업의 종료시점에다가, 현재 힙에서 꺼낸 친구의 소요시간 job[1] 을 더해..

앞에서 풀었던 문제(네트워크 선 자르기)를 재귀로도 풀 수 있다!! 진짜 재미있다..!!ㅎㅎㅎ 이 접근 방식이 동적 계획법으로서의 빛을 발하는 부분은 "메모이제이션 memoization"이다. 동일한 계산을 반복하지 않도록, 이전에 계산한 값을 저장해두는 것으로, 이 문제에서는 불필요한 재귀의 호출을 방지해준다. 재귀를 열심히 연습하면서 종종 내가 너무 모든 경우를 다 돌고 있다는 느낌이 들고는 했는데, 이번에 이걸 배우고 나니 다른 재귀문제를 풀 때도 메모이제이션을 통해 엣지를 탁탁 컷해보고 싶다는 생각이 든다!ㅎㅎ 1. 손 정리 2. 코드로 써보기 n = 7 # 메모이제이션을 위한 공간! 이 리스트의 인덱스번호에 해당하는 길이를 몇 가지 방식으로 자를 수 있는지 구하면 거기에 값을 넣어두기. # 또 ..

재미있다..! 뭔가, 겸손한 방법 같아서(?) 매력적이다..!ㅎㅎ n = 7 dy = [0] * (n+1) dy[1] = 1 # 직관적으로 알 수 있는 작은 단위에 대한 결론을 먼저 짓고. dy[2] = 2 for i in range(3, n+1): dy[i] = dy[i-2] + dy[i-1] print(dy[n])

0. 병합정렬 vs 퀵정렬 퀵 정렬(quick sort)을 공부했다! 이건 병합정렬처럼 재귀적 구조를 가지기는 하지만, 확연히 다른 점이 있다. 바로 "전위순회방식"을 취한다는 점. 즉 자기 레벨에서 지정된 피봇으로 해야 할 작업을 모두 다 진행한 후에! 그래서 피봇이 자기 자리를 땅땅!! 확신한 후에! 이제 피봇위치 기준 좌우로 잘라서 자식들을 만들고, 그 자식들/아래 레벨들에 대해서도 다시 피봇을 설정해 같은 작업을 반복하도록 재귀적으로 호출해주는 것이다. 병합정렬의 경우에는 자식이 처리를 다했어야 자신이 할 일을 할 수 있었던 "후위순회방식"과 대조를 이룬다. 1. 손으로 하는 공부 시간을 꽤 들이기는 했어도, 나의 머리에 좀 더 우직히 퀵 정렬이 자리잡기를 바라는 마음으로 🤓📝 2. 코드 arr ..