6두품 개발자의 고군분투

맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 큐 자료구조를 이용한다. 1. 탐색 시작 노드를 큐에 삽입하고 방문처리. 2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않는 노드를 모두 큐에 삽입하고 방문처리. 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복. 장단점 장점 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다. 단점 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다. 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든..

맹목적 탐색방법의 하나로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 스택 자료구조 혹은 재귀 함수를 이용한다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 더이상 2번의 과정을 수행할 수 없을 떄까지 반복 깊이 제한과 백트래킹 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다. 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다..

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 설명 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로..

삽입 정렬(insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다. 각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다. 그러므로 다음과 같은 결과가 된다. 배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다. 선택 정렬이나 거품 정렬과 같은 같은 O(n^2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다. import java.util.*; public class Main { public static int[] solution(in..

선택 정렬(selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다. 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC 선택 정렬 - 위키백과, 우리 모두의 백과사전 선택 정렬(選擇整列, selec..

프로세스 실행중인 프로그램. 디스크에 실행파일 형태로 존재하던 프로그램이 메모리에 올라가서 실행되기 시작하면 비로소 프로세스가 되며, 프로세스는 CPU를 획득해서 자신의 코드를 수행하기도 하고 때로는 CPU를 반환하고 입출력 작업을 수행하기도 한다. 자신의 임무를 다 수행하고 나면 종료되어 사라진다. 여러 프로세스가 함께 수행되는 시분할 시스템 환경에서는 짧은 시간 동안 CPU를 사용한 후 빼앗겼다가 추후에 다시 CPU를 획득하는 식으로 CPU관리가 이루어진다. CPU를 다시 획득해 명령의 수행을 재개하는 시점이 되면 이전의 CPU 보유 시기에 어느 부분까지 명령을 수행했는지 직전 수행 시점의 정확한 상태를 재현할 필요가 있다. 이때 정확한 재현을 위해 필요한 정보가 바로 프로세스의 문맥(context)..

해싱과 해시함수 Hashing이란 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법을 말한다. 해시함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을수 있다. 해싱을 구현한 컬렉션 클래스로는 HashSet, HashMap, Hashtable등이 있다. 해싱에서 사용하는 자료구조는 배열과 링크드 리스트의 조합으로 되어있다. 저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게되고, 다시 그 곳에 연결되어 있는 링크드 리스트에 저장하게 된다. 1. 검색하고자 하는 값의 키로 해시함수를 호출한다. 2. 해시함수의 계산결과(해시코드)로 해당 값이 저장되어 있는 링크드 리스트를 찾는다. 3. 링크드 리스트에서 검색한 키와 일치하는 데이터를..

먼저 저장한 데이터를 가장 먼저 꺼내는 FIFO(First In First Out)구조로 되어있다. front에서 요소를 꺼내고, rear에서 요소를 삽입하는 구조이다. 큐는 Array와 LinkedList로 구현할 수 있다. Array로 구현 하기 class ArrayQueue { int MAX = 5; int front; int rear; int [] queue; public ArrayQueue() { front = rear = 0; queue = new int[MAX]; } public void push(int value) { if((rear == MAX-1)) { System.out.println("Queue is Full"); } queue[rear++] = value; } public int ..

원형 연결 리스트는 이중 연결 리스트에서 마지막 노드가 첫번째 노드를 가리킨 것이다. 즉, 마지막 노드와 첫번째 노드가 연결되어 있어서 순회가 가능하다. 마지막 노드에서 첫번째 노드로 다시 돌아오는 과정이 이중 연결 리스트보다 간단하다. 원형 연결 리스트 구현 1. 노드 클래스 구현 class Node{ private String data; public Node nextNode; public Node preNode; public Node(String data) { this.data = data; this.nextNode = null; this.preNode = null; } public String getData() { return this.data; } } 2. 원형 연결 리스트 클래스 구현 class..

노드들끼리 서로 연결되어있는 리스트로, 각 노드에는 이전 노드와 다음 노드를 가리키는 참조 변수가 존재한다. 양방향 탐색이 가능하지만 단일 연결 리스트(LinkedList)보다 복잡하다 * 하지만 더 많이 쓰임 이중 연결 리스트(Doubly Linked List)의 구현 1. 노드 클래스 구현 class Node{ private String data; public Node nextNode; public Node preNode; public Node(String data) { this.data = data; this.nextNode = null; this.preNode = null; } public String getData() { return this.data; } } 2. 이중 연결 리스트 클래스 구현..