안녕하세요!
오늘은 공부한 부분집합, 스택, 큐에 대해서 작성해보려고 합니다.
부분집합
집합에 포함된 원소들을 부분적으로 선택하는 것입니다.
다수의 알고리즘은 최적의 부분 집합을 찾는 해법이 자주 쓰입니다.
부분집합 분석해보기
부분집합의 수는 집합의 원소가 n 개일 때, 공집합을 포함해서 2^n 개 입니다.
즉, 원소를 부분집합에 포함하거나 포함하지 않는 경우를 모두 적용한 것입니다.
연장선상으로 시간복잡도는 O(2^n) 이 될 것입니다.
n 이 30이라면 약 10억번의 연산이 필요하니, 비효율적인 시간복잡도에 속한다고 할 수 있습니다!
간단한 코드로 보자
재귀적으로 구현을 하는 방법입니다.
static int[] input;
static boolean[] isSelected;
static int N; // 부분집합 원소 개수
static void subset(count) {
if (count == N) System.out.println("부분집합 완성");
else { // 현재 원소를 포함하거나 포함하지 않거나 두 가지로 재귀
isSelected[count] = true;
subset(count+1);
isSelected[count] = false;
subset(count+1);
}
}위의 방법은 부분집합 원소의 개수가 3개라고는 했지만, 공집합도 포함됩니다.
그래서 모두 원소를 포함하도록 한다면 조합과 같은 로직이 완성될 것입니다.
스택
스택은 LIFO (Last-In-First-Out) 형태의 선형 구조 자료구조입니다.
자료 간의 관계가 1대 1이고, 처음 삽입된 데이터가 가장 나중에 삭제되는 구조이죠.
스택은 삽입과 삭제가 제한적입니다. 한 곳에서만 이뤄집니다. (입구/출구가 동일)
따라서 조회/삭제가 삽입의 역순이 됩니다.
간단한 예시로는 배낭에 가장 처음 넣은 짐은 위부터 순서대로 꺼냈을 때 가장 나중에 꺼내지는 것과 비슷합니다.
스택 분석해보기
스택에 저장된 원소 중 가장 마지막 원소는 top 이라고 합니다.
다른 말로는 가장 마지막에 삽입된 원소라고 할 수 있습니다.
Java에서는 스택을 java.util.Stack 이라는 API로 제공해주고 있어 쉽게 사용할 수 있습니다.
스택의 연산은 아래와 같습니다.
push: 삽입pop: 삭제 (삽입의 역순으로 삭제)peek: 스택 top의 요소를 조회 (삭제가 아님)
그 외에도 컬렉션에서 쓰이는 isEmpty , size 메소드도 사용할 수 있습니다.
알고리즘에서의 스택
보통 문자열 문제에서 자주 쓰입니다.
괄호를 검사하는 부분이나, 기호를 삭제하거나 옮기는 알고리즘 문제들에서 쓰입니다.
또한 연산에도 쓰입니다. 단순 연산이 아닌 수식을 중위표기법에서 후위표기법으로 바꾼다던지, 후위표기법 수식의 계산 등으로 단골 문제입니다.
백준 후위표기식 문제 (골드3)
백준 탑 문제 (골드5)
개발에서의 스택
스택은 프로그래밍 언어에서 메소드(함수)를 실행할 때 사용되는 메모리입니다.
메소드는 실행하는 순서대로 스택에 삽입되며, 가장 나중에 실행한 메소드부터 실행되죠.
그 외에도 브라우저가 있습니다.
브라우저는 뒤로가기를 통해 페이지를 이동했던 역순으로 되돌아갈 수 있습니다.
큐
스택과 마찬가지로 삽입과 삭제의 위치가 제한적입니다.
큐의 삽입은 Rear , 꼬리 부분에서 발생합니다.
큐의 삭제는 Front , 머리 부분에서 발생합니다.
스택과는 반대로 FIFO (First-In-First-Out) 구조를 가지며 역시 선형적인 자료구조입니다.
따라서 가장 처음 삽입된 원소가 가장 처음 삭제되는 원리입니다.
큐 분석해보기
큐는 자바에서 제공하는 API가 따로 없습니다.
보통 LinkedList를 사용하곤 합니다.
java.util.Queue 는 큐에 필요한 연산을 선언해놓은 인터페이스입니다.
큐의 연산은 아래와 같습니다.
enQueue: 삽입 (offer()메소드로 사용)deQueue: 삭제 (poll()메소드로 사용)
큐는 LinkedList 클래스를 실제 객체로 구현하지만, 참조 변수의 타입을 Queue 로 선언하면 사용하는 메소드를 한정지을 수 있어서 좋습니다.
만약 LinkedList 를 사용한다면, addLast 와 같은 메소드들도 모두 사용이 가능해질 것입니다.
마지막에 추가하는 건 큐 자료구조에 해당하지 않기 때문에 Queue 타입 선언을 권장드립니다!
개발에서의 큐
큐는 보통 버퍼로 많이 활용됩니다.
버퍼는 데이터를 입력받고, 출력하기 전에 데이터를 모아놓는 메모리 영역입니다.
보통 입출력 및 네트워킹에서 사용되며 입력받은 순서대로 출력해야하기 때문에 FIFO 구조인 큐를 사용합니다.
스택과 큐 주의할 점
스택에 요소가 없을 때, stack.peek() 또는 stack.pop() 을 실행한다면, 이것은 에러가 발생합니다.
따라서 연산 전에 stack.isEmpty() 를 활용해 비어있는지 여부를 체크해야 합니다.
하지만 큐는 queue.poll() 또는 queue.peek() 을 실행해도 에러가 발생하지 않고 null을 리턴합니다.
queue.remove() 를 사용하면 에러가 발생합니다.
따라서 큐도 연산 전에 queue.isEmpty() 또는 queue.poll() == null 등의 처리가 필요합니다.
마무리
오늘은 이미 원리는 알고 있던 스택과 큐, 부분집합에 대해서 배워서 정리해봤습니다.
원리는 알아도 여전히 알고리즘에 적용하기란 어렵네요..
포스팅 읽어주셔서 감사합니다 :)
