재귀(3) - 하노이의 탑

하노이의 탑 문제 하노이의 탑은 n개의 크기가 다른 원반을 가장 큰 순서부터 위로 쌓아올린 상태에서 3개의 기둥에 첫번째 기둥부터 마지막 기둥까지 모든 원반을 옮기는 문제이다. 조건1) 1번에 1개의 원반만 움직일 수 있다. 조건2) 큰 원반은 작은 원반 위에 쌓을 수 없다. 하노이의 탑은 한번쯤은 접해봤을 문제이다. 이것을 코드로 어떻게 구현을 해야할까 ? //하노이의 탑 구현코드 static void move(int no , int x , int y){ if(no > 1) move(no - 1 , x , 6 - x - y); System.out.printf("원반[%d]을(를) %c번 기둥에서 %c번 기둥으로 옮김\n",no , 'A'- 1 + x , 'A' - 1 + y); if(no > 1){ m..

• format_list_bulleted 재귀 알고리즘
• · 2022. 9. 24.
• textsms

재귀(2)

재귀 알고리즘 분석 import java.util.Scanner; public class 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 sc = new Scanner(System.in); System.out.print("정수를 입력하세요 : "); int x = sc.nextInt(); recur(x); } } Do it 자료구조와 함께 배우는 알고리즘 입문 p170 실습 5-3문제를 참조해봤다. 재귀(1)에서 다룬 factorial(), gcd()와는 다르게 메서드 안에서 재귀 호출을 ..

• format_list_bulleted 재귀 알고리즘
• · 2022. 9. 19.
• textsms

재귀(1)

재귀? 어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라 한다. 즉 프로그램에서 사건이 발생할 경우 해당 메서드를 호출하며, 호출하여 작업을 수행하는 중 작업이 종료되지 않은 상태에서 자신을 다시 호출하는 경우이다. 정확히는 자기 자신을 호출하는 것이 아닌 자신과 같은 메서드를 작업 중에 호출해서 작업을 처리하는 것이다. Java의 메서드 호출 시 호출 스택에 작업들이 쌓이는 것을 생각해보면 좀 더 잘 이해를 할 수 있다. main() -> a()를 호출 a() -> a()를 호출 a() -> a()를 호출 하면 현재 호출 스택에 main() -> a() -> a() -> a() 이런식으로 쌓이게 된다. 마지막으로 호출된 메서드가 종..

• format_list_bulleted 재귀 알고리즘
• · 2022. 9. 18.
• textsms

큐(Queue)

큐 ? - 스택과 같이 데이터를 일시적으로 쌓아 놓는 자료구조 - FIFO(First In First Out) 방식으로 데이터를 입`출력 👉 먼저 들어온 데이터 순으로 먼저 나오게 된다. / 데이터 순서가 보장된다. -Java에서 Queue는 인터페이스이며, 이를 구현한 구현체들이 있는데 이를 활용하여 사용할 수 있다. 그 중 하나가 LinkedList이다. 👉 큐의 경우 데이터의 순서가 있기에 List형 컬렉션을 사용해야하는데 FIFO구조이기에 ArrayList를 사용할 경우 삭제 시 배열의 요소들 간에 이동이 발생한다. 그렇기에 LinkedList로 구현하는 것이 유리하다. 용어 ? 인큐(en-queue) : 큐에 데이터를 저장하는 작업 디큐(de-queue) : 큐에서 데이터를 꺼내는 작업 프런트(..

• format_list_bulleted 자료구조
• · 2022. 9. 17.
• textsms

스택(Stack)

스택이란 ? 데이터를 일시적으로 쌓은 자료구조이다. 입/출력순서는 LIFO(Last In First Out)이다 👉 데이터가 아래부터 순차적으로 쌓이면 꺼낼때는 위부터 순차적으로 뺄 수 있다. 👉 스택사용시 데이터의 순서가 반전된다. 용어 ? push : 스택에 데이터를 넣는 작업 pop : 스택에서 데이터를 꺼내는 작업 Top / 꼭대기 : 스택에서 데이터가 들어오고 나가는 쪽 (위쪽) Bottom / 바닥 : 스택에 가장 최하단 쪽 스택 기능 ? 코드 ? // 스택을 구현해 본 코드 public class IntStack { private int[] stk; // 스택용 배열 private int capacity; // 스택 용량 private int ptr; // 스택 포인터 // 실행 시 예외 :..

• format_list_bulleted 자료구조
• · 2022. 9. 15.
• textsms

이진검색

이진검색이란? 요소(데이터)가 정렬 된 배열일 때 선형검색보다 좀 더 빠르게 검색할 수 있는 알고리즘. 특징? 1. 검색단계를 한 단계 진행 시마다 검색범위가 대략 절반 가량 줄어든다. ( 시간 복잡도 : O(log n) ) -> 선형검색의 경우 첫 번째 요소부터 마지막 요소까지 순차적으로 검색해나가며 원하는 값을 찾아나가기에 정렬이 크게 필요하지는 않다. 그러나 이진검색의 경우 첫 번째 요소가 아닌 검색 범위의 중앙 요소를 기준으로 원하는 값의 대소여부를 파악하며 범위를 대략 절반씩 줄여나간다. 그렇기에 반드시 데이터가 정렬되어 있어야한다. 2. 검색 요소를 한칸 씩 이동하며 검색하는 것이 아닌 범위의 중앙 요소를 검색 대상으로 한다. -> 검색하는 요소의 위치가 여러 칸으로 이동한다. 코드? publ..

• format_list_bulleted 검색 알고리즘
• · 2022. 9. 13.
• textsms