Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 하노이의 탑 설명 1, 2, 3번 기둥 이렇게 3개의 기둥과 크기가 모두 다른 n개의 원판이 있을 때, n개의 원판 모두 1번 기둥에 크기가 큰 원판순으로 아래에 위치되어 있다. 이러한 기둥들을 3번 기둥에 모두 옮겨야 하는데, 한 번에 한 원판만 옮길 수 있고 크기가 작은 원판 위에 크기가 큰 원판을 올릴 수 없다. 이러한 원판 이동을 최소한의 횟수로 옮기는 것이 하노이의 탑의 규칙이다. 하노이의 탑 풀이 가장 위에 있는 원반을 1번원반, 그 아래의 원반을 2번 원반, 가장 아래에 있는 원반을 n번 원반이라고 하면 디테일한 과정 말고 큰 과정을 나열하면 3가지로 압축할 수 있다. 1 ~ n-1번 원반을 2번 기둥에 옮..

일반 재귀 간단 요약 재귀 함수는 정지 조건(재귀 앵커)을 충족하기 전 까지 계속 호출하게 된다. 그러면 함수가 한 번씩 호출될 때마다 파라미터, 리턴값, 리턴 후 돌아갈 위치 등이 스택(메모리 저장공간)에 쌓이게 된다. 재귀 함수를 너무 많이 호출하게 되면 스택의 공간이 모두 차버리는 스택 오버플로가 일어날 수 있다. 꼬리 재귀 static int factorial(int n) { if(n > 0) return n * factorial(n-1); //반환(return)부에 연산이 존재 else return 1; //정지 조건 } 위 코드는 일반 재귀를 이용하여 팩토리얼을 구하는 재귀함수이다. 위 코드는 정지 조건을 충족한 재귀 함수가 1을 리턴을 해야 나머지 재귀 함수의 리턴 값이 정해진다. 아래의 첫..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 재귀 알고리즘의 비재귀적 표현 static void recur(int n) { if(n > 0) { recur(n - 1); System.out.println(n); recur(n-2); } } 위 메소드의 꼬리 재귀를 제거하는 방법과 비재귀적 표현으로 나타내는 방법을 정리하려고 한다. 꼬리 재귀의 제거 메소드의 꼬리에서 재귀 호출하는 메소드 recur(n-2)는 파라미터로 n-2를 전달하여 recur 메소드를 호출한다는 뜻이다. 따라서 이 호출은 'n의 값을 n-2로 업데이트하고 메소드의 시작 지점으로 돌아간다'는 뜻이다. 아래는 위 방법을 그대로 구현한 코드이다. n의 값을 -2만큼 감소한 후 메소드의 시작 지점으로..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 재귀 알고리즘을 분석하는 방법은 아래의 두가지가 있다. 하향식(top down) 분석 방법 상향식(bottom up) 분석 방법 아래의 코드를 바탕으로 하향식과 상향식 분석 방법을 정리하겠다. static void recur(int n) { if(n > 0) { recur(n-1); System.out.println(n); recur(n-2); } } 위 메소드에 파라미터에 4를 넘기면 아래와 같은 결과가 나온다. 하향식 분석 파라미터에 4를 넘기면 recur 메소드는 아래 과정을 순서대로 실행한다. ① recur(3)을 실행 ② 4를 출력 ③ recur(2)를 실행 아래의 그림에서 상자는 recur 메서드의 동작을 나..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 재귀란 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(Recursive)이라고 한다. 재귀는 직접 재귀와 간접 재귀로 나뉜다. 직접 재귀 : 메소드 a가 자신(메소드 a)을 호출 간접 재귀 : 메소드 a가 메소드 b를 호출하고, 메소드 b는 메소드 a를 호출 재귀 메소드는 정지조건(재귀 앵커)을 제대로 설정하지 않으면 무한 루프와 같이 끝없이 재귀 메소드가 호출되므로 유의하여야 한다. 팩토리얼 구하기 음이 아닌 정수 n의 팩토리얼(n!)은 아래처럼 재귀적으로 정의할 수 있다. 0! = 1 n > 0 이면 n! = n * (n-1)! 위의 정의를 그대로 구현하면 아래와 같다. static ..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 큐 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다. 하지만 큐는 스택과 다르게 선입선출(FIFO, First In First Out)이다. 아래의 그림과 같이 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조로 되어 있다. 큐에 데이터를 넣는 작업을 인큐라 하고, 데이터를 꺼내는 작업을 디큐라고 한다. 인큐와 디큐 인큐 위 그림에서 리어(rear)인 53 뒤에 24를 인큐 한다. 이 처리의 시간복잡도는 O(1)이고 적은 비용으로 구현할 수 있다. 디큐 위 그림에서 프론트(front)인19와 22을 디큐 한다. 디큐한 후에는 모든 요소를 앞으로 옮겨야 한다. 이 처리의 시간복잡도는 O(N)이며 ..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 스택 스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다. 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다. 스택에 데이터를 넣는 작업을 푸시라 하고, 스택에서 데이터를 꺼내는 작업을 팝이라고 한다. 이렇게 푸시와 팝을 하는 위치를 꼭대기(top)라 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다. int 배열을 이용한 IntStack 클래스 public class IntStack { private int max; private int ptr; private int []stk; public IntStack(int capaci..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 이진 검색 이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다. 하지만 이진 검색은 데이터가 키 값으로 이미 정렬되어 있다는 전제 조건이 있어야 한다. 이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 시간 복잡도 측면에서 선형 검색은 O(N)이지만 이진 검색은 O(log N)을 가지므로 이진 검색이 훨씬 효율적인 알고리즘이다. 아래와 같은 배열에 오름차순으로 정렬된 데이터에서 39를 찾는 과정을 예로 들면, 먼저 배열 중앙에 위치한 5번째 인덱스부터 검색을 시작한다. 인덱스 5의 값은 31은 39보다 작으므로 검색 대상을 뒤쪽 5개로 좁힐 수 있다. 그런 다음 검..