404 not found

정렬알고리즘 : 데이터를 특정한 기준에 따라 순서대로 나열하는 것 1. 선택 정렬 : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에있는 데이터와 바꾸는 것을 반복 ex) 가장 작은 값을 골라 탐색범위 가장 앞자리와 자리를 바꾼다. 3 4 0 1 5 2 > 0 4 3 1 5 2 > 0 1 3 4 5 2 > 0 1 2 4 5 3 > 0 1 2 3 5 4 > 0 1 2 3 4 5 array = [3, 4, 0, 1, 5, 2] for i in range(len(array)): #i는 가장 작은 데이터와 위치가 바뀔 인덱스 min_index = i #가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: ..

우선순위 큐(Priority Queue) : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 1) 리스트를 이용하여 구현 2) 힙(heap)을 이용하여 구현(단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일) : 완전 이진 트리 자료구조 : 항상 루트노드를 제거한다 최소힙 - 루트노드가 가장 작은 값을 가진다 / 값이 작은 데이터가 우선적으로 제거 최대힙 - 루트노드가 가장 큰 값을 가진다 / 값이 큰 데이터가 우선적으로 제거 * 완전 이진 트리 : 루트 노드부터 시작하여 왼쪽 자식노드, 오른쪽 자식노드 순서대로데이터가 차례로 삽입되는 트리 * 최소 힙 구성 함수 : 부모 노드로 거슬러 올라가며, 부모다 값이 더 작은 경우에 위치를 교체 Python import sys im..

스택 자료구조 : 먼저 들어 온 데이터가 나중에 나가는 형식 : 입구와 출구가 동일한 형태 ex) 박스 쌓기 파이썬(Python) stack = [] #기본 리스트가 stack구조 stack.append(5) stack.append(7) stack.append(2) sack.pop() stack.append(3) stack.append(1) stack.pop() print(stack[::-1]) #최상단 원소부터 출력 print(stack) # 최하단 원소부터 출력 결과================================================= [3,7,5] [5,7,3] 자바(JAVA) import java.util.*; public class Main { public static void..

7. 멱집합(Powerset) 멱집합 임의의 집합의 모든 부분집합 ​ {a,b,c,d,e,f} 의 모든 부분집합을 나열하려면 a를 제외한 {b,c,d,e,f} 의 모든 부분집합들을 나열하고 , {b,c,d,e,f} 의 모든 부분집합에 {a}를 추가한 집합들을 나열한다. ​ 집합 S : k번째부터 마지막 원소까지 연석된 원소들 : data[k], ..., data[n-1] 집합P : 처음부터 k-1번째 원소들 중 일부 : include[i] = true (i = 0, ..., k-1) private static char data[] = {'a','b','c','d','e','f'}; private static int n = data.length; private static boolean [] include..

6. 순환(Recursion)의 응용: N-Queens N-Queens 가로세로 크기가 N인 체스보드에서 N개의 퀸들이 서로를 공격할 수 없게 놓는 문제. 동일한 행, 열, 대각선에 2개 이상의 말이 놓이지 않아야 한다. ​ ex) N = 4 O O O O 상태공간 트리란, 찾는 해를 포함하는 트리. 즉, 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당함. 따라서, 이 트리를 체계적으로 탐색하면 해를 구할 수 있음. 하지만, 상태공간 트리의 모든 노드를 탐색해야하는 것은 아님. ​ 되추적 기법(Backtracking) 상태공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘 ​ 자바 예제) 매개변수는 내가 현재 트리의 어떤 노드에 있는지를 지정해야한다. cols[i] = j 는 i번..

5. 순환(Recursion)의 응용: Counting Cell in a Blob Binary 이미지 각 픽셀은 background pixel이거나 혹은 image pixel 서로 연결된 image pixel들의 집합을 blob이라고 부름 상하죄우 및 대각방향으로도 연결된 것으로 간주 ​ ex) 4개의 Blob이 존재 (x,y)가 포함된 blob의 크기를 구하는 예제 ​ 현재 픽셀이 속해있는 blob의 크기를 세려면, ​ 현재 픽셀이 image color가 아니라면, 0을 반환한다. 현재 픽셀이 image color라면 먼저 현재 픽셀을 카운트하다. 현재 픽셀이 중복카운트되는 것을 방지하기위해 다른 색으로 칠한다. 현재 픽셀에 이웃한 모든 픽셀들에 대해서 그 픽셀이 속한blob의 크기를 카운트하여 카운터..

4. 순환(Recursion)의 응용: 미로찾기 미로찾기 현재 위치에서 출구까지 가는 경로가 있으려면 1. 현재 위치가 출구이이거나, 2. 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있있어야 한다. ​ Decision Problem(답이 Yes or No인 문제) x,y로 부터 출구까지 가는 경로가 있으면 true, 없으면 false ​ 예제) boolean findPath(x,y){ if (x,y) is the exit return true; else for each neighbouring cell(x',y') of (x,y) do //이웃 셀들 //if (x',y') is on the pathway //이웃된 두 셀을 왔다갔다하는 무한루프가 가능 if (x',y') is ..