고양이 두 잔

목차 Divide and Conquer 분할 정복 알고리즘은 큰 문제를 작은 문제로 나누어(분할) 해결(정복)하는 알고리즘이다. 조금 더 구체적으로 적자면 분할(Divide): 복잡한 문제를 더 작고 관리하기 쉬운 부분 문제로 분해하여 정복(Conquer): 이 부분 문제들을 해결한 후 결합(Combine): 이들의 해결 결과를 결합하여 원래 문제의 해답을 찾는다. 예를 들자면 정렬 알고리즘 중 병합정렬과 퀵 정렬이 이에 해당하는데, 각 구현방식은 아래 글에 설명되어 있다. [Java+Python]병합 정렬(Merge Sort) [Java+Python]병합 정렬(Merge Sort) 으로 구현한 다른 정렬: [Java+Python]삽입 정렬(Insert Sort) [Java+Python]버블 정렬(Bub..

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

으로 구현한 다른 정렬: [Java+Python]삽입 정렬(Insert Sort) [Java+Python]버블 정렬(Bubble Sort) [Java+Python]선택 정렬(Selection Sort) [Java+Python]병합 정렬(Merge Sort) [Java+Python]힙 정렬(Heap Sort) [Java+Python]카운팅 정렬(Counting Sort) 퀵 정렬은 1959년 영국에서 태어난 정렬 방식이다. 직관적인 이름대로 일반적으로 비슷한 속도의 병합 정렬, 힙 정렬보다 빠른 성능을 나타내며 힙 정렬과 추가적인 메모리를 요구하지 않기 때문에 자원 이용에 이점이 있다. 다만 안정 정렬이 아니라는 단점이 있어 파이썬에서는 도입하지 않고 있다고 한다. 추가로 데이터 접근 시간이 오래 걸리는 ..