고양이 두 잔

목차 이전 글에서 자바에서의 전략패턴 구현에 대해 알아본 적이 있다. [Java]전략패턴 [Java]전략패턴 목차 Strategy Pattern 전략 패턴은 정책 패턴(Policy Pattern)이라 불리기도 하며, 소프트웨어의 실행 중 상황에 맞는 알고리즘을 선택해 실행할 수 있도록 하는 객체 지향 디자인 패턴이다. 예를 들자면 gnidinger.tistory.com 그 이후로 이런저런 구현을 하다가, 파이썬을 이용해 개발을 해야 할 일이 생겼는데, 아예 처음부터 전략패턴을 적용해서 구조를 설계하면 좋을 것 같다는 생각이 들어서 공부하게 되었다. 이 글에서는 위의 글과 마찬가지로 정렬 로직을 이용해 전략패턴을 구현하는 법을 살펴본다. 각 구현에 대한 세부사항은 아래 글에 적혀있다: [Java+Pytho..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이 문제의 팁에 병합정렬이나 힙정렬 등으로 풀 수 있으나 내부 정렬을 이용해도 된다고 적혀있다. 파이썬의 내부 정렬은 팀정렬이기 때문에 병합정렬만을 사용하는 것보다는 당연히 빠르겠으나, 이참에 파이썬으로도 병합정렬을 구현해보기로 마음먹었다. 아래는 그 결과물: 2023.03.31 - [Development/.py] - [Algorithm..

문제 오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해 보자. N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자. 입력 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2,..., AN이 주어진다. (1 ≤ Ai ≤ 109) 출력 배열 A에 K 번째 저장되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다. 풀이 병합 정렬을 한 번 구현해 보라는 문제이다. 그냥 구현하라고 하면 다른 정렬로 통과할 수도 ..

으로 구현한 다른 정렬: [Java+Python]삽입 정렬(Insert Sort) [Java+Python]버블 정렬(Bubble Sort) [Java+Python]선택 정렬(Selection Sort) [Java+Python]힙 정렬(Heap Sort) [Java+Python]퀵 정렬(Quick Sort) [Java+Python]카운팅 정렬(Counting Sort) 병합 정렬은 전설적인 수학자 폰 노이만이 고안한 알고리즘으로, 대상을 모두 쪼갠 뒤 다시 합치며(Merge) 크기를 비교해 정렬하는 방식이다. 앞서 알아본 버블, 선택, 삽입 정렬에 비해 빠르나 퀵 정렬에 비해 성능이 떨어지고, 정렬 대상의 크기만 한 메모리를 요구하지만 힙, 퀵 정렬과는 다르게 안정적인 정렬이라는 특징이 있다. 추가로 병합..