이론
스택
pop은 삭제하고 확인, peek은 단순 확인만
깊이 우선 탐색(DFS), 백트래킹에 효과적. 후입선출은 재귀 함수 원리와 일맥상통하기 때문
물론 스택보다 재귀를 좀 더 쓰긴 함
그래도 구조가 특이해서 가끔 응용문제가 나오니, 원리만 잘 알아두기
큐
선입선출, 양방향에서 삽입과 삭제
추가는 큐의 rear에서, 삭제는 큐의 front에서
너비 우선 탐색(BFS) 구현할 때 자주 사용
큐랑 스택은 배열의 확장판
큐랑 스택은 자료구조 자체를 이용하기도 하지만,
개념을 이해하고 이에 따라 문제 푸는 경우 많음
=> 후입선출, 선입선출 두 원리만 잘 이해하면 됨
우선순위 큐
들어간 순서 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
front에 따라 항상 최댓값 또는 최솟값 위치
힙을 이용해 구현함
관련 문제
풀기 전 문제 개념 쭉 훑어보면서 기록한 내용
문제 11, 스택 수열, 1874번
오름차순은 작은 것부터 큰 순으로, 내림차순은 큰 것에서 작은 순으로
스택에 push하는 순서는 반드시 오름차순을 지키도록 한다
=> PUSH는 무조건 작은 숫자가 먼저
임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지
=> 입력한 수열을 그대로 출력하기
Stack<Integer> stack = new Stack<>();
stack.pop();
StringBuffer bf = new StringBuffer();
bf.append("+\n");
System.out.println(bf.toString());
문제 12, 오큰수, 17298번
스택의 후입선출이 실마리일 때가 있음.
종종 시간 복잡도를 줄이거나 특정한 문제 조건을 손쉽게 해결하는
=> 문제에 접근할 때 혹시 스택을 이용하면 손쉽게 풀리지 않는지 한 번쯤 고민해보세요
int[]A = new int[n]; // 수열 배열 생성
String[] str = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
A[i] = Integer.parseInt(str[i]);
}
=> split 메소드란 게 있구나, 그렇게 중요한 부분은 아니고
myStack.push(0);
=>
//스택 비어있지 않고 현재 수열이 스택 TOP인덱스 가르키는 수열보다 크면
while (!myStack.isEmpty() && A[myStack.peek()] < A[i]) {
ans[myStack.pop()] = A[i]; //정답 배열에 오큰수를 현재 수열로 저장하기
}
=> 스택에 isEmpty() 가 있구나, myStack.peek()이 있구나
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < n; i++) {
bw.write(ans[i] + " ");
// 출력한다
}
bw.write("\n");
bw.flush();
=> BufferedWriter는 이런 식으로 쓰는 구나, 물론 그리 중요한 부분은 아니고, 어거지로 다른 입출력 함수 써도 됨
문제 13, 카드2, 2164번
가장 위의 카드를 가장 아래에 있는 카드 밑으로 옮기는 동작
=> 큐의 선입선출 성질 이용하면 쉽게 구현 가능
Queue<Integer> myQueue = new LinkedList<>();
=> 큐는 링크드리스트로 해주구나
문제 14, 절댓값 힙, 11286번
N의 최대 범위가 100000이므로 O(nlogn) 시간 복잡도 알고리즘으로 풀 수 있다?
=> 시간 복잡도 종류는 logn -> n -> nlogn -> n의 제곱 -> 2의 n제곱 -> n!
=> 이걸 머릿속에 딱 박아둔 다음, 만약 n의제곱이면 10의 10제곱으로 1억을 훌쩍 넘음, 그러니 그 아래 단계인 nlogn 사용 가능 느낌으로 접근
데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬 필요하므로 우선순위 큐로 문제 쉽게 해결 가능
단, 이 문제는 절댓값 정렬이 필요해서 우선순위 큐의 정렬기준을 직접 정의해야 함
PriorityQueue<Integer> MyQueue = new PriorityQueue<>((o1, o2) -> {
int first_abs = Math.abs(o1);
int second_abs = Math.abs(o2);
if (first_abs == second_abs)
return o1 > o2 ? 1 : -1;// 절대값이 같은 경우 음수 우선 정렬
else
return first_abs - second_abs;// 절대값을 기준으로 정렬
});
=> 이 PriorityQueue는 절대값을 기준으로 정렬하며, 절대값이 같은 경우에는 음수 값을 우선으로 정렬합니다.
=> new PriorityQueue<>((o1, o2) -> {...}): 람다 표현식을 사용하여 사용자 정의 비교자를 제공합니다.
=> Math.abs(o1); // 절대값 처리
=> return first_abs - second_abs;: 절대값을 기준으로 정렬합니다. 절대값이 작은 숫자가 먼저 오도록 합니다.
사용자 정의 비교자 (Comparator)
Comparator 인터페이스를 구현하는 가장 일반적인 방법은 익명 클래스 또는 람다 표현식을 사용하는 것입니다. 이 인터페이스에는 compare라는 메소드가 있으며, 두 개의 객체를 비교하여 정수 값을 반환합니다:
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
int first_abs = Math.abs(o1);
int second_abs = Math.abs(o2);
if (first_abs == second_abs) {
return o1 > o2 ? 1 : -1; // 절대값이 같으면 음수 우선
} else {
return first_abs - second_abs; // 절대값 기준 정렬
}
}
});
=> 위 에제처럼 사용자 지정 비교자를 사용 안 하면, 기본적으로 자연 순서(오름차순)로 정렬합니다.
=> 비교자가 양수를 반환하면 스왑하고, 음수를 반환하면 스왑을 안 함
즉 기본은 오름차순 정리임. 두 요소가 있다고 치자고. {3, 5}가 있고 3이 first, 5가 second임. 순서가
보통 앞에 거 - 뒤에 거, 즉 first-second를 해서 first가 크지? 하지만 기본적으로 정렬 알고리즘은 다 오름차순이 디폴트임.
그러니 앞에 거 크니 양수를 반환하고, 그러니 오름차순으로 정리하기 위해 두 객체를 스왑해서 작은 게 앞에 놓는 거임
'CODING TEST > THEORY' 카테고리의 다른 글
임시) 탐색 (0) | 2024.06.09 |
---|---|
[임시] 정렬 (0) | 2024.06.03 |
[임시] 슬라이딩 윈도우 (0) | 2024.05.28 |
[Do it 코테 자바편] 투 포인터 (0) | 2024.05.24 |
[Do it 코테 자바편] 구간 합 (0) | 2024.05.18 |