폐관코딩

힙이란? 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는 느슨한 정렬상태. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 중복값을 허용한다.(이진 탐색트리와는 다름.) 우선순위 큐, 허프만정렬, 힙정렬 등에서 사용 힙의 종류 1. 최대힙(Max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 key(부모 노드) >= key(자식 노드) 2. 최소힙(Min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완..

트리(Tree)의 개념 트리는 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성 트리는 하나의 루트 노드를 갖고, 루트노드는 0개 이상의 자식 노드를 갖고 있다. 트리에는 사이클(cycle)이 존재할 수 없는 단방향이다. 노드들은 특정 순서로 나열될 수 있다. 트리 관련 용어 루트 노드(root node): 부모가 없는 최상단 노드. 내부(internal) 노드: 부모, 자식이 있는 노드. 단말 노드(leaf node): 자식이 없는 노드. 형제노드(sibling): 같은 부모를 가지는 노드. 간선(edge): 노드를 연결하는 선 (branch 라고도 부름). 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 ..

프로그램 실행 순서 프로그램의 운영체제는 메모리(ram)에 메모리를 할당함 할당해주는 메모리는 총 4가지 이다 . 1. 코드(code) 영역 2. 데이터(data) 영역 3. 스택(stack) 영역 4. 힙(heap) 영역 코드(code) 영역 메모리의 코드(code) 영역은 실행할 프로그램의 코드가 저장되는 영역으로 텍스트(code) 영역이라고도 부른다. CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리함. 프로그램이 시작하고 끝날 때 까지 메모리에 계속 남아있는다. 데이터(data) 영역 메모리의 데이터(data) 영역은 프로그램의 전역 변수와 정적(static) 변수가 저장되는 영역. 데이터 영역은 프로그램의 시작과 함께 할당되며, 프로그램이 종료되면 소멸한다. 힙(heap) 영역 메모리의..

스택(Stack)의 개념 한 쪽으로만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조 메모리의 스택영역은 함수의 호출과 관계되는 지역변수외 매개변수가 저장되는 영역 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸. 컴퓨터의 시간지역성(최근에 참조된 자료가 다시 참조될 확률이 높다는 원리)을 활용할 수 있는 추상적 자료구조 스택(Stack)의 연산 pop: 스택에서 가장 마지막에 입력된 항목을 활용하고 제거한다. push(item): item 하나를 스택의 가장 윗 부분에 추가한다. peek(top): 스택의 가장 위에 있는 항목을 활용한다(삭제 ㄴㄴ). empty(): 스택이 비어 있을 때에 true를 반환한다. full : 스택이 다 차있으면 true반환..