[Algorithm] 병합 정렬(Merge Sort) 코드와 시간 복잡도

인트로 합병 정렬 또는 병합 정렬은 $O(NlogN)$ 시간 복잡도를 갖는 정렬 알고리즘으로 분할 정복 패러다임에 기반한다. 추가로 삽입 정렬, 버블 정렬, 선택 정렬이 추가적인 자료구조 없이 정렬하는 Inplace 정렬이라면 병합 정렬은 정렬한 데이터를 추가적인 임시 공간에 저장한다. 병합 정렬(Merge Sort) : 개념 앞서 언급했듯 병합 정렬은 분할 정복 패러다임에 기반한 알고리즘으로 큰 문제를 아주 작은 문제로 나눈 뒤 작은 문제를 해결하며 최종적으로 큰 문제를 해결한다. 다음과 같은 데이터가 배열에 저장되어 있다. 분할 : 본 배열을 더 이상 쪼갤 수 없을 때까지 쪼개면 [3] [44] [38] [5] [47] [15] [36] [26] 다음과 같은 형태가 된다. 정복 : 두 집합을 하나로 ..

• format_list_bulleted 정렬
• · 2021. 10. 10.
• textsms

[Algorithm] 두 배열을 정렬하며 합치기 : 병합 정렬 기초

인트로 병합 정렬을 포스팅하기 앞서 병합 정렬의 핵심 로직인 두 배열을 정렬하며 합치는 과정을 기록하려 한다. 보다 쉬운 이해를 위해 두 배열을 정렬하며 합치는 문제를 소개하려 한다. ↓병합정렬 포스팅↓ [Algorithm] 병합 정렬(Merge Sort) 코드와 시간 복잡도 [Algorithm] 병합 정렬(Merge Sort) 코드와 시간 복잡도 인트로 합병 정렬 또는 병합 정렬은 $O(NlogN)$ 시간 복잡도를 갖는 정렬 알고리즘으로 분할 정복 패러다임에 기반한다. 추가로 삽입 정렬, 버블 정렬, 선택 정렬이 추가적인 자료구조 없이 정렬하 kangworld.tistory.com 두 배열 합치기 문제 오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요..

• format_list_bulleted 정렬
• · 2021. 10. 9.
• textsms

[Algorithm] 38. 반전 수열(Inversion Sequence)

인트로 수열을 응용한 문제이다. 반전 수열(Inversion Sequence) 문제 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다. 예를 들어 다음과 같은 수열의 경우 [4, 8, 6, 2, 5, 1, 3, 7] 1 앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고, 2 앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개, 3 앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개...... 따라서 4 8 6 2 5 1 3 7의 inversion sequence는 5 3 4 0 2 1 1 0 이 된다. n과 1부터 n까지의 수를 ..

• format_list_bulleted it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 21.
• textsms

[Algorithm] 37. Least Recently Used(카카오 캐시 문제 변형)

인트로 LRU 페이지 교체 알고리즘을 간단하게 구현하는 문제이다. 문제에서도 설명하겠지만 LRU란 가장 오랜 시간 사용되지 않은 페이지를 교체하는 운영체제의 페이지 교체 정책 중 하나이다. LRU(Least Recently Used) 문제 캐시 메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 적어 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시 메모리 사용 규칙이 LRU 알고리즘을 따른다. LRU 알고리즘은 Least Recently Used의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않..

• format_list_bulleted it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 20.
• textsms

[Algorithm] 삽입 정렬(Insertion Sort) 코드와 시간 복잡도 (+ 예제)

인트로 기초 정렬 알고리즘 마지막 파트인 삽입 정렬(Insertion Sort)을 알아보자. 재밌게도 삽입 정렬은 데이터의 배치에 따라 O(N) 시간 복잡도를 가진다. 개인적인 생각으로 버블 정렬의 한 단계 진화한 모습이 삽입 정렬이 아닐까 한다. 삽입 정렬과 관련된 문제는 해당 포스팅을 참고하세요 :) [Algorithm] level0 : LRU(Least Recently Used) [Algorithm] level0 : LRU(Least Recently Used) 인트로 LRU 페이지 교체 알고리즘을 간단하게 구현하는 문제이다. 문제에서도 설명하겠지만 LRU란 가장 오랜시간 사용되지 않은 페이지를 교체하는 운영체제의 페이지 교체정책중 하나이다. 문 kangworld.tistory.com 삽입 정렬(In..

• format_list_bulleted 정렬
• · 2021. 8. 20.
• textsms

[Algorithm] 35. Special Sort(구글 인터뷰)

인트로 정렬을 알고리즘을 적용하는 문제이다. 어떤 정렬을 사용할진 문제를 읽어보고 고민하길 바란다. Special Sort(구글 인터뷰) 문제 N개의 정수가 입력되면 당신은 입력된 값을 정렬해야 한다. 음의 정수는 앞쪽에 양의 정수는 뒤쪽에 있어야 한다. 또한 양의 정수와 음의 정수의 순서에는 변함이 없어야 한다. ※ 입력 설명 첫 번째 줄에 정수 N(5 n; vector v(n); for (int i = 0; i > v[i]; /*Bubble Sort Begin*/ for (int i = 0; i 0 && v[j+1] < 0) { int temp = v[j]; v..

• format_list_bulleted it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 19.
• textsms