You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
루트 노드에는 항상 최댓값(최대 힙) 또는 최솟값(최소 힙)이 저장되는 완전 이진 트리로 push 및 poll 연산을 O(logN)으로 수행한다.
우선 순위 큐
우선순위가 높은 데이터가 먼저 나가는 자료구조로 주로 힙을 이용한다.
주로 그리디 문제를 풀 때 사용한 것 같다.
이분 탐색
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 O(logN)으로 탐색할 수 있다.
데이터를 정렬해도 상관없고, 데이터 양이 100,000이 넘어가면서 탐색이 필요할 때 사용할 것 같다.
파라메트릭 서치
최적화 문제를 결정 문제로 바꾸어 푸는 것
최적화 문제란 문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제
결정 문제란 (예, 아니오) 이 2개의 답만이 나오는 문제로 주로 이분 탐색을 통해 문제를 해결한다.
파라메트릭 서치를 조사하는 주차에 ‘택배’ 문제가 나왔는데, 이때 택배 문제에서 최댓값을 구하라는 것을 보고 파라메트릭 서치로 풀어보려 했다. 이처럼 언제 파라메트릭 서치를 사용해야 되는지는 감이 안 온다. (문제를 많이 풀어봐야 알 것 같긴 하다.)
컵라면
컵라면 문제를 포함한 그리디 문제를 풀 때 주로 실시간 형식으로 문제를 풀었다. 결과를 다 알고 있기 때문에 뒤에서부터 연산을 진행하는 방식을 알게 되었다.
뒤에서 부터 푸는 자바 코드
BufferedReaderbr = newBufferedReader(newInputStreamReader(System.in));
intn = Integer.parseInt(br.readLine());
List<List<Integer>> nums = newArrayList<>();
for (inti = 0; i <= n; i++) {
nums.add(newArrayList<>());
}
for (inti = 0; i < n; i++) {
StringTokenizerst = newStringTokenizer(br.readLine());
intd = Integer.parseInt(st.nextToken());
intc = Integer.parseInt(st.nextToken());
nums.get(d).add(c);
}
intanswer = 0;
PriorityQueue<Integer> pq = newPriorityQueue<>(Collections.reverseOrder());
for (inti = n; i > 0; i--) {
for (intnum : nums.get(i)) {
pq.add(num);
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
}
System.out.println(answer);
n+1 카드 게임
N+1 문제를 실시간으로 풀려 하니 너무 어려웠지만, 등가 상황 대치에 대한 설명과 접근 방식을 통해 다음 날 풀 수 있었고, 그리디 문제 유형을 하나 더 알게 되었다.
또, 이번에 배열 내에 있는 값을 제거할 때 remove 함수를 처음 사용해 봤다. remove는 O(N)이기 때문에 알고리즘을 풀 때 되도록 pop과 poll을 사용하려 했다. 이번 문제를 통해서 데이터양을 비교해 보고 양이 적다면 remove를 사용해도 되는 것을 배웠다.
자바에서 remove 함수는 int형 또는 Object를 매개변수로 받는다. int형은 해당 인덱스의 값을 제거하고, Object는 해당 객체를 삭제한다. N+1 카드 문제에서는 인덱스의 값을 제거하는 것이 아닌 숫자를 없애야 하므로 Integer.valueOf()를 통해 원시 타입을 객체 타입으로 바꿔서 값을 제거할 수 있는 것을 알게 되었다.
publicintsolution(intcoin, int[] cards) {
intn = cards.length;
List<Integer> handCards = newArrayList<>();
List<Integer> drawCards = newArrayList<>();
for (inti = 0; i < n / 3; i++) {
handCards.add(cards[i]);
}
intidx = n / 3;
inttarget = n + 1;
intanswer = 1;
while (idx < n) {
// draw cardfor (inti = idx; i < idx + 2; i++) {
drawCards.add(cards[i]);
}
idx += 2;
intc1 = -1;
intc2 = -1;
inttemp = Integer.MAX_VALUE;
// 손에 있는 카드로만 해결할 수 있는 경우for (inti = 0; i < handCards.size(); i++) {
for (intj = i + 1; j < handCards.size(); j++) {
intsum = handCards.get(i) + handCards.get(j);
if (sum == target) {
c1 = handCards.get(i);
c2 = handCards.get(j);
}
}
}
if (c1 != -1) {
handCards.remove(Integer.valueOf(c1));
handCards.remove(Integer.valueOf(c2));
answer++;
continue;
}
// 카드 한장을 뽑아야 하는 경우if (coin >= 1 && drawCards.size() >= 1) {
for (inti = 0; i < handCards.size(); i++) {
for (intj = 0; j < drawCards.size(); j++) {
intsum = handCards.get(i) + drawCards.get(j);
if (sum == target) {
c1 = handCards.get(i);
c2 = drawCards.get(j);
}
}
}
if (c1 != -1) {
handCards.remove(Integer.valueOf(c1));
drawCards.remove(Integer.valueOf(c2));
answer++;
coin -= 1;
continue;
}
}
// 카드 두장을 뽑아야 하는 경우if (coin >= 2 && drawCards.size() >= 2) {
for (inti = 0; i < drawCards.size(); i++) {
for (intj = i + 1; j < drawCards.size(); j++) {
intsum = drawCards.get(i) + drawCards.get(j);
if (sum == target) {
c1 = drawCards.get(i);
c2 = drawCards.get(j);
}
}
}
if (c1 != -1) {
drawCards.remove(Integer.valueOf(c1));
drawCards.remove(Integer.valueOf(c2));
answer++;
coin -= 2;
continue;
}
}
break;
}
returnanswer;
}
택배
어떻게 풀어야 하는지 접근 방식을 몰랐기 때문에 푸는데 애를 먹었다. 문제를 풀 때 배낭 문제처럼 풀어야 하나 고민하기도 했지만 구현을 못할 것 같아 포기했다. 검색을 통해 풀이를 보는데도 풀이 방식에 대해 오래 걸렸고, 간신히 이해하며 정리했다.
풀어보니 회의실 배정 문제와 비슷한 것 같았고, 이러한 문제 유형을 여러 번 풀어봐야 해당 풀이 방식 또한 적응할 수 있을 것 같다.
힙
우선 순위 큐
이분 탐색
파라메트릭 서치
컵라면
n+1 카드 게임
택배
어떻게 풀어야 하는지 접근 방식을 몰랐기 때문에 푸는데 애를 먹었다. 문제를 풀 때 배낭 문제처럼 풀어야 하나 고민하기도 했지만 구현을 못할 것 같아 포기했다. 검색을 통해 풀이를 보는데도 풀이 방식에 대해 오래 걸렸고, 간신히 이해하며 정리했다.
풀어보니 회의실 배정 문제와 비슷한 것 같았고, 이러한 문제 유형을 여러 번 풀어봐야 해당 풀이 방식 또한 적응할 수 있을 것 같다.