이모저모

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

이것도 인프런 김태원t 의 알고리즘 강의에서 제시되는 문제! DFS를 실컷 연습할 수 있어서 정말 좋다ㅎㅎ 이 강의 너무 감사하다💚 이번 문제도 손으로 정리 먼저하고 그 다음 코드를 써봤다. 역시나 계획단계에서 놓쳤던 점이 있었는데, 좌우에 대한 이동 후에는 방문처리를 했지만, 위로 올라간 경우에 대해서는 방문처리를 안해주었던 점이다.ㅎㅎ 이렇게 나는, 경우들을 나누다보면(혹은 우선순위에 따라 코드를 구분지어야 되게 되면..?), 동일하게 해주어야 할 처리들인데도 빼놓는 것 같다. 앞으로는 나누어진 경우더라도 동일하게 처리해야 할일이 무엇인지 짚어보는 것도 좋겠다 싶다. board = [ [1,0,1,0,0,1,0,1,0,1], [1,0,1,1,1,1,0,1,0,1], [1,0,1,0,0,1,0,1,0,..

먼저 손정리! def solution(numbers, target): count = 0 def DFS(L, S): nonlocal count if L == len(numbers): if S == target: count += 1 return else: DFS(L+1, S + numbers[L]) DFS(L + 1, S - numbers[L]) DFS(0, 0) return count

📝 알게 된 점이자 더 알아봐야 할 점 처음에는 path_set이라고 명명한 set에 원소로서 좌표쌍의 set을 넣으려고 했는데 type error였다. 살짝 찾아보니 set의 원소로서 set이나 list같은 자료형은 불변자료가 아니라서 사용할 수 없는 것 같았다. 일단 이 문제를 풀 때는 튜플을 원소로 쓰고 대신 양방향 처리를 위해서 쌍의 위치를 뒤집어서도 한 번 더 저장했다. 더 좋은 방법이 있는지 알아봐야겠고, 자료형의 특성에 대해서도 공부해야겠다. def solution(dirs): x = 5 y = 5 path_set = set() for i in range(len(dirs)): tmp = (x, y) if dirs[i] == "U": if x-1 >= 0: path_set.add((tmp, (..