4일차 정리(큐, 재귀의 기본)

1. 큐

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

- 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(queue) 구조

- 큐에 데이터를 넣는 작업을 인큐(enqueue)

- 데이터를 꺼내는 작업을 디큐(dequeue)

- 데이터를 꺼내는 쪽을 프런트(front)

- 데이터를 넣는 쪽을 리어(rear)

- IntQueue.java

- IntQueueTester.java

실행결과)

2. 재귀의 기본

- 재귀란?

: 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될떄 재귀적(recursive)이 라고 한다.

- 팩토리얼(factorial)

- 유클리드 호재법(Euclidean method of mutual division)

- 재귀 알고리즘의 분석하기 위한 하향식(top down) 분석과 상향식(bottom up)분석을 살펴보고 재귀 알고리즘을 비재귀적으로 구현하는 방법이 있다.

 A. 하향식 분석 : 가장 처음 메서드 호출부터 시작해 계단식을 자세히 조사하는 분석 기법 ex) 숫자 4를 입력하면 그에따른 프로그램 실행순서를 그래프로 그린다.

 B. 상향식 분석 : 하향식 분석과는 대조적으로 아래쪽 부터 쌓아 올리며 분석하는 방법 ex) 숫자 조건 if( n>0 )이라면 1부터 넣어서 출력결과물을 본다.

- 재귀 알고리즘을 비재귀적 표현방법

: 재귀적 코드

: 비재귀적 코드

: InStack.java