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 ! 자료구조와 함께 배우는 알고리즘 입문 자바편

02-1 배열

자료구조 data structure : 데이터 단위와 데이터 사이의 물리적 또는 논리적인 관계

배열 array 

배열은 같은 자료형의 변수로 이루어진 구성요소component가 모인 것입니다.

구성요소

구성 요솟수(길이)

배열의 구성 요소는 자동으로 0으로 초기화 되는 규칙이 있습니다.

배열의 복제 

a.clone()

주사traverse: 배열의 요소를 하나씩 차례로 살펴보는 과정을 알고리즘 용어 

Random클래스의 인스턴스는 일련의 의사 난수를 생성합니다.

난수는 무에서 생성되는 것이 아니라 seed이라는 수의 값을 바탕으로 여러 연산을 수행하여 얻습니다

배열 a의 최댓값 구하기

static int maxOf(int[] a){

  int max = a[0];

  for (int i = 1; i < a.length;i++)

    if (a[i] > max)

      max = a[i];

  return max;

}

배열 요소를 역순으로 정렬하기 

static void swap(int[] a, int idx1, int idx2){

  int t = a[idx1];

  a[idx1] = a[idx2];

  a[idx2] = t;

}

static void reverse(int[] a){

  for(int i = 0; i <a.length/2; i++)

    swap(a, i, a.alength-i-1);

}

두 배열의 비교

static boolean equals(int[] a, int[] b){

  if(a.length != b.length)

    return false;

  for (int i = 0; i < a.length;i++)

    if(a[i] != b[i])

      return false;

  return true;

}

기수 변환

정수값을 임의의 기수로 변환하는 알고리즘 

기수: 수를 나타내는데 기초가 되는 수

서수 사물의 순서를 나타내는 수 

static int cardConvR(int x, int r, char[] d){

  int digits = 0;

  String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

  do {

    d[digists++] = dchar.charAt(x%r);

    x /= r;

   }while(x != 0);

   return digits;

}

전위형 증가 연산자 ++a

++를 앞에 놓으면 식 전체를 평가하기 전에 피 연산자의 값을 증가시킵니다.

후위형 증가 연산자 a++

++를 뒤에 놓으면 식 전체를 평가한 후에 피연산자의 값을 증가시킵니다.

다차원 배열: 

int[][] x = new int[2][4]

2행 4열

서기 year년은 윤년인가?

static int isLeap(int year){

  return (year % 4 == 0 && year $ 100 != 0 || year % 400 == 0 ) ? 1:0;

}

02-2클래스

클래스: 여러 형의 요소를 조합하여 만든 자료구조 

필드 filed데이터 요소

공개클래스 : 클래스 접근 제한자 public을 붙여 선언한 클래스로 , 다른 패키지에서 사용할 수 있는 것

final 클래스 : 클래스 접근 제한자 final을 붙여 선언한 클래스로 , 서브 클래스를 가질 수 없습니다. 

(새로운 클래스를 상속할 수 없습니다.)

파생클래스 :

  direct superclass

  direct subclass

추상클래스 : abstract

중첩클래스 : nested class

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

01-1 알고리즘이란 ?

세 값의 최대값 : 

int max = a;
if(b > max) max = b;
if(c > max) max = c;

이렇게 여러 문장(프로세스)이 순차적으로 실행되는 구조를 순차적(concatenation)구조라고 합니다.

세 값의 중앙값 :

if (a >= b)

  if (b >= c)

    return b;

  else if (a <= c)

    return a;

  else 

    return c;

else if (a > c)

  return a;

else if(b>c)

  return c;

else 

  return b;

연산자: 기호 +- 등

피 연산자 숫자

01-2 반복 

1부터 n까지의 정수 합 구하기 

int sum = 0;

int i = 1;

while ( i <= n){

  sum += i;

  i++;

}

===> 사전 판단 반복 구조 

for 문 반복

int sum = 0;

for (int i = 1; i <= n; i++){

  sum += i;

}

사전 판단 반복: while문과 for문은 처음에 제어식을 평가한 결과가 0이면 루프 본문은 한번도 실행되지 않습니다.

사후 판단 반복: do문은 루프 본문이 반드시 한번 은 실행됩니다.

구조적 프로그래밍: 하나의 입구와 출구를 가진 구조 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법

단축 평가(short circuit evaluation) 논리 연산의 식 전체를 평가한 결과가 왼쪽 피연산자의 평가 결과만으로 정확해지는 경우 오른쪽 피 연산자의 평가를 수행하지 않는데 이를 단축평가라로 합니다.

드로르간 법칙 (De Morgan's laws): 각 조건을 부정하고 논리곱을 논리합으로 , 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다.

다중 루프 

곱셈표 :

for (int i = 1; i<=9; i++){

  for (int j = 1; j<=9; j++){

    System.out.printf("%3d",i*j);

  }

}

직각 이동변 삼각형 출력

for(int i=1; i<=5;i++){

  for (int j=1;j<=i;j++){

    System.out.print("*")

  }

  System.out.println();

}

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