고민의 흔적

최대 힙 11279번

내가 떠올린 풀이 해설

이 문제는 단순히 우선순위 큐를 이용하면 해결할 수 있는 문제이다. 우선순위 큐의 Collections.reverseOrder를 이용하면 poll를 하면 배열에서 큰 숫자대로 출력된다. 0일 때 배열에서 제일 큰 수가 출력되도록 문제를 풀면 된다.

정확한 풀이

import java.util.*;
import java.io.*;
public class Baek11279 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());
		for(int i = 0; i < n; i++) {
			int m = Integer.parseInt(br.readLine());
			if(m != 0) {
				que.offer(m);
			}
			else {
				if(que.isEmpty()) {
					System.out.println(0);
				}
				else {
					System.out.println(que.poll());
				}
			}
		}
	}
}

Four Squares 17626번

내가 떠올린 풀이 해설

dp는 점화식을 떠올리는게 제일 어렵다. 제일 작은 수부터 계산을 해보면 1은 1개, 2 2개, 3 3개, 4  1개, 5  2개, 6  3개, 7  4개, 8  2개, 9  1개이다. 어떤 수 i의 최적의 해는 i 보다 작은 모든 제곱수 들 중 i - (제곱수)를 한 해 중 가장 작은 해에 1을 더한 값을 의미합니다. 그러면 점화식은 dp [i] = min(dp [i - j * j]) + 1 이렇게 작성할 수 있다. 작성한 점화식을 이용해 2중 for문을 이용해 풀면 답이 나오는 문제이다.

정확한 풀이

import java.util.*;
public class Baek17626 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] dp = new int[n + 1];
		dp[1] = 1;
		int min = 0;
		// 점화식 dp[i] = min(dp[i - j * j]) + 1
		for(int i = 2; i <= n; i++) {
			min = Integer.MAX_VALUE;
			for(int j = 1; j * j <= i; j++) {
				int tmp = i - j * j;
				min = Math.min(min, dp[tmp]);
			}
			dp[i] = min + 1;
		}
		System.out.println(dp[n]);
	}
}

오늘의 회고

오늘은 한주를 시작하는 월요일입니다. 이번 주도 열심히 공부하고 알고리즘 문제를 풀겠습니다. 벌써 제가 5월 13일에 퇴사하고 취업 준비한 지 2달이 지났습니다. 아직 부족한 것이 많은데 시간이 금방 지나갔습니다. 원래 퇴사하고 그전에 있던 회사에서 느낀 점 퇴사한 이유 취업준비에 대한 다짐을 쓴 글을 취업 준비하기 첫날에 쓰려고 했는데 쓰고 지우 고를 반복하다가 아직까지 작성하지 못했습니다. 취업 준비한 지 2달쯤 지났고 해이해진 정신상태를 다시 잡기 위해 다음 주 까지는 작성하겠습니다.

스택

스택은 삽입과 삭제 연산이 후입 선출 LIFO로 이뤄지는 자료구조이다. 후입 선출은 삽입과 삭제가 한쪽에서만 일어나는 특징이 있다.

스택 용어

위치

• top : 삽입과 삭제가 일어나는 위치를 뜻한다.

연산

• push : top 위치에 새로운 데이터를 삽입하는 연산
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산

스택의 중요성

스택은 깊이우선탐색, 백트래킹 종류의 알고리즘에 사용되므로 반드시 알아 두어야 한다.

후입 선출은 개념 자체가 재귀 함수 알고리즘 원리와 같다.

큐 

큐는 삽입과 삭제 연산이 선입선출 FIFO로 이뤄지는 자료구조이다. 스택과 다르게 먼저 들어온 데이터가 먼저 나간다. 그래서 삽입과 삭제가 양방향에서 이뤄진다.

큐 용어

• rear : 큐에서 가장 끝 데이터를 가리키는 영역이다.
• front : 큐에서 가장 앞의 데이터를 가리키는 영역이다.
• add : rear 부분에 새로운 데이터를 삽입하는 연산이다.
• poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
• peek : 큐의 맨 앞에 있는 데이터를 확인할 때 사용하는 연산이다.

큐는 너비 우선 탐색에서 자주 사용하므로 중요한 자료구조입니다.

우선순위 큐

우선순위 큐는 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다.

큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다. 우선순위 큐는 일반적으로 힙을 이용해 구현하는데 힙은 트리 종류 중 하나이다. 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다. 

최대 힙(Max Heap)이란?

• 최대 힙(Max Heap)은 부모 노드가 자식 노드보다 값이 큰 완전 이진트리를 의미한다.
• 최대 힙의 루트 노드는 전체 트리에서 가장 큰 값을 가지는 특징이 있다.
• 항상 전체 크리가 최대 힙 구조를 유지하도록 자료구조를 설계해야 한다.
• 최대 힙도 큐를 기반으로 동작하기 때문에 push, pop이라는 함수가 있다.

우선순위 큐와 큐의 차이점

• 일반적인 큐: 선형적인 형태를 가지고 있다.
• 우선순위 큐: 트리(Tree) 구조로 보는 것이 합리적이다.

시간 복잡도

• 우선순위 큐의 삽입과 삭제는 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도이다.
• 우선순위 큐를 이용한 정렬은 𝑂(𝑁𝑙𝑜𝑔𝑁)의 시간 복잡도이다.