정렬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.