고양이 두 잔

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

목차 Strategy Pattern 전략 패턴은 정책 패턴(Policy Pattern)이라 불리기도 하며, 소프트웨어의 실행 중 상황에 맞는 알고리즘을 선택해 실행할 수 있도록 하는 객체 지향 디자인 패턴이다. 예를 들자면 배열을 정렬하는 sort()라는 메서드가 있을 때, 요청한 알고리즘이 어떤 정렬인지에 따라 다른 로직을 실행하도록 소프트웨어를 디자인하는 것이라고 할 수 있다. 위키백과에 따르면 전략 패턴은 대략 아래와 같은 절차에 따라 구성되며, 복수의 알고리즘을 정의 정의한 알고리즘을 캡슐화 해당 알고리즘을 전략에 맞춰 상호 교체 가능하도록 구성 이어서 아래와 같은 세 부분으로 구성된다. 전략 인터페이스(Strategy Interface) 알고리즘을 정의하는 인터페이스. 일반적으로 알고리즘을 수행..

문제 수열 $S$가 어떤 수 $S_{k}$를 기준으로 $S_{1} S_{k+1} > ... S_{N-1} > S_{N}$을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열 $A$의 크기 $N$이 주어지고, 둘째 줄에는 수열 $A$를 이루고 있는..

문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. 출력 첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다. 풀이 굳이 정리할만한 문제는 아닌 것 같지만, 새로 배운게 있으니 적기로 ..

문제 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]병합 정렬(Merge Sort) [Java+Python]힙 정렬(Heap Sort) [Java+Python]퀵 정렬(Quick Sort) 카운팅 정렬은 말 그대로 세어서 정렬하는 방식이다. 그래서 무엇을 세느냐 하면, 아래에서 보겠지만 정렬 대상이 대는 원소의 등장 횟수를 전부 센다. 이후 원소의 최댓값에 따라 누적합을 보유한 배열을 만든 뒤, 그 배열의 원소를 근거로 대상 배열을 정렬하는 식이다. 카운팅 정렬의 시간 복잡도는 O(N + k)로, 여기서 k는 타깃이 되는 배열 원소의..

으로 구현한 다른 정렬: [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) 크기를 비교해 정렬하는 방식이다. 앞서 알아본 버블, 선택, 삽입 정렬에 비해 빠르나 퀵 정렬에 비해 성능이 떨어지고, 정렬 대상의 크기만 한 메모리를 요구하지만 힙, 퀵 정렬과는 다르게 안정적인 정렬이라는 특징이 있다. 추가로 병합..

으로 구현한 다른 정렬: [Java+Python]삽입 정렬(Insert Sort) [Java+Python]버블 정렬(Bubble Sort) [Java+Python]병합 정렬(Merge Sort) [Java+Python]힙 정렬(Heap Sort) [Java+Python]퀵 정렬(Quick Sort) [Java+Python]카운팅 정렬(Counting Sort) 선택 정렬은 한 마디로 말하면 처음부터 끝까지 훑어서 가장 작은(혹은 큰) 숫자를 처음 인덱스에 넣는 방식이다. 시간 복잡도가 같은 삽입 정렬이나 버블 정렬이 그때그때 값을 바꾸는 데 비해 선택 정렬은 한 바퀴에 한 번씩 원소를 배정한다. 어떤 정렬 상황에서건 일관되게 O(N2)의 속도를 보여준다는 특징도 가지고 있으며, 버블 정렬에 비해 두 배 ..

으로 구현한 다른 정렬: [Java+Python]삽입 정렬(Insert Sort) [Java+Python]선택 정렬(Selection Sort) [Java+Python]병합 정렬(Merge Sort) [Java+Python]힙 정렬(Heap Sort) [Java+Python]퀵 정렬(Quick Sort) [Java+Python]카운팅 정렬(Counting Sort) 버블 정렬(Bubble Sort)은 간단히 말하면 처음부터 시작해 인접한 원소와 비교해 자리를 바꾸는 알고리즘이다. 한 바퀴 돌 때마다 원소 하나가 확실히 정렬되기 때문에, 거품이 떠오르는 것 같다고 해서 붙은 이름이기도 하다. 선택 정렬, 삽입 정렬과 함께 최악의 효율을 보여주며, 그 와중에도 삽입 정렬보다 느리다. 최선의 상황(정렬이 끝난..