재귀 알고리즘 분석 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()와는 다르게 메서드 안에서 재귀 호출을 ..
재귀? 어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라 한다. 즉 프로그램에서 사건이 발생할 경우 해당 메서드를 호출하며, 호출하여 작업을 수행하는 중 작업이 종료되지 않은 상태에서 자신을 다시 호출하는 경우이다. 정확히는 자기 자신을 호출하는 것이 아닌 자신과 같은 메서드를 작업 중에 호출해서 작업을 처리하는 것이다. Java의 메서드 호출 시 호출 스택에 작업들이 쌓이는 것을 생각해보면 좀 더 잘 이해를 할 수 있다. main() -> a()를 호출 a() -> a()를 호출 a() -> a()를 호출 하면 현재 호출 스택에 main() -> a() -> a() -> a() 이런식으로 쌓이게 된다. 마지막으로 호출된 메서드가 종..
큐 ? - 스택과 같이 데이터를 일시적으로 쌓아 놓는 자료구조 - FIFO(First In First Out) 방식으로 데이터를 입`출력 👉 먼저 들어온 데이터 순으로 먼저 나오게 된다. / 데이터 순서가 보장된다. -Java에서 Queue는 인터페이스이며, 이를 구현한 구현체들이 있는데 이를 활용하여 사용할 수 있다. 그 중 하나가 LinkedList이다. 👉 큐의 경우 데이터의 순서가 있기에 List형 컬렉션을 사용해야하는데 FIFO구조이기에 ArrayList를 사용할 경우 삭제 시 배열의 요소들 간에 이동이 발생한다. 그렇기에 LinkedList로 구현하는 것이 유리하다. 용어 ? 인큐(en-queue) : 큐에 데이터를 저장하는 작업 디큐(de-queue) : 큐에서 데이터를 꺼내는 작업 프런트(..
스택이란 ? 데이터를 일시적으로 쌓은 자료구조이다. 입/출력순서는 LIFO(Last In First Out)이다 👉 데이터가 아래부터 순차적으로 쌓이면 꺼낼때는 위부터 순차적으로 뺄 수 있다. 👉 스택사용시 데이터의 순서가 반전된다. 용어 ? push : 스택에 데이터를 넣는 작업 pop : 스택에서 데이터를 꺼내는 작업 Top / 꼭대기 : 스택에서 데이터가 들어오고 나가는 쪽 (위쪽) Bottom / 바닥 : 스택에 가장 최하단 쪽 스택 기능 ? 코드 ? // 스택을 구현해 본 코드 public class IntStack { private int[] stk; // 스택용 배열 private int capacity; // 스택 용량 private int ptr; // 스택 포인터 // 실행 시 예외 :..
이진검색이란? 요소(데이터)가 정렬 된 배열일 때 선형검색보다 좀 더 빠르게 검색할 수 있는 알고리즘. 특징? 1. 검색단계를 한 단계 진행 시마다 검색범위가 대략 절반 가량 줄어든다. ( 시간 복잡도 : O(log n) ) -> 선형검색의 경우 첫 번째 요소부터 마지막 요소까지 순차적으로 검색해나가며 원하는 값을 찾아나가기에 정렬이 크게 필요하지는 않다. 그러나 이진검색의 경우 첫 번째 요소가 아닌 검색 범위의 중앙 요소를 기준으로 원하는 값의 대소여부를 파악하며 범위를 대략 절반씩 줄여나간다. 그렇기에 반드시 데이터가 정렬되어 있어야한다. 2. 검색 요소를 한칸 씩 이동하며 검색하는 것이 아닌 범위의 중앙 요소를 검색 대상으로 한다. -> 검색하는 요소의 위치가 여러 칸으로 이동한다. 코드? publ..
선형검색(순차검색)이란? 요소가 직선형태로 나열된 배열에서 검색하고자 하는 값을 찾을 때까지 맨 앞 요소부터 순차적으로 검색하는 알고리즘 검색 종료 조건? ① 순차적으로 검색하는 중 원하는 값 찾기 성공! (n회 검색) -> 배열 안에 값이 동일한 요소들이 있더라도 가장 먼저 값을 찾으면 검색 종료! ② 마지막 요소까지 검색해도 찾지 못했을 경우 실패!(n+1회 검색) * 요소 하나씩을 검색할 때마다 위 종료조건 2개를 판단해야한다. (=조건판단에 의한 비용발생) 사용 조건? 요소(데이터)가 정렬되어 있지 않은 상태로 저장된 배열에서 원하는 요소(값)을 찾고자 할 때 사용할 수 있는 유일한 방법이다. 코드 ? public class SeqSearch { static int seqSearch(int[] a..