🧨 문제 출처 문제 출처 : 백준 2750번 문제 난이도 : 브론즈 1 문제 링크 : www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 시간복잡도 O(n^2) 을 가지는 삽입, 버블 정렬을 이용하면 시간초과가 날지 궁금해서 삽입, 버블로 구현해 제출하니 다행히 시간초과 오류가 나진 않았다. 다른 c++ 코드는 0ms 도 많던데 아마 퀵이나 병합정렬을 이용하면 간단하게 줄어들 거 같다. #include #include using na..
📌 병합정렬 병합정렬은 오름차순으로 정렬된 두 리스트 A, B의 병합으로 정렬해나가는 방식이다. 병합정렬은 대표적인 분할정복기법(Divide-and-Conquer) 중 하나로 문제를 작은 단위로 쪼개서 풀어나가는 방식이다. 분할정복기법을 사용한 정렬 알고리즘에는 병합정렬, 퀵정렬이 있다. 병합정렬에서 중요한 아이디어는 주어진 리스트를 일단 반으로 자르고 나중에 합치자는 것이다. 다음과 같은 두 가지 단계로 생각해볼 수 있다. 1) 분할정복기법에 맞게 병합정렬도 주어진 리스트를 원소 1인 리스트 여러 개로 쪼개지도록 자른다. 자르는 기준은 이진분할이다. 2) 모두 다 분할하여 주어진 원본 리스트의 길이 N만큼의 각 원소 리스트가 생성된다. 이 각 원소를 하나의 리스트로 간주하여 두 개씩 병합해 나가며 순차..
📌 삽입정렬 삽입정렬에서는 정렬대상이 될 원소를 두 부분으로 나누는 것이 핵심이다. 이미 정렬된 부분(왼쪽)과 정렬해야 하는 부분(오른쪽)으로 나누고 정렬해야 하는 부분의 첫번째 원소를 이미 정렬이 된 부분에 하나씩 삽입해 정렬한다. 즉, 정렬할 부분의 원소를 이미 정렬된 부분에 하나씩 삽입해 전체적으로 정렬된 부분의 비율을 키우는 것이다. 이미 정렬된 부분에 하나씩 삽입한다고 해서 '삽입'정렬이라고 부른다. 이때 삽입할 때는 이미 정렬된 부분의 가장 큰 원소(가장 오른쪽 원소)부터 비교해나간다. n = 5 인 { 8, 3, 9, 7, 6 } 배열을 오름차순으로 삽입정렬해본다. 이미 오름차순으로 정렬된 부분은 왼쪽에, 정렬되지 않은 부분은 오른쪽으로 두고 3부터 하나씩 삽입한다. 총 3, 9, 7, 6 ..
코테 문제를 풀면서 꼭 필요한 알고리즘 기법 중 하나가 정렬이라고 할 수 있다. 일반적으로 문제에 따라 (시간복잡도를 고려한) 적절한 정렬 알고리즘을 공식처럼 사용한다. 그 전에 자주 쓰는 정렬 알고리즘 종류와 시간복잡도를 계산했다. 📌 버블정렬 (Bubble Sorting) 맨 왼쪽 원소부터 바로 이웃한 오른쪽 원소와 비교해가며 큰 수가 오른쪽으로 가도록 교환하는 정렬방식이다. 거품정렬이라고도 하며 두 인접한 원소를 비교하는 것이 핵심이다. 시간복잡도는 O(n^2)이지만 구현이 쉬워 자주 사용된다. TMI) 양방향으로 번갈아 수행하면 칵테일 정렬이라고 한다. 이해하기 쉽도록 { 8, 3, 9, 7 6 } 배열을 오름차순 정렬하는 것을 예로 들었다. 버블정렬은 이해하기도 쉽고 구현하기도 쉬워서 자주 쓰이..
