정렬 정렬의 경우 모든 경우에 최적인 알고리즘은 없다 정렬 알고리즘 평가 기준 비교 횟수의 많고 적음 이동 횟수의 많고 적음 정렬 알고리즘의 종류 기본 정렬 O(n^2) 선택 정렬 버블 정렬 삽입 정렬 고급 정렬 O(nlogn) 병합 정렬 퀵 정렬 힙 정렬 셀 정렬 특수 정렬 O(n) 계수 정렬 기수 정렬 버킷 정렬 선택 정렬 Selection Sort 초기에는 왼쪽 리스트는 비어있고, 정렬한 숫자들은 모두 오른쪽 리스트에 존재 오른쪽 리스트에서 가장 작은 숫자를 선택해서 왼쪽 리스트로 이동하는 작업을 되풀이정렬된 왼쪽 리스트와 정렬 안된 오른쪽 리스트로 가정 def selection_sort(arr): n = len(arr) for i in range(n-1): min_idx = i # 최솟값의 인덱스..

Dynamic Programming Dynamic Programming(동적계획법)이란? 하나의 큰 문제를 여러개의 작은 문제로 나누어 그 결과를 저장 후 다시 큰 문제를 해결할 때 사용하는 방법이다. 쉽게 말하면 "기억하며 풀기"이다. 재귀와 유사하지만 일반적인 재귀방식으로 연산할시 동일한 작은 문제들이 여러번 호출되어 비효율적이다. 재귀 - 피보나치 수열 재귀의 예시로 피보나치 수열에 대해 살펴보자 //재귀 방식으로 구현한 피보나치 수열 public class fibo { static int count=0; private static int fibona(int n){ int result = 0; count++; if(n==0) return 0; if(n==1) return 1; return fibon..

Hash Key와 Value가 쌍을 이루는 자료구조 Direct Address Table 해쉬에 대하여 알아보기 전에 먼저 알고 가야하는 자료구조이다. 키 값을 배열의 인덱스로 환산하여 데이터에 접근하는 자료구조인데 Direct Address Table은 key가 테이블 slot T[key]에 저장되기 때문에 테이블의 크기는 전체 키(U)개수가 된다. 중복키가 없고, 테이블의 크기가 작을 경우 사용 가능한 자료구조이다. Direct Address Table는 연산속도가 매우 빠르지만 문제점이 단점이 존재한다 전체 키(U)를 예측해야 테이블 사이즈를 정할 수 있으며 전체 키(U)가 크다면 테이블에 저장하는 것은 비효율적이다 전체 키(U) 대비 사용하는 키(key)가 훨씬 적을 경우 공간 복잡도에서 비효율적..

Graph 객체들의 쌍들이 서로 연관되어 객체의 집합을 이루는 자료구조 사물/추상적인 개념간의 연결 관계를 표현한 것 그래프란? 트리도 그래프의 특수한 경우 큰 프로젝트에서 작은 프로젝트 간의 우선 순위 도시들의 연결 상태 지하철 노선도 그래프의 구성요소 정점(Vertex/Node) : 그래프에서의 위치 여러가지 특성을 가질 수 있는 객체를 의미 V(G) : 그래프 G의 정점들의 집합 간선(Edge/Link/Branch) : 그래프에서 위치간의 관계 정점(노드)를 연결하는 선 E(G) : 그래프 G의 간선들의 집합 인접 정점(Adjacent Vertex) : 간선(Edge)에 의해 직접 연결된 정점을 의미 G(V, E) : 그래프는 정점과 간선의 집합이므로 G(V, E)는 그래프 자체를 의미 그래프의 종..

우선순위 큐 (Priority Queue) 일반 큐와 달리 힙(Heap) 자료구조를 가지며 우선순위가 가장 높은 자료가 먼저 꺼내지는 자료구조이다 우선순위 큐를 구현하는 방법 3가지 연결리스트와 배열 시간복잡도 : 원소 추가 O(1), 검색 O(n) 구현 쉬움 균형잡힌 이진 검색트리 시간복잡도 : 원소 추가, 삭제 O(logN) 구현 어려움 힙 시간복잡도 : 원소 추가, 가장 큰 원소를 꺼내는 연산 모두 O(logN) 구현 쉬움 위의 정리한 내용을 토대로 가장 효율적이며 쉬운 방법은 힙으로 구현하는 것이다. 힙(Heap) 추후에 상세히 다룰 예정이지만 쉽게 말하면 힙 자료구조는 '최솟값 or 최댓값을 빠르게 찾아내기 위한 완전이진트리 형태로 만들어진 자료구조'이다. 즉 기본적으로 중점을 두는 포인트는 최..

Tree 계층적인 구조를 나타내는 자료구조 트리의 용어 노드(node) : 트리의 구성요소 루트(root) : 부모가 없는 노드 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리 단말노드(terminal node) : 자식이 없는 노드 비단말노드 : 적어도 하나의 자식을 가지는 노드 자식, 부모, 형제, 조상, 자손 노드 : 인간과 동일 레벨(level) : 트리의 각층 번호 최상위 경우 level 1 그 자식은 level 2, level 2의 자식은 level 3 높이(height) : 트리의 최대 레벨(3) 차수(degree) : 노드가 가지고 있는 자식 노드의 개수 트리의 값 저장 방식 1. 데이터와 연결 상태를 저장할 클래스 공간(=노드) 생성 public static..