정렬9 백준알고리즘_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. 정렬알고리즘_힙정렬을 이용한 문자열 정렬 예시 [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. 정렬알고리즘_계수정렬 [7/8] [ 계수 정렬이란? ] 데이터의 크기를 기준으로 정렬하는 방식 데이터의 정렬 범위가 정해져있을 때 O(N)의 시간 복잡도를 가지므로 매우 빠름 다른 방식들은 숫자 외에도 적용할 수 있지만 계수 정렬은 숫자만 가능 숫자의 범위가 크고 분포가 넓을 경우(숫자 사이 간격이 클 경우), 메모리 비효율 발생 기본적인 방식은 매우 좋습니다만.. 숫자 범위가 엄청 넓은데 띄엄띄엄 숫자가 존재할 경우에는 메모리 공간 낭비가 심하고 비효율적이 될 수 있습니다. 예를 들어 이 방식에서는 1 ~ 10000 까지의 숫자가 있을 때 temp[10000]의 임시 공간을 만들어줘야 한다는 단점이 있습니다. 중간에 빈 공간이 많이 발생할 수도 있구요. 해쉬방식으로 배열을 나누고 연결리스트 구조를 사용해도 되겠다는 생각은 들지만.. .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9. 정렬알고리즘_힙 정렬 [6/8] [ 힙 정렬이란? ] 이진 트리에 기반한 힙 트리구조를 만들어가며 배열을 정렬시킴 병합정렬의 메모리 효율성 문제를 해결하면서 O(n*logN)의 시간 복잡도를 보장 결국 시간복잡도가 log지수의 증가를 가지려면 소그룹으로 분리시켜 정렬해나가야 함 소그룹으로 쪼개서 정렬하는 방법에 힙 트리(이진 트리) 구조가 적용된 방식이라 볼 수 있음 [ 이진 트리란? ] 하나의 노드에 자식 노드가 2개 이하인 트리 구조 [ 힙 트리란? ] 이진 트리 구조에서, 노드 간의 관계에 규칙성이 적용 된 구조 최대 힙 구조 : 부모 노드가 자식 노드보다 값이 큼 (가장 위 root 값이 최대값이 됨) 최소 힙 구조 : 최대 힙 구조와 반대 이진 트리를 최대 힙 또는 최소 힙 구조로 완성시킴 (최대값, 최소값을 빠르게 찾을 .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9. 정렬알고리즘_병합정렬 [5/8] [ 병합 정렬이란? ] 퀵정렬이 이미 정렬이 완료돼있는 경우 최악 시간 복잡도 O(n^2)을 가지는 문제를 보완 인접한 숫자 2개를 정렬하고 인접한 정렬 묶음을 다시 정렬하는 방식을 반복 수행 이미 정렬된 소그룹을 계속해서 합쳐 나가는 방식으로 O(n*logN)의 시간 복잡도를 보장 평균적으로는 퀵정렬과 비슷한 속도이지만 어느 상황에서나 속도를 보장할 수 있다는 장점 코드로 구성해보겠습니다. 반복문이 여러번 중복으로 들어가서 머릿속에서 그리는데 좀 어려웠습니다. 천재가 되고 싶다... 병합정렬은 분할정복(퀵정렬처럼 분할해서 정렬) + 삽입정렬을 섞어쓰는 느낌입니다. 그룹을 잘게 쪼개서 시간 복잡도를 log지수로 만들고, 각 그룹을 정렬하는 방식입니다. 삽입정렬에서 설명드렸듯이 정렬이 많이 되어 있는 .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9. 정렬알고리즘_퀵 정렬 [4/8] [ 퀵 정렬이란? ] 특정 값을 기준으로 정렬해야할 데이터그룹을 소규모 그룹으로 쪼개가며 정렬하는 방식 일반적으로 정렬은 n의 크기에 따라 O(n^2)로 시간 복잡도가 증가하지만, n의 크기를 일정하게 유지해 나가며 데이터를 정렬하기 때문에 O(n*logN)의 평균 시간 복잡도를 지니게 됨 이미 정렬이 잘 되어 있는 경우는 삽입 정렬에 비해 비효율적인 방식이 될 수 있음 가장 첫 값을 피봇값으로 지정해서 시작 오른쪽으로는 피봇값보다 큰 숫자를 찾고 왼쪽으로는 작은 숫자를 찾음 둘 다 찾았는데 큰값의 위치와 작은 값의 위치가 교차되지 않았다면 두 숫자를 바꿔줌 두 위치가 교차되었다면, pivot값과 left 값을 바꿔줌 크로스가 발생했다는 것은, 현 left의 위치까지 피봇값보다 큰 값은 없다는 것을 의미.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9. 정렬알고리즘_삽입정렬 [3/8] [ 삽입 정렬이란? ] 정렬 기준에 맞도록 배열의 중간에 끼워넣는 방식 앞쪽부터 계속 데이터 정렬을 수행하기 때문에 뒤로 갈 수록 수행 횟수가 줄어듦 일반 배열의 경우 값을 중간에 삽입하면 다른 데이터들을 뒤로 밀어줘야하기 때문에 비효율적 시간 복잡도 또한 O(n^2)로 비효율적인 구조에 속함 (최악정렬, 역순으로 정렬돼있을 경우) 선택정렬과 버블 정렬에 대비 수행횟수가 줄어들어 효율적인 편 삽입 정렬은 역순으로 정렬되어 있을 경우 매우 비효율적이며, 반대로 거의 정렬이 완성돼 있는 경우에는 매우 효율적인 구조가 됩니다. 랜덤하게 정렬돼 있는 경우 또는 지속적으로 정렬을 해줘야하는 상황이라면 데이터가 많을 수록 배열의 이동이 많아지기 때문에 비효율적이 됩니다. 따라서 데이터 정렬이 항상 필요한 경우는.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9. 정렬알고리즘_버블정렬 [2/8] [ 버블 정렬이란? ] 기준값과 다음값을 비교해서 작은 값을 앞으로 가져옴 이 과정을 계속 반복해서 마지막까지 가면 정렬 완료 코드는 간단하지만 O(n^2)의 시간 복잡도를 가지는만큼 매우 비효율적인 정렬 방식 수행횟수 : 9 + 8 + 7 + ... + 1 = 9(9+1)/2 = n(n+1)/2 선택정렬보다 값을 교체(Swap)하는 수행 횟수가 많으므로 더 비효율적이고 느림 arr[0] > arr[1] 이면 두 값을 바꿔줌 arr[1] > arr[2] 이면 두 값을 바꿔줌 ...반복... arr[8] > arr[9] 이면 두 값을 바꿔줌 (한 사이클 완료) arr[0] > arr[1] 이면 두 값을 바꿔줌 ...반복... arr[7] > arr[8] 이면 두 값을 바꿔줌 (한 사이클 완료) ...반복... ▸C언어/알고리즘 및 자료구조 2019. 12. 9. 정렬알고리즘_선택정렬 [1/8] [ 선택정렬이란? ] 전체 데이터를 모두 검색하는 과정을 반복해서 특정 기준으로 정렬하는 방법 쉽게 사용할 수 있으나, O(n^2)의 시간 복잡도를 가지는만큼 매우 비효율적인 정렬 방식 수행횟수 : 9 + 8 + 7 + ... + 1 = 9(9+1)/2 = n(n+1)/2 [ 오름차순 vs 내림차순 ] 왜 항상 헷갈리는 걸까요.. 내림차순 : 큰 것 → 작은 것 (높은 고도(500)에서 내려간다 (1)) 오름차순 : 작은 것 → 큰 것 (낮은 고도(1)에서 올라간다(500)) arr[0] ~ arr[9] 중 가장 작은 값을 찾아 "arr[0]"과 바꿔줌 arr[1] ~ arr[9] 중 가장 작은 값을 찾아 "arr[1]"과 바꿔줌 arr[2] ~ arr[9] 중 가장 작은 값을 찾아 "arr[2]"와 .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9. 이전 1 다음 반응형
