정렬(2)
-
[JavaScript] 백준 3273번 두 수의 합
이 글은 백준 3273번 두 수의 합을 풀이한다. 코드는 JavaScript로 구현하였다. 문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 예제 입력 1 9 5 12 7 10 9 1 2 3 11 13 예제 출력 1 3 제..
2023.06.28 -
[Algorithm] 합병 정렬(merge sort) 정리
합병 정렬(merge sort) 이란? 합병 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 📖 안정 정렬 이란? 안정 정렬 알고리즘은 반복되는 요소를 입력 때와 동일한 순서로 정렬시킨다. (참고) 📖 분할 정복 알고리즘(Divide and conquer alogorithm) 이란? 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 합병 정렬(merge sort) 과정 합병 정렬 4단계 분할(Divide) → 정복(Conquer) → 결합(Combine)→ 복사(Copy) 분할(Divde) 정렬되지 않은 리스트를 절반으로 잘라 리스트를 두 부분으로 나눈다. 정복(Conquer) 부분 배열을 정렬한다. 부분..
2022.12.26