이번 포스팅에서는 재귀 알고리즘 기초에 대해서 알아보겠습니다. 1. 재귀 알고리즘 기초. 재귀 (Recursion) 함수란 특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수입니다. 문제를 해결하기 위해 원래 범위의 문제에서 더 작은 범위의 하위 문제를 먼저 해결함으로써 원래 문제를 해결해 나가는 방식입니다. 일반 반복문을 통해 구현 가능한 기능은 재귀 함수를 통해 구현이 가능하며 반대로 재귀 함수로 구현 한 기능을 반복문으로 구현이 가능합니다. 재귀 함수는 함수 내에서 자기 자신을 계속 호출하는 방식이기 때문에 함수 안에 반드시 종료 구간이 되는 Base Case를 생각하며 코드를 구현해야 합니다. 아래 샘플 예제를 한 번 보겠습니다. 1234567891011121314public c..

힙 정렬 (Heap Sort) ▶힙 정렬은 힙 자료구조를 기반으로 원소들을 정렬하는 방식을 의미합니다. 힙에 대한 기본 지식은http://lktprogrammer.tistory.com/69 에서 확인 할 수 있습니다. ■ 정렬 과정 ▶ 이번 게시글에서는 최대힙을 기준으로 설명을 하겠습니다. 힙의 기본은 완전 이진 트리의 형태이면서 부모 노드가 자식 노드보다 큰 값을 가지는 힙 성질을 만족하는 트리를 의미합니다. 따라서 최상위 노드인 루트 노드는 전체 원소 중에서 항상 최대값을 가지게 됩니다. 1. 배열에 저장 된 원소들을 최대힙으로 구성 2. 루트 노드에 존재하는 값을 가지고 오고, 가장 말단에 있는 노드를 루트 노드에 위치 시킵니다. 새로 자리 잡은 루트 노드에 대하여 다시 힙 성질에 맞게끔 배열을 조..

힙 자료구조 힙 자료구조는 원소 값들 중에서 최대값과 최소값을 구하는데 효율적인 자료 구조를 의미합니다. 트리의 개념을 공부하고 싶으면 http://lktprogrammer.tistory.com/67 여기를 참조해주세요. 힙은 완전 이진 트리의 형태를 가지면서 동시에 다음과 같은 힙 성질을 만족해야 합니다. ● 부모노드가 자식노드보다 큰 경우 - 최대 힙 ● 부모노드가 자식노드보다 작은 경우 - 최소 힙 ▶ 이번 게시글에서는 최대 힙을 기준으로 설명 하겠습니다. 왼쪽 최대 힙을 보면 모두 부모 노드의 값이 자식 노드 값보다 큰 형태를 이루고 있습니다. 부모 노드 50의 경우 자식 노드 25와 40보다 크며, 부모 노드 25는 자식 노드 12와 14보다 큰 형태를 이루고 있습니다. 즉, 힙의 이러한 성질 ..

옵저버 패턴 (Observer Pattern) 옵저버 패턴은 개개체의 상태 변화를 관찰하는 관찰자들, 즉 옵저버들의 목록을 객체에 등록하여 상태 변화가 있을 때마다 메서드를 통하여 관찰 대상자가 직접 옵저버들에게 통지하여 상태를 동기화 할 수 있도록 하는 디자인 패턴을 의미합니다. ■ 옵저버 패턴 예제 ▶옵저버 패턴이 적용된 예제를 구현 해보겠습니다. ● Generator : 관찰 대상자를 나타내며, 현재 관찰 대상자에 붙어있는 Observer들을 관리합니다. 뿐만 아니라 현재 관찰 대상자의 상태 정보를 얻기 위한 메서드를 제공하며, 상태 변화시 등록되어 있는 모든 관찰자들에게 상태 변화를 통지해주는 메서드를 제공합니다. ● StringGenerator : Generator를 상속받는 실제 상태 정보를 ..

트리 (Tree) 계층적인 구조를 표현하기 위한 자료구조로 여러 노드가 한 노드를 가리킬 수 없는 구조를 의미합니다. 일반적으로 조직도, 디렉토리 구조등을 생각하면 됩니다. 스택이나 큐와 같은 선형구조가 아닌 뒤집어놓은 나무 모양 같은 계층구조를 가지며, 탐색이나 계층적 구조를 가져야 하는 데이터를 다루는데 많이 사용됩니다. 트리의 특징 ▶ 트리는 노드(A,B,C,D,E,F)와 노드들 사이를 이어주는 링크로 이루어져 있습니다. 트리의 노드가 n개라면 링크의 개수는 n-1개가 됩니다. 최상위 노드 A를 루트 노트라고 부르며 B,C를 가지노드라 하며 D,E,F와 같이 자식을 가지지 않는 최하위 노드들을 리프노드라고 부릅니다. ▶ 트리는 기본적으로 부모-자식 관계를 가집니다. A노드 입장에서는 B,C의 자식 ..

메멘토 패턴 (Memento Pattern) 메멘토 패턴은 객체의 상태 정보를 저장하고 사용자의 필요에 의하여 원하는 시점의 데이터를 복원 할 수 있는 패턴을 의미합니다. ■메멘토 패턴 예제 구조 ▶ 실제로 메멘토 패턴을 사용하여 객체 정보를 저장하고 복원하는 예제를 살펴 보겠습니다. 예제는 간단히 String형 데이터 하나와 Int형 데이터 하나에 대한 정보로 가지는 Information 객체를 구현하였습니다. ● User : 메멘토 패턴이 적용 된 Information 객체를 실제로 사용하는 사용자입니다. ● Information : 상태를 저장하고 복원 할 데이터를 가지고 있는 클래스입니다. ● Memento : 특정 시점의 Information의 상태정보를 저장하는 클래스입니다. ● CareTak..

데코레이터 패턴 (Decorator Patter) 중심이 되는 객체에 부가적인 기능을 동적으로 추가하고자 할 때 사용하는 패턴입니다. ■ 데코레이턴 패턴 구조 (예제) 예제는 기본 빵 객체를 대상으로 여러가지 재료를 조합하여 동적으로 햄버거를 만드는 예제입니다. ● Hamburger : 장식할 대상이 가져야 할 공통 인터페이스를 정의합니다. ● Bread : 구체적인 장식 할 대상입니다. 다른 장식 대상을 장식 할 수는 없습니다. ● Ingredient : 장식 할 대상을 장식하는 클래스로 또한 Hamburger의 인터페이스를 가지기 때문에 장식 대상이 될 수도 있습니다. 장식 할 대상의 객체를 참조합니다. ●Shrimps_Patty 와 Bulgogi_Patty : Ingredient의 인터페이스를 구현..

원형큐 (Circular Queue) 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조입니다. 앞선 포스팅에서 선형큐의 문제점은 rear이 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용 할 수가 없었습니다. 원형큐에서는 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해집니다. ■ Enqueue rear의 포인터를 1증가 시키고 그 위치에 데이터 삽입이 이루어집니다. 만약 rear+1이 배열의 끝이고 포화상태가 아니라면 배열의 첫 번째 인덱스에 데이터를 삽입합니다. → 배열의 포화상태 여부를 판단하기 위하여 배열의 1칸은 비워둡니다. (rear+1)%arra..

방문자 패턴 (Visitor Pattern) 데이터 구조와 연산을 분리하여 데이터 구조의 원소들을 변경하지 않고 새로운 연산을 추가 할 수 있습니다. 새로운 연산을 추가하려면 새로운 방문자를 추가하기만 하면 됩니다. ■ 방문자 패턴 구조 (예제) 오른쪽에는 Composite 패턴으로 구현 된 File과 Directory로 이루어진 데이터 구조가 있습니다. 다만, 방문자를 수용하기 위해 Element 인터페이스를 상속받아서 accept() 메서드를 각각 구현하고 있으며 각 element의 경로를 구하는 연산 부분이 방문자에서 이루어집니다. 왼쪽에는 방문자로 데이터 구조를 방문하면서 필요한 연산을 수행합니다. 각 element에 접근하기 위한 visit메서드를 오버라이딩 및 오버로딩을 하고 있습니다. ■ 소..

컴포지트 패턴 (Composite Pattern) 객체들을 트리 구조로 구성하여 그릇 객체와 내용물 객체를 동일하게 취급할 수 있도록 만들기 위한 패턴입니다. Composite Pattern Structure ● Component : Leaf와 Composite의 상위 클래스로써 이들을 동일하게 취급 할 수 있도록 공통 인터페이스 정의 ● Composite : 그릇을 나타내는 역할을 하고, 또 다른 그릇을 참조하거나 내용물 객체를 참조 할 수 있음 ● Leaf : 내용물 객체로서, 그릇 객체를 포함 할 수 없음 예제 예제는 디렉토리 구조를 구성하는 예제로 디렉토리는 그릇 객체에 해당되며 파일은 내용물 객체에 해당합니다. 예제의 클래스 다이어그램입니다. Entry 객체는 File과 Directory를 동일..

기수정렬 (Radix Sort) 기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다. ■ 정렬 방식 1. 0~9 까지의 Bucket(Queue 자료구조의)을 준비한다. 2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다. 3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다. 4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다. 아래의 8개 데이터에 대하여 기수 정렬을 시도해 보겠습니다. 위의 그림과 같이 각 숫자에 해당하는 Queue공간을 할당하고 진행합니다. 먼저..

선형 큐 (Linear Queue) 큐는 가장 먼저 들어온 데이터가 가장 먼저 내보내지는 (FIFO : First In First Out) 구조를 가집니다. 선형 큐는 데이터를 집어넣는 Enqueue 기능과 데이터를 내보내는 Dequeue 기능을 제공합니다. ■Enqueue 기능 Enqueue는 큐 자료구조에 데이터를 집어 넣는 기능을 수행합니다. 영화 매표소에 사람들이 줄을 선다고 생각해봅니다. 이때 매표소 가장 앞사람을 가르키는 것을 front라 하고 마지막에 서있는 사람을 가르키는 것을 rear이라고 부릅니다. 1번이 Enqueue 되어진 상태입니다. 첫 번째로 줄을 선 사람이므로 front와 rear이 둘다 1번을 가르키고 있습니다. 다음으로 2번이 Enqueue 기능을 수행 한 상태입니다. Fr..

스택 (Stack) 스택(Stack)은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO- Last In First Out)으로 되어있습니다. 자료를 넣는 것을 PUSH라고 하고 넣어둔 자료를 꺼내는 것을 POP이라고 합니다. ■ 스택 입/출력 방식 실제로 스택이 어떤 식으로 자료가 입/출력 되는지 살펴 보겠습니다. 상자안에 책을 쌓는다고 생각을 하면 됩니다. 즉 가장 먼저 넣은 책은 가장 나중에 꺼낼 수 있으며, 가장 최근에 넣은 책을 가장 먼저 뺄수 있습니다. 가장 먼저 5를 PUSH 합니다. 스택 자료 구조에 가장 아래에 위치하게 됩니다. 차례대로 PUSH 4, PUSH 3을 한 결과입니다. POP 2회를 실시하게 되면 출력 결과는 3,4가 됩니다. 즉 3은 가장 나중에 입력 되었지만 ..

역할 사슬 패턴 (Chain Of Responsibility) 여러 개의 객체 중에서 어떤 것이 요구를 처리할 수 있는지를 사전에 알 수 없을 때 사용됩니다. 즉 요청 처리가 들어오게 되면 그것을 수신하는 객체가 자신이 처리 할 수 없는 경우에는 다음 객체에게 문제를 넘김으로써 최종적으로 요청을 처리 할 수 있는 객체의 의해 처리가 가능하도록 하는 패턴입니다. 구조 (Structure) ● Handler : 요청을 처리하기 위한 수신자들이 가져야 할 인터페이스를 정의 ● ConcreteHandler : Handler 인터페이스 구현, 각자가 요청 종류에 따라 자신이 처리 할 수 있는 부분을 구현 ● Client : 맨 처음 수신자에게 처리를 요구함 예제 예제는 역할 사슬 패턴을 사용하여 1~20까지의 반..

퍼사드 패턴 (Facade Pattern) Facade는 "건물의 정면"을 의미하는 단어로 어떤 소프트웨어의 다른 커다란 코드 부분에 대하여 간략화된 인터페이스를 제공해주는 디자인 패턴을 의미합니다. 퍼사드 객체는 복잡한 소프트웨어 바깥쪽의 코드가 라이브러리의 안쪽 코드에 의존하는 일을 감소시켜 주고, 복잡한 소프트웨어를 사용 할 수 있게 간단한 인터페이스를 제공해줍니다. 동기 어떤 사람이 영화를 보고자 합니다. 영화를 보기 위해서는 다음과 같은 과정을 거치게 됩니다. 음료를 준비한다 -> TV를 켠다 -> 영화를 검색한다 -> 영화를 결제한다 -> 영화를 재생한다. 123456789101112public void view(){ Beverage beverage = new Beverage("콜라"); Re..