알고리즘
-
스레드 이진 트리 (Threaded Binary Tree)개인 공부/알고리즘 2021. 10. 10. 01:47
* 참고: https://youtu.be/AndqtbiTfe8 1. 기존 이진 트리의 문제점 왼쪽 자식, 값, 오른쪽 자식을 저장하는 일반적인 이진 트리의 경우 대다수의 포인터(n+1)들은 null을 가리키고, 이는 메모리의 낭비를 일으킨다. 이런 이진 트리의 순행하기 위해서 스택 또는 큐가 필요한데, 이 역시 많은 저장공간을 필요로 하게 된다. 이를 해결하기 위해 우리는 스레드 이진 트리를 사용한다. 2. 스레드 이진 트리의 특징 스레드 이진 트리는 널 포인터 대신 의미 있는 정보들을 저장한다. 운행을 위해 스택 또는 큐를 사용하지 않는다. 이때 의미 있는 정보들이란 중순위 선행/계승 정보를 가리킨다. 왼쪽 null 포인터는 선행 노드를 가리키고 오른쪽 null 포인터는 계승 노드를 가리키도록 한다. ..
-
[LeetCode] Climbing Stairs개인 공부/알고리즘 2021. 5. 18. 01:56
Climbing Stairs 처음으로 직접 맞힌 동적 프로그래밍 문제...!!!!!!!😭😂 class Solution { public int climbStairs(int n) { int [] counts = new int[n+1]; counts[1] = 1; if (n > 1) counts[2] = 2; for (int i = 3; i 1 2 -> 2 3 -> 1+1+1 / 1+2 / 2+1 4 -> 1+1+1+1 / 1+2+1 / 1+1+2 / 2+1+1 / 2+2 ... 그리고 나열한 것들을 뚫어지게 쳐다봤다..^-^.. 1+1+..+1 제외하면 바로 전이랑 관련이 있나 생각해봤다. (답은 아니지만 암튼 그렇게도 생각해봤다.) 내가 나열한 목록은 순서 없이 마구잡이로 나열된 것이라는 생각이 들었다. ..