힙정렬을 이해하기 위해서는 아래 3개의 정의를 알고 가야함 . 이진 트리 : 모든 노드의 자식이 2개 이하인 트리. 완전 이진 트리 : 데이터가 루트 노드 부터 시작해서 왼쪽 부터 빼곡하게 차있는 트리 형태 힙 (heap) : 완전 이진 트리의 일종으로 최댓값, 최솟값을 쉽세 추출 할 수 있는 자료구조 이다. 최대 힙 : 부모 노드가 자식 노드보다 큰 힙 최소 힙: 부모 노드가 자식 노드보다 작은 힙 힙 정렬 : 자료구조 '힙(heap)'을 이용하여 최대 힙 트리나 최소 힙 트리를 구성해 정렬 하는 방법 오름 차순으로 정렬 을 하기 위해서는 최대 힙을 사용하고 , 내림차순은 최소힙을 사용. 힙 정렬의 시간 복잡도는 O(N*log N) 이다. 정렬 순서 알고리즘 오름차순 기준 1. 현재 배열을 최대 힙구조..

문제 링크 : https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 문제 설명 1. 맵의 크기 NxM 이 주어지고 ,고슴도치의 위치(S), 탈출구의 위치(D),물의 위치(*), 돌의위치(X)가 ..

문제 링크: https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 문제 설명 1.가중치가 있는 양방향 그래프가 주어짐. 2. 가중치는 다리가 버틸수있는 최대 무게이고 시작 점과 도착점이 주어졌을때, 한번에 가장많이 옮길수있는데 물품의 중량 출력 알고리즘 1.처음에는 다익스트라 알고리즘을 이용하여 이동시 드는 최소 가중치를 구하였는데 문제 의도와 는 달라서 fail. 2. 다음 블로그를 찾아보며 문제를 ..

문제 링크 : https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다� www.acmicpc.net 문제 설명 1. 처음에 해킹당하기 전에 연결된 네트워크가 주어짐. 2. 네트워크는 가중치가 있는 양방향 그래프 형식. 3. 최소의 가중치로 모든 네트워크를 연결 하기위한 간선의 갯수와 연결할 간선을 출력. 알고리즘 1. 다익스트라 알고리즘을 이용하여 통신 최소 시간 을 계속 갱신. 2. 최소 시간을 갱신하면서 따로 배열을 만들어 네트워크를 이어주는 간선 ..

퀵 정렬은 피벗이라는 기준 숫자를 정하여 기준숫자보다 작으면 왼쪽인덱스로 크면 오른쪽은덱스로 옮기는 방식으로 약간 분할정복 개념 으로 정렬을 한다. c++의 sort STL 은 퀵정렬을 사용하며 시간복잡도 O(NlogN)을 보장한다. 퀵정렬의 시간복잡도는 최악의 경우 O(N^2) 이지만 평균적으로 O(NlogN)을 보인다. 정렬 과정 밑줄친 숫자는 피벗 숫자이고 빨간색 숫자는 정렬이 완료된 숫자이다 알고리즘 1. 배열의 가장 왼쪽 에 있는 수를 피벗 으로 정함 2. 피벗기준으로 피벗보다 작은수는 왼쪽으로 큰수는 오른쪽으로 옮김 3. 피벗을 계속 갱신해주고 피벗을 이용하여 정렬한 숫자를 다시 1-2번과정을 통하여 정렬. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ..

삽입 정렬은 정렬이 필요한 경우에만 알맞은 위치에 삽입하며 정렬한다. 시간복잡도는 O(N^2) 으로 버블 정렬,선택정렬과 동일하지만 일반적으로 두개의 정렬보다 더 빠르다. 진행 과정을 살펴보며 이해하자. 정렬 과정 알고리즘 1. 앞의 회색은 정렬된 배열이고 빨간색 수는 정렬 할 수이다. 2. 빨간색수를 정렬된 배열 맨뒤부터 값을 비교하며 대상 인덱스의 숫자보다 크면 앞으로 이동 3. 2번 과정을 반복하다가 더이상 이동이 없을시 정렬이 완료된것. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include using namespace std; int main() { int arr[10] = { 1,10..