알고리즘 (56) 썸네일형 리스트형 [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/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개를 만듭니다. 계속해서 비교정렬.. [C/C++] 퀵 정렬(quick sort) 원리부터 구현까지 퀵 정렬이란? 퀵 정렬(quick sort)은 배열의 요소를 정렬하기 위한 분할 정복 알고리즘의 일종으로, 1959년 토니 호어(Tony Hoare)에 의해 개발되었다. 퀵 정렬은 기준키를 기준으로 작거나 같은 값을 지는 데이터는 앞으로, 큰 값을 지는 데이터는 뒤로 가도록 하여 작은 값을 갖는 데어터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다. 예를 들어 다음과 같이 1부터 10까지의 수를 무작위로 섞어놓은 배열이 있습니다. 5 6 10 4 3 8 7 1 2 9 먼저, 적당한 피봇(pivot, 기준값)을 선택해야 합니다. 일반적으로 데이터의 총 평균값에 근접하는 값을 취하는데 편의상 가장 앞에 있는 값으로 하겠습니다. 그러면 여기서는 피봇이 5입니다. 피봇을 두고 왼쪽에서 오른쪽으로 탐색하여.. [C/C++] 삽입 정렬(insertion sort) 삽입 정렬이란? 삽입 정렬(insertion sort)은 새로운 데이터를 이미 정렬된 데이터들 사이의 적절한 자리에 집어넣는 정렬 방식입니다. 예를 들어 다음과 같이 1부터 10까지의 수를 무작위로 섞어놓은 배열이 있습니다. 값56104387129 위치[0][1][2][3][4][5][6][7][8][9] 먼저, [0]인 5는 이미 정렬된 상태라고 생각합니다. 그다음 [1] 위치의 6이라는 숫자를 정렬해야 합니다. 그러면 6이 올 수 있는 위치는 두 군데입니다. _ 5 _ 6은 5보다 크므로 5 뒤에 위치합니다. 5 6 이제 [2] 위치의 10을 정렬해야 합니다. 10이 올 수 있는 위치는 세 군데입니다. _ 5 _ 6 _ 10은 가장 뒤에 있는 숫자 6과 비교하여 크므로 6 뒤에 위치합니다. 5 6 1.. 이전 1 ··· 3 4 5 6 7 다음
