키리Kirri's IT노트

: factorial 메서드 혹은 gcd 메서드와 달리 메서드 안에서 재귀 호출을 여러 회 실행하는 메서드를 순수하게(genuinely) 재귀적이라고 하며, 실제 동작은 매우 복잡하다. 이러한 복잡한 구조를 가진 재귀 메서드를 보다 전략적으로 분석하기 위해 하향식, 상향식의 두 방향으로 분석한다. 1 2 3 4 5 6 7 static void recur(int n) { if(n > 0) { recur(n - 1); System.out.println(n); recur(n - 2); } } ・하향식 분석(top down) -매개변수 n으로 4를 전달한 경우 [1] recur(3) 실행 [2] 4를 출력 [3] recur(2) 실행 [1]로 인해 재귀 호출이 실행되고, 모든 재귀 호출을 수행한 뒤 [2]가 실..

재귀(Recursive) : 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용해 정의될 때 재귀적(recursive)이라고 한다. 재귀를 사용하면 프로그램도 간결하게 할 수 있다. 재귀적 정의(recursive definition) 예: 1. 1은 자연수이다. 2. 자연수 n의 바로 다음 수도 자연수다. ・팩토리얼 구하기 -음이 아닌 정수 n의 팩토리얼(n!) 1. 0! = 1 2. n > 0 이면 n! = n x (n - 1)! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class Factorial { static int factorial(int n) { if(n > 0) return n * factorial(n - 1); else return ..

: 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조. 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO; First In First Out)인 점이 스택과 다르다. *인큐(enqueue): 큐에 데이터를 넣는 작업 *디큐(dequeue): 데이터를 꺼내는 작업 ・배열로 큐 만들기 -인큐: 리어(rear)에 새로운 데이터를 저장. O(1)의 복잡도로 적은 비용으로 구현 가능 -디큐: front에서 데이터를 꺼낸 다음 두 번째 이후의 요소를 모두 맨 앞으로 이동. O(n)의 복잡도, 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어짐 ・링 버퍼(ring buffer)로 큐 만들기 : 배여래의 처음과 끝이 연결되어있는 자료구조로, 배열 요소를 앞쪽으로 옯기지 않는다. 논리적으로..

: 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다. (LIFO, Last Input First Out) *푸시(push): 스택에 데이터를 넣는 작업 *팝(pop): 스택에서 데이터를 꺼내는 작업 ・스택 만들기 1. 생성자 IntStack : 스택 본체용 배열을 생성하는 등 준비 작업 수행 1 2 3 4 5 6 7 8 9 public IntStack(int capacity) { ptr = 0; max = capacity; try { stk = new int[max]; } catch(OutOfMemoryError e) { max = 0; } } 2. 푸시 메서드 push : 데이터를 푸시하는 메서드 1 2 3 4 5 public int push(int x) th..

: 데이터가 키 값으로 이미 정렬(sort)되어 있을 때, 선형 검색보다 빠르게 검색 가능 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 ・이진 검색 알고리즘의 종료 조건 ① a[pc]와 key가 일치하는 경우(검색 성공): 대략 ⌈log(n-1)⌉회 비교 ② 검색 범위가 더 이상 없는 경우(검색 실패): ⌈log(n+1)⌉회 비교 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 static int binSearch(int[] a, int n, int key) { int pl = 0; int pr = n - 1; do { int pc = (pl + pr) / 2; // 중앙 요소의 인덱스 if(a[pc] == key) return pc; else if(a[..