[학부]자료구조/알고리즘

개요 알고리즘 > 주어진 문제를 유한한 시간 내에 해결하는 단계적 절차 데이터 구조 > 데이터를 조직하고 접근하는 체계적 방식 프로그램 알고리즘 + 데이터 구조 의사코드 > 알고리즘을 설명하기 위한 고급 언어 자연어 문장보다 더 구조적, 프로그래밍 언어보다 덜

알고리즘 자신을 사용하여 정의된 알고리즘비재귀적 알고리즘과 대비됨보류된 재귀호출을 위한 변수들에 관련된 저장/복구→ 컴퓨터에 의해 자동적으로 수행장점 : 복잡한 문제를 적은 양의 코드로 가독성 좋게 서술 가능단점 : 컴퓨터 성능부담재귀 케이스베이스 케이스아래 규칙을 따

고급 데이터 구조를 구축하는데 사용 가능한 데이터 구조로, 비교적 구체적이다.순차 기억장소에 할당된 유한 개수의 동일 자료형 데이터 원소들배열명 V배열크기 N : 원소를 저장하는 셀 개수배열첨자 i시작첨자 : LB 또는 0끝첨자 : UB 또는 N-1배열원소 V\[i]배

( 의사코드의 실제 구현은 c로 하였음 ) 리스트 ADT > 연속적 임의 개체들을 모델링하는 추상자료형 = 원소들의 순서 집단을 저장하기 위한 기초적이고 일반적 목적의 데이터 구조 순위(r : rank) 특징 : 해당 원소 앞의 개수를 특정하는 수단 쓸모 : 원소(

각각 상이한 카테고리에 속하는 데이터원소들을 표현하기 위한 자료구조.리스트ADT를 확장하여 구현.레코드의 리스트구조체의 1차원배열로 구현이중연결리스트로 구현부리스트의 리스트2차원배열로 구현이중연결리스트의 배열로 구현레코드 : 몇 개 필드의 복합으로 이루어진 원소방법 :

공유 > 상이한 그룹에 의해 공유되는 데이터 원소들을 표현하기 위한 자료구조 리스트ADT를 확장하여 구현 공유의 예시 그룹 x y와 원소 a b c가 있다고 할 때, 아래와 같이 한 원소가 2개이상의 그룹에 속한 경우를 다룬다. |원소|속한 그룹| |:-:|:-:|

유일한 개체들을 담는 자료구조를 모델링집합을 집합 원소들의 정렬된 리스트로 표현집합A에 대한 집합연산 : $$O(|A|+|B|)$$를 만족해야 함.이 연산은 파괴적일수도, 비파괴적일 수도 있음.set union(B) : A∪Bset intersect(B) : A∩Bse

개요 top에서 후입선출(LIFO)로 삽입/삭제가 이루어지는 ADT 메소드 push(e) : 삽입 element pop() : 가장 최근에 삽입된 원소 삭제 후 반환 element top() : 가장 최근에 삽입된 원소 반환 integer size() : 저장된 원소

선입선출(FIFO)순서에 따라 삽입 삭제가 일어나는 ADT삽입은 뒤(Rear)에서, 삭제는 앞(Front)에서 수행enqueue(e) : rear에 원소 삽입element dequeue() : front쪽 원소 삭제 후 반환element front() : front쪽

계층적으로 저장된 데이터 원소를 모델링루트 원소는 0개의 부모, 0개 이상의 자식을 갖는다.루트가 아닌 원소는 1개의 부모, 0개 이상의 자식을 갖는다.노드루트 : 부모가 없는 노드내부 노드 : 1개 이상의 자식이 있는 노드외부 노드(리프 노드) 자식이 없는 노드형제(

상호배타적인(교집합이 없는) 집합을 모델링 \--> 집합 ADT의 특화set find(e) : 원소 e가 속한 집합 반환union(S1, S2) : 집합 S1, S2 합집합 수행int size(S) : 집합S의 크기(원소 개수) 반환구성요소3개의 집합 A={0,1,4,

(key, element) 쌍을 저장insertItem(k, e)element removeMin() : 최소 키를 가진 원소 삭제, 반환integer size()boolean isEmpty()element minElement() : 최소 키를 가진 원소 반환elemen

내부노드에 key를 저장하고 외부노드에는 key가 없는 이진트리다음을 만족해야 한다.힙 순서 : 루트를 제외한 모든 내부노드 v에 대해 최소힙이면 key(v) ≥ key(parent(v))최대힙이면 key(v) ≤ key(parent(v))완전이진트리 : 각 깊이(0,

분할통치법 (분할정복, divide-and-conquer) 세 단계를 통해 문제를 해결한다. 분할 : 문제를 여러개로 분할 한다. 재귀 : 분할된 개별 문제에 대해 재귀한다. 통치 : 재귀로 해결된 개별 문제의 답을 합쳐 전체 문제의 답을 구한다. 합병정렬 분할통치

탐색 가능한 형태의 (key, element)쌍 항목의 모음무순사전과 순서사전으로 분류integer size()boolean isEmpty()element findElement(k)insertItem(k, e)element removeElement(K)유일키 : 한 개

내부노드에 키,원소 쌍 저장하는 적정 이진트리어떤 원소 v에 대해key(v.left) <= key(v) <= key(v.right)중위순회 하면 키가 증가하는 순서로 방문함.n개 항목이 있다고 하면높이 h : 최악의 높이 O(n), 최선의 높이 O(logn)

해시테이블 키-주소 매핑으로 구현한 사전 ADT 구성요소 버켓 : 키-원소 쌍, 또는 NoSuchKey를 담는 공간. 버켓 배열의 각 셀 버켓 배열 : 버켓의 집합. (e.g., 크기 M의 배열) 해시 함수(h) : 주어진 키를 고정 범위로 매핑하는 함수 해시코드

내용 그래프 개요순회 (DFS, BFS)방향그래프 (강연결, 이행적폐쇄, 플로이드 워셜, DP, DAG, 위상정렬)최소신장트리최단거리 (다익스트라, 벨만포드)정점(Vertex)의 집합 V, 간선(Edge)의 집합 E가 있을 때(V, E)쌍을 그래프(Graph)라고 한