키리Kirri's IT노트

: 쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘 ・하노이의 탑 : 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제. 모든 원반은 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여 있다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 된다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다. key. 가장 먼저 맨 아래 원반을 제외한 나머지 원반을 중간 기둥으로 옮겨야 한다. [소스코드] 1 2 3 4 5 6 7 8 9 10 11 static void move(int no, int x, int y) { if(no > 1) move(no - 1, x, 6 - x - y); System.ou..

: 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..