LALA's blog

퀵 정렬 (Quick Sort)이란? - 분할 정복 알고리즘 중 하나로 pivot을 기준으로 양쪽으로 정렬하는 알고리즘이다. - 병합 정렬과는 다르게 배열을 비균등하게 분할한다. Process ① 배열에서 하나의 원소(Pivot)을 고른다. ② (분할) Pivot 앞에는 Pivot보다 작은 원소들이 오고, Pivot 뒤에는 Pivot보다 큰 원소들이 오도록 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. ③ 분할된 두 배열에 대해 재귀적으로 이 과정을 반복한다. Code 시간복잡도 최선의 경우 : O(nlog₂n) * 비교 횟수 => log₂n 레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k) 했을 때, n=2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순..

삽입 정렬 (Insertion Sort)이란? - 선택 정렬과 유사하지만, 좀 더 효율적인 알고리즘이다. - 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. - 매 순서마다 해당 원소를 삽입할 위치를 찾고 해당 위치에 넣는 방식이다. Process ① 처음 Target 값은 두 번째 원소부터 시작한다. 두 번째 원소부터 앞의 원소들과 비교하여 삽입할 위치를 찾는다. ② 찾은 위치부터 자료를 뒤로 밀고 그 자리에 해당 원소를 삽입한다. Code void InsertSort(int Data[], int Lenght) { for(int i = 1; i < Lenght; i++) { int j, Target = Dat..

선택 정렬 (Selection Sort)이란? 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을 지 선택하는 알고리즘이다. 선택 정렬 vs 삽입 정렬 선택 정렬은 배열에서 해당 자리를 선택하고 그자리에 오는 값을 찾는 것이라고 생각하면 편하다. Process ① 주어진 배열 중에 최소값을 찾는다. ② 그 값을 맨 앞에 위치한 값과 교체한다. ③ 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. Code void SelectionSort(int DataSet[], int Lenght) { for(int i = 0; i DataSet..

버블 정렬 (Bubble Sort)이란? 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. Process ① 1회전에서 첫 번째 원소부터 시작. 첫 번째 원소와 두 번째 원소를 비교하여 첫 번째 원소가 더 크면 두 원소의 자리를 교환한다. 그리고 두 번째 원소를 세 번째 원소와, 세 번째 원소를 네 번째 원소와, ... N - 1 번째 원소를 N 번째 원소와 비교와 교환을 반복한다. ② 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하기 때문에, 2회전에서는 맨 마지막 원소를 제외하고 비교하면 된다. 이렇게 1회전 수행할 때마다 뒤에서 하나씩 비교 대상에서 제외된다. Code void BubbleSort(int DataSet[], int Lenght..

신장트리(Spanning Tree)란? 방향성이 없는 그래프의 서브그래프(Subgraph)들 중에서 모든 정점을 연결하는 트리를 말한다. 서브그래프는 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 트리를 말한다. 신장 트리는 그래프의 하위 개념이기도 하다. 그래프에서 난데없이 트리? 그래프는 사이클을 형성하는 간선만 제거하면 트리로 변신할 수 있다. 그래프 vs 트리 그래프 - 정점(Vertex)와 그 노드를 연결하는 간선(Edge)으로 이루어져 있다. 트리 - 그래프의 일종 - Cycle을 가지지 않는다. - 계층적 구조를 가진다. - 단 하나의 root를 가진다. 최소 신장 트리(Minimum Spanning Tree : MST)란? 최소 가중치 신장 트리(Minimum Weight S..

신장트리(Spanning Tree)란? 방향성이 없는 그래프의 서브그래프(Subgraph)들 중에서 모든 정점을 연결하는 트리를 말한다. 서브그래프는 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 트리를 말한다. 신장 트리는 그래프의 하위 개념이기도 하다. 그래프에서 난데없이 트리? 그래프는 사이클을 형성하는 간선만 제거하면 트리로 변신할 수 있다. 그래프 vs 트리 그래프 - 정점(Vertex)와 그 노드를 연결하는 간선(Edge)으로 이루어져 있다. 트리 - 그래프의 일종 - Cycle을 가지지 않는다. - 계층적 구조를 가진다. - 단 하나의 root를 가진다. 최소 신장 트리(Minimum Spanning Tree : MST)란? 최소 가중치 신장 트리(Minimum Weight S..

분할 정복 알고리즘은 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘이다. 분할 정복 알고리즘의 핵심은 '문제를 잘게 쪼개기'라고 할 수 있다. 문제를 쪼개는 방법에 대해서는 정해진 공식이나 규칙은 없다. 이것은 알고리즘을 개발하는 개발자의 창의력에 달려있는 것이다. 다만 분할 정복 알고리즘을 설계하는 대강의 요령은 있다. 그 요령은 다음과 같다. ① 분할(Divide) : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다. ② 정복(Conquer) : 하위 문제가 여전히 분할이 가능한 상태라면 하위 집합에 대해 ①을 수행한다. 그렇지 않다면 하위 문제를 푼다. ③ 결합(Combine) : ②과정에서 정복된 답을 취합한..

그래프의 정점끼리의 최단 경로를 구하는 문제 1) 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제 (1:1) 2) 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 (1:N) 3) 하나의 목적지로 가는 모든 최단 경로를 구하는 문제 (N:1) 4) 모든 최단 경로를 구하는 문제 (N:N) 다익스트라 알고리즘은 간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘이다. 사이클이 없는 방향성 그 래프에 한해서만 사용할 수 있다. 1. 다익스트라 알고리즘? Dist[] 배열에 시작점으로부터 자신에게 이르는 경로의 길이를 ∞(무한대)로 초기화 시작 정점의 경로 길이를 0으로 초기화하고(시작 정점 -> 시작 정점 거리는 0) + 방문한 정점으로 체크 방문한 정점들과 연결되..

문제 링크 https://www.acmicpc.net/problem/12100 종류 DFS + 시뮬레이션 소스코드 #include #include #include #define MAX 20 using namespace std; int N, Answer = 0; int origin[MAX][MAX]; int dr[4] = {-1, 1, 0, 0}; int dc[4] = {0, 0, -1, 1}; void input() { cin >> N; for(int i = 0; i > origin[i][j]; } } } void copy_map(int board[MAX][MAX], int map[MAX][MAX]) { for(int r ..

C 언어로 작성된 프로그램은 세 가지 종류의 메모리 영역을 가진다. 정적 메모리 프로그램이 실행하면서 프로그램에서 사용될 전역 변수/정적 변수를 메모리에 할당한 후 프로그램이 종료될 때 해제하는 영역이다. 따라서 잊어버리게 되더라도 큰 문제가 되지 않는다. 자동 메모리 자동 메모리는 스택 구로졸 이루어져 있다. 이곳에 저장된 변수는 코드 블록('{'와 '}'의 괄호로 이루어진 블록)이 종료됨에 따라 4차원의 세계로 사라진다. { /* 코드 블록 시작 */ int a = 43; double b = 1.1; } /* 코드 블록 끝. 여기에서 a와 b는 자동 메모리에서 제거된다.*/ int Plus(int a, int b) /* a와 b도 자동 메모리에 저장 */ { int c = a + b; /* c도 자동..