영권's

단순 삽입 정렬 단순 삽입 정렬은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘 입니다. 단순 삽입 정렬은 2번째 요소부터 선택하여 진행합니다. 4는 6보다 앞에 위치해야 하므로 앞쪽에 삽입합니다. 다음 3번째 요소인 1을 선택해 앞쪽에 삽입합니다. 그 이후에도 계속해서 같은 작업을 수행합니다. 그림에서 볼 수 있듯이 정렬된 부분과 아직 정렬되지 않은 부분에서 배열이 다시 구성된다고 생각하면서 작업을 n-1번 반복하면 정렬을 마치게 됩니다. 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입합니다. package chap06; import java.util.Scanner; // 단순 삽입 정렬 class InsertionSort { //..

정렬이란? • 주어진 자료들을 어떤 기준에 의하여 크기 순서대로 나열한 것 • 정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입이며 대부분의 정렬 알고리즘은 이 세가지 요소를 응용한 것입니다. • 데이터를 정렬해야 하는 이유는 탐색을 효율적으로 하기 위해서 입니다. 선택 정렬 선택 정렬 : 잘못된 위치에 들어가 있는 원소를 찾아 그것을 올바른 위치에 집어넣는 원소 교환으로 정렬을 하는 방법이다. 그래서 먼저 작은 원소를 찾아 첫 번째 위치에 있는 원소와 교환하고 다음에는 두 번째로 작은 원소를 찾아 두 번째 위치에 있는 원소와 교환한다. 이렇게 매번 나머지(a[i] ... a[n-1]) 원소 중에서 가장 작은 원소를 찾아 a[i] 원소와 교환하는 작업을 모든 원소가 올바른 위치에 있게 될 때까지 계속하면 ..

그래프 그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조입니다. 그래프 G는 G=(V,E)로 정의한다. 여기서 V는 공백이 아닌 노드(node) 또는 정점(vertex)의 유한 집합으로 이것만을 표현할 때는 V(G)라 표기하고, E는 상이한 두 정점을 잇는 간선(edge)의 유한 집합으로 이것만을 표현할 때는 E(G)라고 표기한다. 그래프는 무방향 그래프(undirected)와 유방향 그래프(directed)로 구분한다. 무방향 그래프(undirected graph)는 간선을 표현하는 두 정점의 쌍에 순서 즉 방향이 없는 그래프이다. 따라서 두 정점 V0과 V1을 잇는 간선 (V0, V1) 과 (V1,V0)은 똑같은 간선을 나타낸다. 보통 그래프라고 하면 이 무방향 그래프를 의미한다...

트리(Tree)의 개념 트리는 노드(node)들을 간선으로 연결한 계층형 자료구조(hierarchical data structure)를 의미한다. 따라서 이 트리는 제일 위에 하나의 노드를 루트(root)로 하여 나머지 노드들이 간선으로 연결되어 있다. 노드(node)들과 노들을을 간선들로 구성되어 있다. 트리에는 사이클(Cycle)이 존재할 수 없다. 노드들은 특정 순서로 나열될 수 있고 그럴 수 없을 수도 있다. 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다. 각 노드는 어떤 자료형으로도 표현 가능하다. 비선형 자료구조로 계층적 관계를 표현한다. Ex) 디렉터리 구조, 조직도 그래프의 한 종류 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) 또는 DAG(..

1. 스택(Stack) 스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)입니다. 스택에 데이터를 넣는 작업을 푸시(push)라 하고 데이터를 꺼내는 작업을 팝(pop)이라 합니다. 스택 구조에 푸시와 팝을 하는 위치를 꼭대기(top)이라 하고 스택의 가장 아랫부분을 바닥(bottom)이라고 합니다. Java 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용합니다. 스택 구현(Java) import java.util.Scanner; public class StackMain { public static void main(String[] args) { Scanner sc = new Scanner(Sys..

1. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행합니다. 2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행합니다. 3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행합니다. · 체인법 : 같은 해시값의 데이터를 선형 리스트로 연결하는 방법 · 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시 하는 방법 1. 선형 검색 선형 검색이란 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키값을 갖는 요소를 안날 때까지 맨앞부터 순서대로 요소를 검색하면 되는데 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고리즘입니다. 위 그림에서 선형 검색은 다음과 같은 순서로 ..