깊이 우선 탐색 : 탐색을 할 때 깊이를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 ​ ' 맹목적으로 각 노드를 탐색 ' 할 경우 주로 사용하는 탐색 기법으로, 모든 노드를 방문하고자 하는 경우 ( 완전 탐색) 사용 너비 우선 탐색 ( BFS) 보다 지나온 경로를 쉽게 파악할 수 있다는 장점이 있다. 또 층별로 모든 자식 노드를 저장해야 할 필요가 없기 때문에 BFS에 비해 메모리 요구량이 훨씬 적다 ​ ※ 어느 방향으로 검색할지 확률에 따라 속도가 많이 빨라질 수도 있고 느려질 수도 있다.(확률 의존) ​ 깊이 우선 탐색을 수행하기 위해서 필요한 준비물은 Stack이다. 이다. ※컴퓨터는 구조적으로 스택의 원리를 사용하기 때문에 재귀 함수를 사용하여 구현이 가능하다. ​ 이제 어떤 식으로 정렬이 이루..

너비 우선 탐색 : 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 ​ ' 맹목적인 탐색 ' 을 하고자 할 때 사용할 수 있는 탐색 기법으로 ' 최단 경로 ' 를 찾아준다는 점에서 최단 길이를 보장할 때 많이 사용 ​ ※ 시작점과 거리가 멀수록 탐색이 느려진다. 하지만 근처에 있을 경우 빠르게 탐색 가능하다. ※ 맹목적인 탐색 : 이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 탐색하는 방법을 말한다. ​ 너비 우선 탐색을 하기 위해서 필요한 준비물은 Queue ( 큐 ) 이다. ​ 우선 어떤식으로 정렬이 이루어 지는지 보자면! 다음과 같이 1 2 3 4 5 가 서로 연결되어 있다고 보았을 때 너비 우선 탐색을 해보자면 시작 노드 ( Start Node ) 를 큐에 삽입..

Queue : 데이터를 일시적으로 저장하기 위한 자료구조 가장 먼저 들어온 데이터가 가장 먼저 나가는 자료구조 ( FIFO : First In First Out) ex) 은행 창구 : 먼저 번호표를 뽑은 사람이 먼저 서비스를 받는다. Queue를 코드로 구현해보자면 import java.util.LinkedList; public class QueueEx { public static void main(String[] args) { Queue s = new Queue(); for(int i = 1; i

Stack : 데이터를 일시적으로 저장하기 위한 자료구조 가장 먼저 들어온 데이터가 가장 마지막에 나가는 자료구조 ( FILO : First In Last Out) ex) 택배 상하차 : 택배차에 택배를 처음 넣은 것이 제일 마지막에 나온다. ​ Stack을 코드로 구현해보자면 import java.util.ArrayList; public class StackEx { public static void main(String[] args) { // TODO 자동 생성된 메소드 스텁 Stack s = new Stack(); for(int i = 1; i

선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 중 가장 빠른 알고리즘은 당연히 퀵 정렬, 병합 정렬, 힙 정렬 중 하나일 것이다. ​ 하지만 '범위 조건' 이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있다. 그것은 바로 계수 정렬이다. ​ 계수 정렬 : 단순하게 ' 크기를 기준으로 ' 세는 알고리즘 ​ 1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1 즉 5이하의 자연수 데이터들을 오름차순으로 정렬할 때 ​ 크기를 기준으로 정렬하기 때문에 크기 : 1 = 0 크기 : 2 = 0 크기 : 3 = 0 크기 : 4 = 0 크기 : 5 = 0 ​ 여기에서 1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 ..

힙 정렬 : 힙 트리 구조 ( Heap Tree Structure)를 이용하는 정렬 방법 -> 병합 정렬 (Merge Sort) , 퀵 정렬 (Quick Sort) 만큼 빠른 정렬 알고리즘이다. ​ 힙(Heap)이 무엇인지 알기 전에 이진 트리(Binary Tree)에 대해서 알아보자면 이진트리 : 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드에 담은 뒤 노드를 두 개씩 이어 붙이는 구조 여기서 각 노드는 자식 노드가 2개 이하인 노드여야 합니다. 1 : Root(루트) 라고 하며 3, 4, 5 : Leaf(리프)하고 한다. -> 이진트리의 종류도 많이 있는데 우선 완전 이진 트리를 알아보자면 데이터가 Root(루트) 노드 부터 시작해 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드​​ 순으로 차근..

클래스(Class)를 정의해서 여러 개의 변수가 존재하는 상황에서 '특정한 변수' 를 기준으로 정렬하는 방법은 실무에서는 적합한 방법이지만 프로그래밍 속도 측면에서는 유리하지 않다. ​ 일반적으로 프로그래밍 대회같은 빠른 개발이 필요할 때는 페어(Pair) 라이브러리를 사용하는 것이 효율적이다. #include #include #include #include // vector가 정의되어 있는 헤더 using namespace std; int main(void) { vector v; // pair : 한 쌍의 배열(int, string)을 묶어음 v.push_back(pair(90, "잉여인간 1호")); // 배열의 마지막 부분에 삽입을 나타내는 push.back v.push_back(pair(85, "..

sort() 함수 사용하는 방법 #include #include // STL 라이브러리 -> sort() 함수가 정의되어있음 using namespace std; bool compare(int a, int b) { // 비교 함수 return a > b; // 정렬 기준 : 내림차순 정렬 } int main(void) { int a[10] = { 9, 3, 5, 4, 1, 10, 8, 6, 7, 2 }; sort(a, a + 10); // a -> 메모리 주소, a + 10 -> 정렬할 마지막 주소가 있는 메모리 주소 sort(a, a + 10, compare); // 추가로 함수를 넣어주면 원하는 정렬 기준으로 정렬을 할 수 있다. //=> 9 ~ 2 까지의 주소를 정렬한다는 사실을 나타냄 for (i..