[코드트리 챌린지] 5회차(10월 4일 ~ 10월 9일) : 사각형 채우기 3

실력 진단 결과

---

이번주는 DP 공부와 함께 코딩테스트에서 자주 사용하는 자료구조 몇가지 함수들에 대해 정리해 보았다.

 

---

[코드트리] 사각형 채우기 3

import java.io.*;
import java.util.*;
public class Main {
    //dp[0] = 1 , dp[1] = 2, dp[2] = 3, dp[3] = 2, dp[4] = 2
    static int N;
    static long[] dp;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new long[1000+1];
        dp[0] = 1; 
        dp[1] = 2; 
        for(int i = 2; i <= N; i++){
            dp[i] = (dp[i-1] * 2 + dp[i-2] * 3)%1000000007;
            for(int j = i - 3; j >= 0; j--)
                dp[i] = (dp[i] + dp[j] * 2) % 1000000007;
        }
        System.out.println(dp[N]);
    }
}

https://www.codetree.ai/missions/2/problems/rectangle-fill-3?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

---

HashMap

// HashMap
HashMap<K,V> map = new HashMap<>();
map.put(K,V);
map.remove(K);
map.getOrDefault(K);
map.get(K);
Set<K> keys = map.keySet();
List<K> keyList = new ArrayList<>(keys);

---

HashSet

- 시간 복잡도 O(1) 

// HashSet<V> 
HashSet<E> set = new HashSet<>();
set.add(E);
set.remove(E);
set.contains(E);

비교대상 > List였지만, Set으로 바꾸고,

비교대상.contains(E); 로 List의 아이템인 E가 비교대상에 포함되어 있는지 확인할 수 있다.

---

PriorityQueue

PriorityQueue<E> pq = new PriorityQueue<>();
pq.add(E);
pq.size();
pq.isEmpty();
pq.peek();
pq.poll();