우주수첩의 우주먼지

Insertion Sort 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 적절한 위치를 찾아 해당 위치에 삽입한다. 삽입정렬은 두 번째 자료부터 시작하여 해당 위치 기준 왼쪽의 자료들과 비교하여 삽입할 위치를 지정한다. 이는 기준점의 왼쪽의 자료들은 모두 sorted상태임을 알 수 있다. 처음 key 값은 두번째 자료부터 시작한다. #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int j; for (int i = 1; i < 10; i++) { int ..

Selection Sort 제자리 정렬 알고리즘 중 하나. 정렬되지 않은 입력 배열 외에 다른 추가 메모리를 요구하지 않는다. 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘. 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓는 행위를 반복하며 정렬을 수행한다. 1회전을 하고 나면 가장 작은 값의 자료가 맨 앞에 위치. 다음 회전에는 두번째 위치의 배열부터 처리한다. 정렬 과정 주어진 배열에서 최소값을 찾는다. 현재 범위 내에서 맨 앞의 값과 교환한다. 교환한 위치를 제외한 나머지 배열을 같은 방법으로 교체한다. 하나의 원소만 남을 때 까지 반복한다. #include #include using namespace s..

BUBBLE SORT 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 => 인접한 두 개의 원소를 비교하여 순서대로 되어있지 않을 경우 서로 교환한다. => array[3] 제외되는 데이터가 하나씩 늘어난다. #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int temp; for (int i = 0; i arr[j + 1]) { temp = arr[j + 1]; arr[j ..

https://cses.fi/problemset/task/1675/ CSES - Road Reparation cses.fi 망할 알고리즘 응용 덕분에 크루스칼 제대로 머리에 기억 남을 듯 하다. 물론 얼마나 갈지는 모르겠지만. #include #include #include using namespace std; vector Edge; class UFDS { private: vector p, rank, setSizes; int numSets; public: UFDS(int N) { numSets = N; rank.assign(N, 0); p.assign(N, 0); for (int i = 0; i < N; i++) p[i] = i; setSizes.assign(N, 1); } int findSet(int ..

최소 스패닝 트리(MST)를 만들기 위한 방법 중 하나. (+ 프림알고리즘) 1. 모든 간선들의 가중치를 오름차순으로 정렬한다. 2. 가중치가 가장 작은 간선을 선택한다. 3. 선택한 간선이 연결하려는 2개의 노드가 아직 서로 연결되지 않은 상태라면 2개의 노드를 서로 연결한다. 4. 반복. => 최소가중치를 가진 간선들을 사이클이 발생하지 않게 계속 연결하여 MST를 찾는다. 시간 복잡도 : O(mlog n) 구현 가장 작은 가중치를 갖는 간선이 연결하고자 하는 두 노드가 연결되어있는지 확인해주는 과정에서 많이 사용하는 방식이 Union-Find이다. 이전에 Union_Find를 다룬 적이 있는데 이를 이렇게 적용할 줄이야 하하핳. parent[] 코드 구현시에 대중적으로 많이 사용하는 방법은 pare..

Graph 그래프는 Vertex(정점)들의 집합 V(G)와 두 vertex를 이어주는 edge(간선)들의 집합 E(G)로 구성되어있는 구조 (G = V(G),E(G))로 표기한다. 방향성 그래프의 edge가 방향성이 있는지 없는지에 따라 Directed Graph, Undirected Graph로 나뉜다. Directed Graph : E(G)의 각 원소들은 ordered pair == 방향성이 있음. e=(a,b) != (b,a) : directed pair 는 방향성을 갖고 있기 때문에 vertex 순서도 중요하다. Undirected Graph : E(G)의 각 원소들은 unordered pair == 방향성이 없음. 인접하다 (v,u) 가 E(G)에 속해있을 때 adjacent(인접하다)라고 한다..

구현 코드 ) #include #include #include using namespace std; #define maxn (int)(le9)+1 int t, n, x, ans, cnt, block; map lastseen; int main() { cin >> t; // 테스트 케이스 개수 입력 while (t--) { cin >> n; // 정수 리스트의 길이 입력 lastseen.clear(); //테스트 케이스가 1개 이상 입력 될 경우 map을 초기화 하여 입력을 받아온다. ans = 0, cnt = 0, block = 0; for (int i = 1; i > x; int lx = lastseen[x]; if (lx != 0) { block = max(block, lx); cnt = i - blo..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net #include #include using namespace std; int line[1001][1001]; bool visited[1001]; int n, m, v; queue q; void dfs(int idx) { cout v; for (int i = 0; i > from >> to; line[fro..

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 알고리즘 응용 때문에 연습을 핑계로 재귀관련된 문제를 계속 찾아보다가 웃긴 문제를 찾았다 !!! ㅋㅋㅋㅋㅋㅋㅋㅋㅋ https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 친절하게도 언더바로 어디까지가 재귀인지 구분을 해 주어서 구현하기 훨씬 수월했던 것 같다! #include #include using namespace std; string separate(int n) { string str; for (int i = 0; i < ..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net #include #include using namespace std; void hanoi(int n, int start, int mid, int dest) { if (n == 1) printf("%d %d\n", start, dest); else { hanoi(n - 1, start, dest,mid); printf("%d %d\n", start, dest); hanoi(n - 1, ..