자료구조와 알고리즘 입문16 Chapter 05-3. 재귀 알고리즘_하노이의 탑 하노이의 탑(towers of Hanoi)작은 원반이 위에, 큰 원반이 아래 위치하도록 쌓은 원반은 3개의 기둥 사이에서 옮기는 문제원반은 1개씩만 옮길 수 있고 큰 원반에서 작은 원반 순으로 쌓으면서 최소 횟수로 옮겨야 함 하노이의 탑package ch05_3;import java.util.Scanner;// 하노이의 탑public class Ex01_hanoi { // no개의 원반을 x번 기둥에서 y번 기둥으로 옮김 static void move(int no, int x, int y) { if (no > 1) { move(no - 1, x, 6 - x - y); } System.out.printf("원반[%d]을(를) %d번 기둥에.. 2024. 8. 11. Chapter 05-2. 재귀 알고리즘_재귀 알고리즘 분석 재귀 함수 이해package ch05_2;import java.util.Scanner;// 재귀 함수 이해public class Ex01_recur { // 재귀 함수 static void recur(int n) { if (n > 0) { recur(n - 1); System.out.println(n); recur(n - 2); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("정수를 입력하세요.: "); int x = scan.. 2024. 8. 11. Chapter 05-1. 재귀 알고리즘_재귀 알고리즘의 기본 재귀란?어떤 사건이 자기 자신을 포함하고 있거나 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라고 함재귀의 개념을 사용하면 1부터 2, 3, …과 같이 무한히 계속되는 자연수를 아래와 같이 정의 가능1은 자연수 입니다.자연수 n의 바로 다음 정수도 자연수입니다.재귀적 정의(recursive definition)를 사용하여 무한으로 존재하는 자연수를 위의 두 문장으로 정의함 팩도리얼 구하기음이 아닌 정수 n의 팩토리얼(factorial) n!은 아래와 같이 재귀적으로 정의 가능0! = 1n > 0 이면 n! = n * (n - 1)!예를 들어, 10의 팩토리얼인 10!은 109!로 구할 수 있고, 9!은 98!로 구할 수 있음 팩토리얼값을 재귀적으로 구함package ch05_1;im.. 2024. 8. 11. Chapter 04-2. 스택과 큐_큐란 큐(queue)스택과 마찬가지로 데이터를 일시적으로 쌓아 놓는 자료구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out)큐에 데이터를 넣는 작업 인큐(en-queue), 데이터를 꺼내는 작업 디큐(de-queue) int형 고정 길이 큐(링 버퍼 사용하지 않고 구현)package ch04_2;// int형 고정 길이 큐(링 버퍼 사용하지 않고 구현)public class IntArrayQueue { private int[] que; // 큐용 배열 private int capacity; // 큐 용량 private int num; // 현재 데이터 개수 // 실행 시 예외 - 큐가 비어있음 public class EmptyIn.. 2024. 8. 4. Chapter 03-3. 검색 알고리즘_이진 검색 이진 검색(binary search)요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 → 데이터가 키값으로 이미 정렬(sort)되어 있는 것이 전제 조건종료 조건은 일치하는 값을 찾거나 더 이상 검색 범위가 없을 때선형 검색보다 빠르게 검색 가능 이진 검색package ch03_3;import java.util.Scanner;// 이진 검색public class Ex10_binSearch { // 요솟수가 n개인 배열 a에서 key와 같은 요소를 이진 검색 static int binSearch(int[] a, int n, int key) { int pl = 0; // 검색 범위의 첫 인덱스 int pr = n - 1; // 검색 범위의 끝 인덱스 .. 2024. 8. 4. 이전 1 2 3 4 다음