Data Structure

큐: 선입선출, 먼저 들어온 데이터가 먼저 나가는 자료구조 전단: 삭제위치, 후단: 삽입위치 선형큐 큐의 시작 포인터: front, 끝 포인터: rear 초기 상태: front = rear = -1 자료 삽입 -> rear += 1 자료 삭제 -> front +=1

전단(front)과 후단(rear)에서 모두 삽입, 삭제가 가능한 큐양쪽 끝에서 높은 효율성으로 데이터 처리가 가능하다.getFront()는 큐의 peek() 연산과 같다.원형 큐 클래스를 확장하여 구현할 수 있다. -> 원형 덱원형 큐 클래스를 상속하여 원형 덱 클래

트리: 하나의 루트 노드에서 시작해서 여러 개의 자식 노드들로 이어지는 자료구조 트리의 용어 노드: 트리의 구성요소 간선: 노드를 연결하는 선(==link, branch) 루트노드: 최상위 노드, 부모노드가 없다. 서브트리: 하나의 노드와 그의 자손들로 이루어져 있다

그래프란 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다.객체는 노드로 표현되고 노드들은 간선(edge)으로 연결된다.따라서 그래프는 노드와 각 노드를 연결하는 간선을 모아 놓은 것이다.트리는 그래프의 대표적인 예시이다.오일러 문제: 다리를 한 번만 건너서 처음

template 함수 템플릿 함수의 일반화된 버전을 작성 함수의 매개변수나 리턴타입을 일반화된 형태로 선언, 이를 특정한 타입으로 대체하여 함수를 인스턴스화 특정 타입에 대해 재사용 가능 명시적 특수화: 특정 타입에 대해 명시적 특수화를 제공, 해당 타입에 대해 특별

간선들의 가중치를 합한 값이 최소가 되는 신장 트리 n-1개의 간선만 사용 사이클 포함 X kruskal 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 작은 간선 e를 선택(정렬된 순서대로 간선 선택) e를 신장 트리에 넣을 경우 사이클이 생기면

최단 경로: 네트워크에서 정점u, 정점v를 연결하는 경로 중에서 가중치 합이 최소가 되는 경로 Dijkstra 다익스트라 알고리즘 dist[i] 배열: 시작 노드 ~ i 노드까지의 최단경로 길이 그레프의 한 노드에서 다른 모든 노드까지의 최단 경로 계산 가중치가 음수

간단하지만 비효율적인 정렬 방법 내부 정렬 하나의 배열에서 작업하는 경우, 모든 데이터가 주기억장치에 있음 외부 정렬 배열을 위해 배열이 추가로 필요한 경우, 대부분의 데이터는 외부기억장치에있고 일부만 주기억장치에 저장된 상태에서 정렬 정렬 알고리즘의 안정성 값이 똑같

복잡하지만 효율적인 정렬 셸 정렬 삽입 정렬을 보완한 알고리즘 시간복잡도 최선: O(n) 최악: O(n^2) 평균: O(N^1.5) 부분 리스트가 점진적으로 정렬된 상태가 되기 때문에 삽입 정렬 속도 증가 합병 정렬 분할 정복 사용 재귀적으로 정렬한 후 합병 시간