재귀 함수

9/26 (화) 이진 트리 후위 순회 구현 TIL

공부한 것LeetCode #145. Binary Tree Postorder TraversalLeetCode - The World's Leading Online Programming Learning PlatformLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/binary-tree-postorder-traversal/description/후위 순회(Postorder traversal): ‘나’와 두 자식을 기준으로, “왼 자식 → 오른 자식 → 나” 순..

9/25 (월) 이진 트리 전위 순회와 중위 순회 구현하기 TIL

공부한 것LeetCode #144. Binary Tree Preorder TraversalLeetCode - The World's Leading Online Programming Learning PlatformLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/binary-tree-preorder-traversal/description/전위 순회(Preorder traversal): ‘나’와 두 자식을 기준으로, “나 → 왼 자식 → 오른 자식” 순으로 ..

9/12 (화) 재귀를 스스로 풀다 TIL

공부한 것LeetCode #1448. Count Good Nodes in Binary TreeLeetCode - The World's Leading Online Programming Learning PlatformLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/count-good-nodes-in-binary-tree/⇒ 어제에 이어서 스스로 풀어본 해답이 통했다! (스택을 이용한 해답은 다른 사람들의 해답을 참고함.) 재귀를 이용한 DFS도, 스택을 ..

9/11 (월) 트리 심화 TIL

공부한 것LeetCode #1448. Count Good Nodes in Binary TreeLeetCode - The World's Leading Online Programming Learning PlatformLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/count-good-nodes-in-binary-tree/ Uploaded by N2T

9/8 (금) 이진 탐색 트리(BST)인지 검증하라 TIL

공부한 것LeetCode #98. Validate Binary Search TreeLeetCode - The World's Leading Online Programming Learning PlatformLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/validate-binary-search-tree/description/재귀함수가 이렇게 간단한 형태가 될 수도 있다: function isValidBST(root: TreeNode | null, min ..

9/7 (목) 이진 탐색 트리(BST)의 특징을 이용한 문제 TIL

공부한 것LeetCode #235. Lowest Common Ancestor of a Binary Search TreeLeetCode - The World's Leading Online Programming Learning PlatformLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/BST는 부모 노드의 값이 왼쪽 서브트리에 있는 모든 노드의 값..

9/6 (수) 계속하여 재귀함수 TIL

공부한 것LeetCode #543. Diameter of Binary TreeLeetCode - The World's Leading Online Programming Learning PlatformLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/diameter-of-binary-tree/description/트리의 최대 깊이를 구하는 문제에 살짝 변주를 준 문제였다. Uploaded by N2T

9/5 (화) 재귀함수와 백트래킹 TIL

공부한 것오늘은 재귀함수에 대한 유튜브 강의를 듣다가 백트래킹(Backtracking)이라는 용어가 나오길래 정확히 어떤 건지 궁금하여 찾아보았다. 백트래킹(Backtracking, 퇴각검색)길이 여러 갈래로 나뉘어진 재귀호출이다. 가능한 모든 경우의 수를 낱낱이 탐색할 때 사용한다. 주로 다음과 같은 경우에 백트래킹을 적용한다: 일정한 크기의 조건들이 주어지고, 그 안에서 완전탐색을 통해 최적비용 또는 최적경로를 탐색해야 하는 경우.각 조건에서 선택할 수 있는 경우의 수가 정해져 있을 경우 (이차원 배열 등)예제 1) 주사위 던지기: 주사위를 N개 던져서 나올 수 있는 경우의 수를 모두 출력하기코드: // 주사위를 N번 던진 결과의 모든 조합을 배열 형태로 출력하기. // 예를 들어 3번 던진 결과는 ..

9/1 (금) 트리 문제 기초 접근법을 3가지로 정리하다 TIL

공부한 것LeetCode #226. Invert Binary TreeLeetCode - The World's Leading Online Programming Learning PlatformLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/invert-binary-tree/description/트리를 뒤집어 반환하는 문제이다. 각 노드별로 좌우 자식을 바꿔주면 되고 이는 결국 노드를 전부 방문해야 한다는 얘기가 된다. 기초적인 전위 순회(Preorder ..

8/17 (목) 오버로딩 안되는 JavaScript의 메소드와 속성 TIL

공부한 것LeetCode #61. Rotate List (링크드 리스트 회전시키기)를 풀었다.Abdul Bari의 유튜브 강의 中 Dividing function로 표현된 재귀함수 점화식의 시간복잡도를 구하는 master’s theorem을 짧게 공부하였다. (Master’s theorem이란 한 마디로 마법식 같은 것이었다. 미적분의 기본 정리, 페르마의 정리처럼 해법의 패턴을 정리해놓은 정리이다.) 알게 된 것JavaScript에서 클래스에 같은 이름의 속성과 메소드를 동시에 만들 수 없다는 것을 알았다. 예를 들면 다음과 같은 클래스에서: /** * 주어진 singly-linked list의 정의는 다음과 같다: */ class ListNode { constructor(val, next) { thi..

8/16 (수) 링크드 리스트와 재귀함수 점화식 TIL

오늘 공부한 것그동안 LeetCode에서 문제를 풀었다. 아래 로드맵에서 보는 바와 같이 Array와 Hash map, Two pointers, Stack, Binary search, Sliding window의 주제를 골라 풀었고, 지금은 Linked list 문제들을 푸는 중이다. 푼 문제는 LeetCode에 제출되어있고 테스트 코드와 세트로 로컬 js 파일로 저장되어 있으며 최근 들어서는 깃헙에도 세트로 푸시하고 있다. LeetCode의 discussion 섹션에서 추천받은 재귀함수 유튜브 강의를 듣고 있다. Recurrence Relation(점화식)의 형태에 따른 알고리즘의 시간복잡도를 계산하는 방법을 가르쳐준다. Uploaded by N2T

11/24 (재귀 함수와 쪼끔 더 친해진, 목) TIL

BFS 탐색을 실제로 활용하는 문제를 하나 풀었다. 나 스스로는 재귀 호출 쪽으로 생각해보다가 풀지 못했던 문제이다. “너무 경우의 수가 많을 것 같은, 말하자면 재귀로 돌려야 할 것 같은데 분기가 너무 많아지는 것 같다 싶은 문제인 경우, 모든 경우의 수를 다 나열해야겠구나싶은 경우”에 BFS를 사용하면 된다고 한다..! 주어진 트리나 그래프의 자료 정보가 없는데 어떻게 가능했던 건지는, 이전에 한 번 적어봤던 BFS 탐색 코드와 비교해가며 좀 더 연구해봐야겠다. DFS에는 스택! BFS에는 큐!파이썬에서 스택은 list로 쓰고, 파이썬에서 큐는 collections.deque을 쓰고, 파이썬에서 최소힙(과 최대힙)은 heapq로 구현되어 있는 걸 쓰면 된다. 어제 저녁까지 고민하던 문제(’영화관 좌석..