1. 우선순위 큐와 힙 우선순위를 부여하는 기준은 다양하다. 우선순위를 가진 원소를 삽입할 수 있고, 우선순위가 가장 큰 원소를 빼낼 수 있으면 우선순위 큐(Priority Queue)라고 한다. 우선순위 큐는 트리처럼 임의의 값을 가진 원소를 검색하는 기능은 필요 없고 가장 높은 것을 알려주고 삭제할 수 있으면 된다. 우선순위 큐도 선형 자료구조를 이용해서 구현할 수 있지만 더 효율적인 방법이 있다. 바로 힙(Heap)이다. 힙은 대표적인 우선순위 큐로, 완전 이진 트리 구조를 사용한다. 이진 트리: 모든 노드가 2개 이하의 자식을 갖는 트리 포화 이진 트리: 루트부터 모든 노드가 정확히 자식 노드를 2개씩 가지면서 꽉 채워진 트리 완전 이진 트리: 노드 수가 맞지 않아 포화 이진트리를 만들 수 없는 ..
1. 스택이란? 스택이란 가장 뒤에 들어온 데이터가 가장 먼저 나가는 구조의 자료구조다. 스택은 맨 위의 원소만 접근 가능한 것이 특징이며 맨 위의 원소를 스택 탑(top)이라고 한다. 새 원소를 삽입할 때는 스택 탑 바로 윗자리에 원소를 저장한 후 새 원소가 스택 탑이 된다. 그리고 원소를 삭제할 때는 무조건 탑에 있는 원소를 삭제한 후 바로 아래 원소가 스택 탑이 된다. 2. 배열 스택의 구현 public interface StackInterface { public void push(E newItem); public E pop(); public E top(); public boolean isEmpty(); public void popAll(); } public class ArrayStack imple..
재귀란? 예를 들자면 n! = 1 X 2 X 3 X … X (n-1) X n 이고, 여기서 맨 끝의 n을 제외하면 (n-1)!이 된다. 즉 n! = n X (n-1)!이다. 이처럼 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 재귀적 구조를 갖고 있다고 말한다. 재귀 구조의 예 수열 초항이 1이고 공차가 3인 등차수열 public class Main { public static void main(String[] args){ int n = 5; System.out.println(seq(n)); } static int seq(int n) { if(n == 1) { return 1; } else { return seq(n-1) + 3; } } } 재귀 알고리..
