이모저모

병합정렬이 어떻게 이루어지는지를 배웠다. 그 과정에 핵심적으로 작용하는 건 후위순회방식의 DFS였다. 후위순회방식은 언제 쓰이는가 생각해보면, 즉, 각 레벨에서 동일한 패턴의 작업을 해야 해서 재귀를 불러야 하되, 나보다 자식(?)/아래 레벨의 아이들이 먼저 작업을 완료해줘야, 이를 토대로 나의 본연의 일을 할 수 있는 경우. 병합정렬이 이 경우에 해당한다. 왜냐하면 병합정렬은 자신의 왼쪽 오른쪽 아이들이 정렬된 상태로 있어야, 그 양쪽을 합칠 수 있기 때문이다. 즉 더 이상 양쪽으로 쪼갤 수 없을 레벨 (2칸짜리 배열) 까지 깊이 들어가서, 그 친구들이 정렬을 마친 후에야 상위 레벨로 돌아와서, 자식들이 배열을 마쳤다는 안심스러운 토대위에서 자기 레벨에서의 정렬을 진행할 수 있다. 1. 손으로 배운내용..

연습을 안하면 또 까먹고 막막해질까봐 매일 DFS 연습을 해야지 싶다! 손으로 계획 -> 코드쓰기 -> 생각대로 안 되면 디버깅 이 순서대로 반복 공부중인데, 내가 어디서 실수하거나 놓치는지를 발견하게 되어서 아주 뿌듯하다. 📝 이번에 발견한 놓침 포인트 ✔︎ 해당 턴에서 빠져나오면서 다시 자기 턴이 했던 작업을 초기화시켜야 하는 점 (예를 들어 8원을 A에게 주는 작업을 하고 다시 빠져나올 때는 줬던 8원을 다시 뺏어와야 한다.) ❓ 궁금한 점 ✔︎ 나는 이 문제에서 모든 경우를 다 돌고 있는데, 적절히 컷해서 백트래킹할 수 있는 방법은 없을까? 0. 문제 오늘의 문제는 A, B, C 3명에게 N개의 동전을 나누어주는 문제이다. 받은 동전의 총액이 가장 큰 사람과 가장 작은 사람의 차가 최소가 되도록 ..

0. 문제 방 n 개가 주어지고, 각 방의 이름은 0 ~ n-1 이다. 그리고 rooms라는 리스트형 input은 각 인덱스번호인 방에 가면 발견할 수 있는 키들을 나타낸다. example 1로 보면, 0번째 방은 [1] 로 표시되어 있으므로 1번 방에 대한 키가 있는 것이다. example 2로 보면, 0번째 방에는 [1,3]이므로 1번과 3번 방에 대한 키가 있는 것이다. 이렇게 키를 획득해서 다른 방으로 이동할 수 있다. 문제는 주어진 방과 키의 정보를 보고, 모든 방을 다 방문할 수 있는지 판별하는 것이었다. 1. 손으로 생각 2. 코드 - 나는 DFS로 풀었는데, 함께 공부하고 계신 분의 경우에는 queue를 사용해서 푸셨다. 나도 BFS 방식을 많이 연습해야겠다!! class Solution(..

✔︎ 그리디 알고리즘 그리디 알고리즘을 위키백과에서 찾아보면, "여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달"하는 것으로 소개되어 있다. 좀 더 나아가서는 이런 알고리즘이 잘 작동하는 상황이란, 지역적으로도 최적인 것이 전역적으로도 최적인 경우라고 한다. 그렇지 않은 경우도 있다는 것이니 더 공부해봐야겠다..! 일단 지금은 그리디 알고리즘을 본질적으로 이해하고 있지는 않다. 하지만 아마 문제를 풀다보면 개념적으로도 더 와닿는 시간이 오지 않을까 하는 기대를 하면서! 그리디 알고리즘을 적용한다고 하는 문제풀이를 연습했다. ✔︎ 알게 된 점튜플을 원소로 하는 리스트를 정렬하고 싶을 때, 그냥 sort()를 하면 튜플의 첫번..

김태원쌤 알고리즘 강의를 들으면서 계속 연습중인 DFS! 이번 문제는 만약 스스로 해냈다면 참 뿌듯했을 것 같다. 엄청나게 심오하고 어려워서라기보다는, 뭔가 이전까지 배운 것들을 잘 소화해서 긴 호흡으로 문제에 활용해볼 수 있는지에 대한 힘을 확인해볼 수 있었을 것 같다. 오늘의 나는 아직 그런 힘이 너무 부족하지만 계속 계속 공부하다보면 생기겠지!ㅎㅎ 암튼 이 문제는 단순히 DFS로 조합을 생성하는 데에서 더 나아가 그 생성된 조합을 이중 for문 내부에서 사용한다. 지금의 내 수준에서는 뭔가 탄탄하고 풍성한 느낌이 있는 문제랄까. 그래서 공부하는 것만으로도 재미가 있었다. 나중에 다시 보면 아이고 이거 쉬운 거였구나라고 느끼게 되면 좋겠다ㅎㅎ 그래서 요 문제 풀이 흐름, 코드 공부도 열심히 해보았다 ..

이진트리야 친해지자..^^ 재귀를 쓰더라도 부모 자신부터 처리하고 자식레벨로 넘어가는 상황은 조금이나마 직관적으로 받아들이기가 낫다. 그런데 이 문제처럼 아예 리프 노드부터 처리되고 그 리턴값을 받아와서 그걸로 그 상단 노드가 처리를 해야 할 경우가 아직 어렵다..^^ 그래도 요런 아이들도 자꾸 보다보면 익숙해지겠지라는 마음으로 공부공부✍️ 1. 손정리 class Solution(object): def isBalanced(self, root): def DFS(root): if not root: return 0 left = DFS(root.left) right = DFS(root.right) # 균형이 깨졌음을 알려줄 수 있는 세 가지 지표 if abs(left-right) > 1 or left == -1..