본문 바로가기

재귀5

Leetcode Fibonacci Number 파이썬 풀이 요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다. 문제: Fibonacci Number 등급: Easy 내용: 피보나치 수. 피보나치 수의 개념은 간단하다. 각 숫자들은 앞의 두 숫자의 합이다. 그래서, 011235.... 이렇게 되는 숫자들이다. 간단하게, 그렇다면 f(n) = f(n-1) + f(n-2)를 적으면 되는 것이다. class Solution(object): def fib(self, n): if n< 2: return n return self.fib(n-1)+self.fib(n-2) 그렇다면 이런 코드가 나오게 되어있다. 하지만, 이 코드의.. 2022. 2. 2.
Leetcode Pascal's Triangle II 파이썬 풀이 요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다. 문제: Pascal's Triangle II 등급: Easy 알아낸 점으로는, 구하고자 하는 row의 전 row가 모두 쓰인다는 점이다. 그 전 row의 (i-1, j-1)이 사용된다. 이 점을 활용할수 있지 않을까? 어떻게든 재귀 호출의 방식을 사용하고 싶었다. 어떻게 list를 더하는 방식으로 되지 않을까 생각했는데, 음.. base case를 어떻게 정해야 하나? if rowindex == 0: return [1]이랑 if rowindex == 1: return [1,1]는 맞을 것 같긴한데... 그.. 2022. 2. 1.
Leetcode: Reverse Linked List python 풀이 요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다. 문제: Reverse Linked List 등급: Easy 내용: linked list를 reverse해야한다. 처음 든 생각은, value를 바꾸는 것이었다. 그런데 그러려면 linked list를 array에 저장해서 해야 하는 방법밖에 없을 것 같아서 포기했다. array를 만든다면 linked list의 이점을 포기하는 것 아닌가. 그렇다고 또 다른 linked list를 만들 수는 없지 않은가... 어떻게든 pointer를 바꿔서 해볼까 생각하고 있었다. 그런데 내 머리로는 도저히 안 되는 거였다.. 2022. 1. 28.
Leetcode recursion (재귀): Swap Nodes in Pair 파이썬 풀이 요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다. 문제: Swap Nodes in Pairs 등급: Medium 어떻게 풀어야할까. Recursion을 공부하면서 나온 문제니까, recursive function으로 풀어야 할 텐데.. Guideline으로 적혀있는 것은: 1. 첫 두 개의 노드를 바꾼다 (head and head.next) 2. swap(head.next.next)를 계속 불러서 list의 전체의 노드들의 value가 바뀌도록 한다. 3. 그런 다음 새로운 list의 head를 반환한다. 처음 step은 문제가 없다. (일 줄 알았는데).. 2022. 1. 26.
[Binary Tree / 이진트리] Solve Tree Problems Recursively / Maximum Depth of Binary Tree 요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다. 문제: 오늘은 문제가 아니라, Recursion lesson 등급: --- 두가지 방법, 솔루션이 주어진다. 첫번째는, "top-down" solution. 이렇게 definition이 적혀있다: "Top-down" means that in each recursive call, we will visit the node first to come up with some values, and pass these values to its children when calling the function recursi.. 2022. 1. 20.