NAIAHD

04-1. 스택 데이터를 일시적으로 저장하기 위한 자료구조

스택이란: 

스택은 Stack은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로 , 데이터의 입력과 출력 순서는

후입선출LIFO Lst In First Out입니다. 가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다.

스택에 데이터를 넣는 작업을 push 꺼내는 작업을 pop이라고 합니다.

푸시와 팝을 위치하는 위치를 top이라고 하고 , 스택의 가장 아랫부분을 bottom이라고 합니다.

스택 만들기

스택 본체용 배열 : stk

스택 용량: max

스택 포인터 ptr 스택에 쌓여 있는 데이터 수를 나타내는 필드

푸시 메소드 push OverflowIntStackException 

팝 메서드 pop EmptyIntStackException

피크 메서드 peek 스택의 꼭대기에 있는 데이터를 "몰래 엿보는 " 메소드입니다.

검색 메서드 indexOf

스택의 모든 요소를 삭제하는 메서드 clear

용량을 확인하는 메소드 capacity

데이터 수를 확인하는 메소드 size

스택이 비어 있는지 검사하는 메소드 IsEmpty

스택이 가득 찼는지 검사하는 메서드 IsFull

스택안에 모든 데이터를 표시하는 메서드 dump

04-2 큐

가장 먼저 넣은 데이터를 가장 먼저 나오는 선입선출(First In First Out)인 점이 스택과 다릅니다.

큐란: 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조

인큐 enqueue 데이터를 넣은 작업

디큐 dequeue 데이터를 꺼내는 작업

데이터를 꺼내는 쪽을  front

데이터를 넣는 쪽을 rear

링 버퍼 : 배열의 처음이 끝과 연결되었다고 보는 자료구조

큐 클래스 IntQueue

1. 큐로 사용할 배열 que

2. 큐의 최대 용량 max

3. 프런트 front

4. 리어 rear

5. 현재 데이터 수 num

인큐 메서드 enque 인큐에 성공하면 인큐한 값을 그래도 반환합니다.

디큐 메서드 deque  큐에서 데이터를 디큐하고 그 값을 반한하는 메서드 입니다.

프크 메서드 peek :

검색 메서드 indexOf

모든 요소를 삭제하는 메서드 clear

최대 용량을 확인하는 메소드 capacity

데이터 수를 확인하는 메소드 size

큐가 비어 있는지 검사하는 메소드 IsEmpty

큐가 가득 찼는지 검사하는 메서드 IsFull

큐안에 모든 데이터를 표시하는 메서드 dump

05. 재귀 알고리즘

05-1 재귀의 기본

재귀란: 어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적 이 라고 합니다. recursive

재귀적 정의 recursive definition : 무한으로 존재하는 자연수를 위의 두 문장으로 정의 할 수 있습니다.

팩토리얼 구하기 

1. 0! =1

2. n>0이면 n! = n * (n-1)!

static int factorial(int n){

  if(n>0)

    return n * factorial(n-1);

  else

    return 1;

}

직접 재귀 : 자신과 같은 메소드 호출 하면 

간접 재귀 : 메소드 a가 메소드 b를 호출하고  다시 메소드 b가 메소드 a를 호출하는 구조로 이루어집니다.

유클리드 호제법

두 정수의 최대공약수(greatest common division)

static int gcd(int x, int y){

  if(y == 0)

    return x;

  else

    return gcd(y , x % y);

}

05-2 재귀 알고리즘 분석

하향식 분석 top down : 가장 위쪽에 위치한 상자의 메소드 호출부터 시작해 계단식으로 자세히 조사하는 분석 기법

상향식 분석 bottom down :  위쪽부터 분석하는 하향식 분석과는 대조적으로 아래쪽부터 쌓아 올리며 분석하는 방법

05-3 하노이의 탑

하노이의 탑 Towers of Hanoi 작은 원반이 위에 , 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 상이에서 옮기는 문제입니다.

statc void move(int no, int x, int y){

  if (no >1)

    move(no-1, x, 6-x-y);

  if (no >1)

    move(no-1, 6-x-y, y);

}

05-4 8퀸 문제 8-Queen problem: 재귀 알고리즘에 대한 이해를 돕기 위한 예제로 자주 등장할 뿐만 아니라 19세기의 유명한 수학자 카를 프리드리히 가우스 가 잘못된 해답을 낸 사실로도 잘 알려진 문제입니다.

static void set(int i){

  for(int j = 0 ; j < 8; j++){

    if(flag_a[j] == false &&

       flag_b[i+j] == false &&

       flag_c[i-k+7] == false{

      pos[i] = j;

      if (i == 7)

        print();

      else{

        flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = true;

        set(i+1);

        flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = false;

      }

    }

  }

}

divide and conquer분할 정복법 : 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법

출처 : Do it ! 자료구조와 함께 배우는 알고리즘 입문 자바편