전체 글 (88) 썸네일형 리스트형 [C/C++] 코드업(codeup) 3011번 거품 정렬(Bubble Sort) ▽문제 바로가기 https://codeup.kr/problem.php?id=3011 거품 정렬(Bubble Sort) 첫 줄에 데이터의 개수 n이 입력된다. (2 [C++] 코드업(codeup) 3004번 데이터 재정렬 ▽문제 바로가기 https://codeup.kr/problem.php?id=3004 데이터 재정렬 50 23 54 24 123 에서 23, 24, 50, 54, 123 순서로 0, 1, 2, 3, 4 가 된다. 그리고 원래의 위치대로 출력한다. codeup.kr 입력 첫째 줄에 데이터의 개수 N이 입력된다. ( 1 [C/C++] 크루스칼 알고리즘(Kruskal algorithm) 크루스칼 알고리즘이란? 크루스칼 알고리즘(Kruskal algorithm) 또는 크러스컬 알고리즘(Kruskal's algorithm)은 모든 노드를 최소한의 비용으로 연결하는 알고리즘이다. 크루스컬 알고리즘은 최소 비용 신장 트리(Minimal Spanning Tree, MST)를 구하는 대표 알고리즘입니다. 신장 트리(Spanning Tree)는 기존 그래프의 모든 노드를 포함하지만 싸이클이 존재하지 않는 그래프 트리를 말합니다. 예를 들어 다음과 같은 그래프가 있습니다. 노드는 총 7개가 있고 노드를 연결하는 간선은 11개입니다. 크루스칼 알고리즘은 싸이클이 발생하지 않는다고 했습니다. 싸이클이 발생하는지 안 하는지 여부를 확인하기 위해서는 다음과 같은 과정이 필요합니다. 노드의 최종 부모를 가리키.. [C/C++] 깊이 우선 탐색(DFS) 깊이 우선 탐색이란? 깊이 우선 탐색(depth-first search, DFS)은 맹목적 탐색방법의 하나로 깊이를 우선적으로 탐색하는 방법이다. 깊이 우선 탐색은 스택과 관련 있습니다. 예를 들어 위와 같은 이진트리가 있습니다. 가장 먼저 루트 노드를 방문합니다. DFS와 마찬가지로 방문하면 방문 체크를 해줍니다. 스택 1 방문체크 1 스택의 최상단 노드와 연결된 노드 중 하나를 방문합니다. 2번 노드를 방문합니다. 스택 1-2 방문체크 1-2 아직 방문하지 않은 노드가 있으면 방문합니다. 3번 노드를 방문합니다. 스택 1-2-3 방문체크 1-2-3 최상단 노드와 연결된 방문하지 않은 노드가 없다면 꺼냅니다. 3번 노드와 연결된 노드 중 방문하지 않은 노드가 없으므로 꺼냅니다. 스택 1-2 방문체크 1.. [C/C++] 너비 우선 탐색(BFS) 너비 우선 탐색이란? 너비 우선 탐색(Breadth-first search, BFS)은 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 너비 우선 탐색은 큐와 관련 있습니다. 예를 들어 다음과 같이 연결된 이진트리가 있습니다. 가장 먼저 루트 노드를 방문하고 방문했다는 체크를 해줍니다. 큐 1 방문체크 1 큐에서 하나의 노드를 꺼내고 인접한 노드를 검사하여 큐에 차례대로 넣습니다. 큐 2-3 방문체크 1-2-3 다시 큐에서 하나의 노드를 꺼내고 인접한 노드를 검사하여 큐에 넣습니다. 2를 꺼낼 차례입니다. 3은 큐에 있으므로 4와 5를 넣어줍니다.(이미 방문한 노드는 넣지 않습니다.) 큐 3-4-5 방문체크 1-2-3-4-5 반복해서 큐에서 하나의 노드를 꺼내고 인접한 .. [C++] sort 함수로 정수, 문자열 오름차순 내림차순 정렬하기 sort 함수란? sort 함수는 C++ 'algorithm' 헤더 파일에 있는 함수입니다. sort 함수는 정렬 기능을 가진 함수입니다. qsort라는 함수도 정렬 기능을 하지만 sort함수가 더 빠릅니다. 표준 라이브러리에 있는 만큼 강력하기 때문에 사용하는 게 좋다고 합니다. 함수의 원형입니다. //default template void sort (RandomAccessIterator first, RandomAccessIterator last); //custom template void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); 쉽게 표현하면 다음과 같습니다. void sort(첫번째주소, 마지막주소, 정렬.. [C/C++] 힙 정렬(heap sort)로 오름차순 정렬하기 힙 정렬이란? 힙 정렬은 힙을 사용하여 정렬하는 알고리즘입니다. 그러면 힙 이란 무엇인가? 힙은 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전이진트리입니다. 예를 들어 다음과 같이 1부터 10까지의 수를 무작위로 섞어놓은 배열이 있습니다. 값56104387129 위치[0][1][2][3][4][5][6][7][8][9] 먼저 힙 상태를 만들어야 합니다. 이 과정을 heapify라고 합니다. 자기와 자기 자식의 요소들을 비교하여 자기보다 큰 값을 가지는 자식 노드가 있다면 자리를 바꾼다. 여기서 교환이 일어나면 당연히 위에 노드도 점검을 해야 합니다. 힙 정렬 알고리즘은 다음과 같습니다. 힙 상태인 데이터에서 루트와 최하단 노드를 교체합니다.(그러면 최하단 노드는 정렬이 완료됩니다.) 힙 상.. [C/C++] 병합 정렬(merge sort) 원리와 오름차순구현 병합 정렬이란? 병합 정렬(merge sort) 또는 합병 정렬은 분할 정복 알고리즘의 하나로 원소를 분할하여 비교 및 정렬하는 알고리즘이다. 퀵 정렬은 피봇이라는 기준값이 있는 반면에, 병합 정렬은 피봇없이 일단 분할하는 방식이다. 예를 들어 다음과 같이 무작위로 섞어놓은 배열이 있습니다. 5 6 10 4 3 8 7 1 각 원소를 1나 씩 분할하는 것으로 시작합니다. 각 리스트의 길이가 1 될 때까지 분할합니다. 561043871 각 리스트는 길이가 1이므로 정렬된 것으로 봅니다. 이제 분할된 원소는 이웃한 원소 끼리 비교하며 병합합니다. 561043871 5 64 103 81 7 5와 6 비교, 10과 4 비교, 3과 8 비교, 7과 1 비교하여 길이가 2인 리스트 4개를 만듭니다. 계속해서 비교정렬.. 이전 1 ··· 3 4 5 6 7 8 9 ··· 11 다음
