# programmers

inyong_pang

루트 노드의 제거 - 이것이 원소들 중 최대 값트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치자식 노드들과의 값 비교로 아래로, 비교하여 아래로 이동(자식은 둘이 있을 수 있는데 더 큰값을 기준으로 이동)원소 개수가 n인 최대 힙에서 최대 원소 삭제는 자식 노

inyong_pang

이진 트리의 한 종류 (이진 힙 - binary heap)이진힙은 특별한 조건들을 만족하는 이진 트리루트(root) 노드가 언제나 최대값 또는 최소값을 가진다최대값을 가지면 최대 힙(max heap), 최소값을 가지면 최소 힙(min heap)완전 이진 트리여야 한다최

inyong_pang

키(key)를 이용해서 노드를 찾는다만약 해당 키의 노드가 없으면 삭제할 것이 없음노드가 있으면 찾은 노드의 부모 노드도 알고 있어야 함찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리입력 : 키(key)리턴(출력) 삭제한 경우 : True해

inyong_pang

이진 트리의 일종모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족함단, 중복되는 데이터는 없는 것으로 가정데이터 검색하는데 유용탐색법은 이진탐색과 비슷이진 탐색 트리를

inyong_pang

원칙수준(Level)이 낮은 노드를 우선으로 방문같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문, 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야함하나의 노드를 방문했을 때 나중에 그

inyong_pang

size() : 현재 트리에 포함되어 있는 노드의 수를 구함depth() : 현재 트리의 깊이(또는 높이;height)를 구함순회(traversal)깊이 우선 순회(depth first traversal)중위 순회(in-order traversal)전위 순회(pre-o

inyong_pang

정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조모든 노드의 차수(degree)가 2이하인 트리재귀속성이 있음루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리(단, 이 때 왼쪽과 오른쪽 서브트리 또한 이진 트리→ 재귀 속성의 종단 조건

inyong_pang

큐가 FIFO(First-In-First-Out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식대표적인 응용 예로는 운영체제에서 CPU 스케줄러를 구현할 때 현재 실행할 수 있는 작업들 중 가장 우선순위가 높은 것을 골라 실행하는 알고리즘을 들 수

inyong_pang

자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로(asynchronously) 일어나는 경우자료를 생성하는 작업이 여러 곳에서 일어나는 경우자료를 이용하는 작업이 여러 곳에서 일어나는 경우자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에

inyong_pang

자료(data element)를 보관할 수 있는 (선형)구조단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 함 → 인큐(enqueue) 연산꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 함 → 디큐(dequeue) 연산선입선출(FIFO, First-In-First-Out)선형

inyong_pang

(A + B) \* (C + D)연산자가 피연산자들의 사이에 위치AB + CD + \*연산자가 피연산자들의 뒤에 위치후위 표현식을 왼쪽부터 한 글자씩 읽어서피연산자이면, 스택에 push연산자를 만나면 스택에서 pop → (1), 또 pop → (2)(1) 연산 (2)

inyong_pang

연산자가 피연산자들의 사이에 위치(A + B) \* (C + D)연산자가 피연산자들의 뒤에 위치AB + CD + \*중위 (A + B) \* C후위 A B + C \*여는 괄호는 스택에 push닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop→ 괄호안에 있는 내용들

inyong_pang

자료(data element)를 보관할 수 있는 (선형)구조단, 넣을 때에는 한 쪽 끝에서 밀어 넣는다 → 푸시(Push)연산꺼낼 때에는 같은 쪽에서 뽑아 꺼내야 한다 → 팝(Pop)연산후입선출(LIFO, Last-In First-Out) 특징을 가지는 선형 자료구

inyong_pang

양방향 연결 리스트(Doubly Linked Lists) 한 쪽으로만 링크를 연결하지 말고, 양쪽으로! → 앞으로도(다음 node), 뒤로도(이전 node) 진행 가능 노드의 확장 리스트 처음과 끝에 dummy node를 두자 → 데이터를 담고

inyong_pang

insertAfter(prev, newNode)→ 맨 앞에는 어떻게 삽입할까?popAfter(prev) → 맨 앞에는 어떻게 삭제할까?⇒ Dummy Linked List가 필요맨 앞에 dummy node를 추가한 형태길이 얻어내기리스트 순회특정 원소 참조(K번째)원소

inyong_pang

4. 원소 삽입 5. 원소 삭제 6. 두 리스트 합치기 원소의 삽입 def insertAt(self, pos, newNode): pos가 가리키는 위치에 (1 <= pos <= nodeCount + 1) newNode를 삽입하고 성공/실패 에 따라 True/Fa

inyong_pang

Datae.g. 정수, 문자열, 레코드....A set of operations삽입, 삭제, 순회...정렬, 탐색...데이터 원소들을 순서를 지어 늘어놓는다선형 배열(Linear array)와 비슷함선형 배열 : 번호가 붙여진 칸(index)에 원소들을 채워넣어 관리

inyong_pang

문제의 크기와 이를 해결하는데 걸리는 시간 사이의 관계문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계임의의 입력 패턴을 가정 했을 때 소요되는 시간의 평군가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간점근 표기법(asymptotic notat

inyong_pang

n개의 서로 다른 원소에서 m개를 택하는 경우의 수 구하기일반적인 방법재귀적 방법trivial case를 고려해야함크기 순서로 쌓여 있는 원반을 한 막대에서 다른 막대로 옮기기더 큰원반 작은 원반 위에 올릴 수 없음재귀적 방법이 훨신 더 걸린다

inyong_pang

재귀 함수(Recursive Functions) 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것 e.g. 이진 트리(binary trees) 자연수의 합 구하기 1부터 n까지의 모든 자연수의 합을 구하기 재귀 호출의 종결 조건 알고리즘의 종결조