728x90 공부/알고리즘33 힙정렬 저번주에 공부하긴 했지만 이해하는데 좀 시간이 걸리는 바람에 지금 포스팅합니다. 힙정렬은 퀵정렬과 병합정렬과 더불어 시간복잡도 O(nlogn) 을 가진 정렬입니다. 힙정렬을 이해하기 위해서는 완전 이진 트리를 이해해야하는데요. 이진 트리는 자식노드가 두개 이하 트리를 의미합니다.. 여기서 가장 위에 있는 7은 루트노드(root)입니다. 그리고 8과 5의 부모노드입니다. 2와 3은 8의 자식노드입니다. 가장 밑 부분인 2 3 1 2 는 리프노드(leaf)라고 합니다. 트리는 다양하게 생길 수 있습니다. 이런식도 가능합니다. 그 중에서 이진 트리는 자식노드가 두개 이하인 트리이고 완전 이진트리는 자식노드가 두개인 트리를 의미합니다. 간단하죠? 힙은 이런 완전 이진트리를 사용합니다. 한번 트리를 만들어 볼까요.. 2020. 6. 1. C++ Sort() 사용 클래스 객체를 이용해서 정렬하는 건 실무에서 많이 사용되는 방법이고 프로그래밍 대회에선 실행 시간에 안 좋은 측면 때문에 자주 사용되지 않는다고 합니다. 실제로는 C++에 vector 라이브러리에, pair 를 더 많이 이용합니다. 정렬은 이미 만들어진 훌륭한 라이브러리가 많으니깐 원리를 이해하고 바로 라이브러리를 사용하면 좋겠죠! sort 함수는 라이브러리에 포함되어있고 pair는 라이브러리에 포함되어 있습니다. #include #include using namespace std; //sort 기준을 스스로 정할 수 있음 //단순 데이터 정렬 기법은 현실적이지 않음 bool compare(int a,int b){ return a < b; } int main(void){ int a[10] = {9, 3,.. 2020. 5. 30. 병합정렬 복습 저번 시간에서는 O(NlogN) 인 퀵정렬에 대해 배웠습니다. 하지만 퀵정렬은 정렬이 거꾸로 되어 있는 경우에 O(N^2)의 시간복잡도로 효율이 굉장히 안 좋아지는데요. 그에 반해 병합정렬은 O(NlogN) 의 시간복잡도를 보장해줍니다. 평균이 퀵정렬보다 빠르진 않지만 보장해준다는 면에서 굉장히 좋은 정렬 알고리즘임을 알 수 있습니다. 병합정렬도 퀵정렬과 같이 나누고 해결하는 '분할 정복(divide and conquer) 알고리즘' 을 사용하는데요. 여기서 병합정렬이 시간복잡도를 보장해주는 이유에 대해서 나옵니다. 병합정렬은 무조건 두개로 나눠줍니다. 그리고 합치면서 정렬을 수행합니다. 합칠때 계산 횟수가 n 번이기 때문에 병합정렬은 O(nlog n) 의 시간복잡도를 보장할 수 있는 것 입니다. i 번.. 2020. 5. 29. 퀵정렬 복습 오늘은 퀵정렬에 대해 배워보았습니다. 말에서 부터 뭔가 굉장히 빠를 거 같은 느낌이 들죠? 선택,삽입,버블 정렬은 다 O(N^2) 복잡도의 알고리즘이었는데요 . 퀵정렬은 무려 O(n log n)의 복잡도를 가지고 있습니다. log n 은 어마어마한 수인데요 생각해보면 n = 1000 log n = 10 정도고 n = 1000000 이면 n은 20 정도 입니다. 실제로 알고리즘을 조금 더 공부하면 log n의 대단함을 더 느낄 수 있다고 하네요. 이런 퀵정렬의 핵심은 "특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누면 어떨까!" 입니다. 이 특정한 값을 보통 기준 pivot 값이라고 칭합니다. 퀵정렬은 큰 문제를 나눠서 해결하는 분할 정복 알고리즘에 기반하기 때문에 더 빠르게 정렬이 가능합니다. -> 특.. 2020. 5. 28. 이전 1 ··· 4 5 6 7 8 9 다음 728x90
