힙정렬4

• 

  백준알고리즘_2751_정렬 (힙정렬) (C언어) 사실 시간 복잡도 O(nlogN)의 알고리즘은 기초알고리즘 게시판에서 다 정리했지만.. 혹시 까먹었을까 싶어 한 번 풀어봤습니다. 오랜만에 짜봐서 그런지 또 시간이 꽤 걸렸네요. ㅎㅎ 시간 복잡도를 낮추려면 병합정렬, 퀵정렬, 힙정렬 세 가지 중 하나를 사용하면 됩니다. 저는 제일 좋아하는 힙정렬을 사용했습니다. 알고리즘 설명은 아래 링크글에 있습니다. 2019/12/09 - [C언어/알고리즘 및 자료구조] - 정렬알고리즘_힙 정렬 [6/8] #include #include void heap(int* arr, int n); void swap(int* arr, int x, int y); int main() { // 배열 생성, 스택에 담기엔 너무 크다고 에러나서 동적 할당 int* arr = (int*)m.. ▸알고리즘 문제 풀이 2019. 12. 9.

• 

  크루스칼 알고리즘_고속도로 길찾기 [1/1] 뭔가 했더니 도시 간 고속도로를 최단 거리로 잇기 위해서는 어떻게 할 것이냐하는 옛 퀴즈를 푸는 알고리즘입니다. 아래와 같이 각 도시 간 이어진 고속도로가 있고 최단거리로 모든 도시를 한바퀴 돌려면 어디서 출발해서 어느 길로 가야하는가를 푸는 문제라고 보면 되겠네요. 실전에서는 어디다가 쓰이는지는 감이 잘 안잡히지만 일단 한 번 풀어보겠습니다. 먼저 두 가지 기준이 생각났는데 첫 번째로는 도시를 기준으로 연결돼 있는 길들을 잇는 방식입니다. 하지만 이 방식은 도시 - 도시 간 최단거리는 찾을 수 있겠지만 전체로 볼 때 가장 짧은 루트를 찾을 수는 없으므로 패스하겠습니다. ​ 그럼 각 길을 중심으로 찾는 방법이 있겠네요. 보자마자 떠오른 방식은 연결리스트를 응용하는 것인데 잘 될지 한 번 짜보겠습니다. 전.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  정렬알고리즘_힙정렬을 이용한 문자열 정렬 예시 [8/8] 숫자 정렬보다는 문자열 정렬이 실제로 더 많이 사용되므로 제일 맘에 들었던 힙정렬을 이용해서 문자열 정렬을 한 번 해보겠습니다. 구현 방식은 완전히 같습니다. 다만 문자열을 서로 비교해서 무엇이 더 큰지만 잘 비교해주면 됩니다. strcmp() 함수가 있는걸 깜박하고 그냥 만들어 썼는데 그냥 기본 함수를 써도 무방합니다. #include int compare_text(char text1[], char text2[]); void swap(char* arr[], int x, int y); void arr_printf(char* arr[], int size); void main() { char* arr[] = { "banana", "pine", "candy", "home", "apple", "apple2", .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  정렬알고리즘_힙 정렬 [6/8] [ 힙 정렬이란? ] 이진 트리에 기반한 힙 트리구조를 만들어가며 배열을 정렬시킴 병합정렬의 메모리 효율성 문제를 해결하면서 O(n*logN)의 시간 복잡도를 보장 결국 시간복잡도가 log지수의 증가를 가지려면 소그룹으로 분리시켜 정렬해나가야 함 소그룹으로 쪼개서 정렬하는 방법에 힙 트리(이진 트리) 구조가 적용된 방식이라 볼 수 있음 ​[ 이진 트리란? ] 하나의 노드에 자식 노드가 2개 이하인 트리 구조 ​[ 힙 트리란? ] 이진 트리 구조에서, 노드 간의 관계에 규칙성이 적용 된 구조 최대 힙 구조 : 부모 노드가 자식 노드보다 값이 큼 (가장 위 root 값이 최대값이 됨) 최소 힙 구조 : 최대 힙 구조와 반대 이진 트리를 최대 힙 또는 최소 힙 구조로 완성시킴 (최대값, 최소값을 빠르게 찾을 .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.