바위타는 두루미

문제 이진 탐색 트리에서 주어진 노드의 '다음' 노드( 중위 후속자 ) 를 찾는 알고리즘을 작성하라. 각 노드에는 부모 노드를 가리키는 링크가 존재한다고 가정하자. 해결법 이진 트리에서 중위 후속자를 찾는방법 1. 오른쪽 노드가 있다면 오른쪽 노드의 가장 왼쪽 노드 2. 오른족 노드가 없다면 현재 노드가 왼쪽 노드일때까지 부모를 타고 올라가기 def get_left(node): while node.left is not None : node = node.left return node def Solution(node): if node is None : return None if node.right is not None : return get_left(node.right) else : cur = node p ..

문제 주어진 이진트리가 이진 탐색 트리인지 확인하는 함수를 작성하라. 접근법 1. 중위순회를 이용하여 배열의 원소를 저장해두고 이것이 정렬된 결과인지 확인한다. -> 중복된 값이 있을때 재대로 동작하지 않을 수 있다. 사실, 배열에 저장한다고 해도 바로 전의 원소와 그다음 원소만 사용하기 때문에 굳이 배열이 필요없음을 알 수 있다. 2. 마지막으로 검사했던 원소만 저장해두고 순회하며 그 다음 원소와 비교한다. last = float("Inf") def chkBST(root): if root is None: return True if not chkBST(root.left) : return False if last != float("Int") and last >= root.data : return False..

문제 이진 트리가 균형 잡혀있는지 확인하는 함수를 작성하라. 이 문제에서 균형 잡힌 트리란 모든 노드에 대해서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미한다. 해결법 재귀적으로 각 노드까지의 높이를 확인하며 1이상의 차이가 나는지 확인하고, 1 이상의 차이가 나지 않는다면 높이를 반환해 나가며 균형이 잡혀있는지 확인한다. def chkHeight(root): if root is None : return -1 left = chkHeight(root.left) if left == float("Inf") : return float("Inf") right = chkHeight(root.right) if right == float("Inf") : return float("..

문제 이진 트리가 주어졌을 때 같은 깊이에 있는 노드를 연결리스트로 연결해 주는 알고리즘을 설계하라. 즉, 트리의 깊이가 D라면 D개의 연결리스트를 만들어야한다. 접근법 재귀를 이용한 전위탐색으로 해결하거나, BFS로 해결이 가능하다. 두 방법모두 비슷한 탐색법이지만, 재귀를 이용한 전위탐색은 탐색시 logN만크의 추가공간을 요구한다. 하지만 어쩌피 return할때 무조건 N만큼 공간을 차지하기 때문에 N에 비교하면 logN은 많은 공간이 아니고, 공간 효율성 측면에서는 두 방법모두 O(N)이다. 아래 코드는 BFS로 탐색하여 해결한 코드 def Solution(root): level_list = [] current = [] if root is not None: current.append(root) wh..

문제 오름차순으로 정렬된 배열이 있다. 이 배열 안에 들어 있는 원소는 정수이며 중복된 값이 없다고 했을때 높이가 최소가 되는 이진탐색트리를 만드는 알고리즘을 작성하라. 접근법 이진탐색트리는 '모든 왼쪽 자식들

문제 가장 작은 값이 위로 오도록 스택을 정렬하는 프로그램을 작성하라. 추가적으로 하나 정도의 스택은 사용해도 괜찮지만, 스택에 보관된 요소를 배열 등의 다른 자료구조로 복사할 수는 없다. 스택은 push, pop,peek,isEmpty의 네가지 연산을 제공해야한다. 접근법 정렬을 위한 스택을 하나 더 사용한다고 했을떄, 두번째 스택에는 정렬된 형태로만 들어갈 수 있도록 하여 해당 값이 들어갈 위치를 찾아주는 방식으로 해결 할 수 있다. class SortStack : def __init__(self): stack = [] def sort(self): tmp_stack = [] while stack : cur_num = stack.pop() if not tmp_stack or tmp_stack[-1] >..

문제 스택 두개로 큐 하나를 구현한 MyQueue 클래스를 구현하라 접근법 q1, q2가 존재하고 push를 하면 q1에 넣는다. pop를 부르는 순간, p1에서 p2에 순차적으로 pop하고 push한다. 그리고 p2에서 pop하면 가장 먼저 들어간 데이터가 먼저 나올 것이다. (FIFO) class QueueByStack : def __init__(self): s1 = [] s2 = [] def push(self, num): sl.append(num) def pop(self): if not s2 : while s1 : s2.append(s1.pop()) return s2.pop()

문제 기본적인 push와 pop기능이 구현된 스택에서 최솟값을 반환하는 min함수를 추가하려고한다. 어떻게 설계할 수 있는가? push, pop, min 연산은 모두 O(1)시간에 동작해야한다. 접근법 1. minValue 변수를 두고 minValue가 제거되면 다음 minValue를 탐색한다. -> push와 pop이 O(1)에 연산이 불가능 2. 스택에 각 상태값(minValue)를 함께 저장해두기 class MinStack : def __init__(self): stack = [] def push(self, num): if len(stack) == 0 : stack.append((num, num)) else : cur_min = min(stack[-1][1], num) stack.append((nu..

문제 순환 연결리스트(Circular linked list ) 가 주어졌을때, 순환되는 부분의 첫째 노드를 반환하는 알고리즘을 작성하라. 순환 연결리스트란 노드의 next포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는, 엄밀히 말해서는 변질된 방식의 연결리스트를 의미한다. 해결법 해법에 있는 해결법은 Runner 기법을 이용해 해결하는데 독특해서 그대로 가져와봤습니다. 1. 연결리스트에 루프가 있는지 검사 FastRunner와 SlowRunner가 각각 2칸씩 1칸씩 이동한다면 루프가 있다면 언젠가 충돌한다. 2. 언제충돌하지? 루프가 아닌 부분의 크기가 K라고 했을때, SlowRunner가 루프에 진입하기 시작하는 순간은 K번 움직인 순간이고 그순간에 FastRunner는 두배를 움직..

문제 단방향 연결리스트 두개가 주어졌을때 이 두리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 첫번째 리스트에 있는 k번째 노드와 두 번째 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소가 된다. 해법 교집합의 유무를 판별하기 위해서는 우선 각 리스트의 마지막노드가 같아야하고, 같은 길이의 출발점에서부터 순차적으로 탐색을 했을때 동시에 방문하는 노드가 같은 점이 잇어야한다. 1. 각 연결리스트를 순회하면서 길이와 마지막 노드를 구한다. 2. 길이가 긴쪽의 리스트에서 짧은쪽과의 차이만큼 시작포인터를 옮긴다. 3. 두 포인터가 같아질때까지 두 리스트를 함께 순회한다. def lengt..