[코드트리 조별과제] 6주차 - 누적합 / TreeSet / DP

JYC·2024년 8월 25일

[코드트리 조별과제]

목록 보기

5/5

6주차에는 INTERMEDIATE MID에서 누적합 알고리즘과 TreeSet에 대해 학습했고, 문제은행 중 기억에 남는 문제를 가져왔다.

연속한 K개의 숫자

유형	문제 경험치	난이도
Intermediate Mid / Shorten time Technique / Prefix Sum	60xp

[문제링크]에서 문제를 참고하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    //누적합 문제
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[n+1];
		int[] sum = new int[n+1];
		Arrays.fill(arr, 1);
		
		for(int i=0; i<b; i++) {
			int num = Integer.parseInt(br.readLine());
			arr[num]=0;
		}
		sum[1]=arr[1];
		
		for(int i=2; i<=n; i++) {
			sum[i] = sum[i-1]+arr[i];
		}
		
        //최대 수를 구한 후, (k - 최대)를 하면 최소 개수를 구할 수 있다.
		int min_num =0;
		for(int i=1; i<=n-k; i++) {
			min_num = Math.max(min_num, (sum[i+k]-sum[i]));
		}
		
		min_num = k - min_num;
		
		System.out.println(min_num);
	}
}

누적합 알고리즘을 이용해 누적합을 구한 후, 입력된 K 값에서 최대를 뺌으로서 최소를 구했다.

범위 내에 있는 점의 수 2

유형	문제 경험치	난이도
Intermediate Mid / Shorten time Technique / Prefix Sum	60xp

[문제링크]에서 문제를 참고하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	//누적합 문제
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[1000003];
		int[] sum = new int[1000003];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			int num = Integer.parseInt(st.nextToken());
			arr[num]=1;
		}
		
		for(int i=1; i<=1000000; i++) {
			sum[i] = sum[i-1]+arr[i];
		}
		
		for(int i=0; i<Q; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(a==0) {
				sb.append(sum[b]+"\n");
			}
			else {
				sb.append((sum[b] - sum[a-1])+"\n");
			}
		}
		
		System.out.println(sb.toString());	
	}
}

각기 사람마다 다양한 이유가 있겠지만, 내가 생각하기에 이 문제가 정답률 49%를 기록한 것에는, '0 ≤ A ≤ B ≤ 1,000,000 즉 A가 0일 수 있다는 점을 간과해서'라고 생각한다.

문제 자체에는 큰 어려움이 없었으나, 문제를 꼼꼼히 읽는 습관을 가지는 것이 중요할 것 같다...

문제 추천 시스템 1

유형	문제 경험치	난이도
Intermediate Mid / 중급 자료구조 / TreeSet	40xp

[문제링크]에서 문제를 참고하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;

class Node implements Comparable<Node>{
	int P;
	int L;
	
	public Node(int P,int L) {
		this.P = P;
		this.L = L;
	}
	
	public int compareTo(Node n) {
		if(this.L == n.L) {
			return this.P - n.P;
		}
		else {
			return this.L - n.L;
		}
	}
}
public class Main {
    //TreeSet 문제
	static TreeSet<Node> tree = new TreeSet<Node>();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		
		for(int i=0; i<n; i++) {
			st= new StringTokenizer(br.readLine());
			int P = Integer.parseInt(st.nextToken());
			int L = Integer.parseInt(st.nextToken());
			
			tree.add(new Node(P,L));
		}
		
		int m = Integer.parseInt(br.readLine());
		
		for(int i=0; i<m; i++) {
			st= new StringTokenizer(br.readLine());
			String command = st.nextToken();
			if(command.equals("rc")) {
				int num = Integer.parseInt(st.nextToken());
				if(num==1) {
					sb.append(tree.last().P+"\n");
				}
				else {
					sb.append(tree.first().P+"\n");
				}
			}
			else if(command.equals("ad")) {
				int P = Integer.parseInt(st.nextToken());
				int L = Integer.parseInt(st.nextToken());
				
				tree.add(new Node(P,L));
			}
			else {
				int P = Integer.parseInt(st.nextToken());
				int L = Integer.parseInt(st.nextToken());
				tree.remove(new Node(P,L));
			}
		}
		System.out.println(sb.toString());
	}
}

TreeSet과 Class를 통한 정렬 기준을 만들어, 해결하는 문제이다.

어렵다기보다는 이렇게 문제를 풀어야할 때가 올 수 있으므로 기억하자는 의미에서 가져왔다.

Comparable을 통해 정렬 기준을 만들어 정렬하는 방법은 여러 곳에서 충분히 쓰일 수 있을 것이라 생각한다.

물건 구입 비용 - (문제은행 Silver 2)

유형	출처
DP	일반연습 / 문제은행

[문제링크]에서 문제를 참고하자.

이 문제도 Class를 활용해 정렬 기준을 만들었다... 하지만 쓸모가 있는지는 잘 모르겠다.

여튼 물건을 구입하기 위한 최소 비용을 구하는 문제이다.

이 문제를 가져온 이유는 다름이 아닌, 현저히 낮은 정답률때문도 있고, 문제를 꼼꼼히 읽는 걸 좀 연습하라는 의미이기도 하다.

일단 이 문제의 정답률은 무려 27%인데... 사실 문제는 봤을때는 "엥 그정돈가??" 라고 생각했다.

하지만 실제로 직접 풀어보니 나 또한 첫 제출은 틀렸다.

이건 그 당시 제출했던 코드다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Store{
	int set;
	int money;
	
	public Store(int set,int money) {
		this.set = set;
		this.money =money;
	}
}
public class Main {
	//dp 문제
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int p = Integer.parseInt(st.nextToken());
		
		Store[] store = new Store[p];
		int[] dp = new int[n+1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		
		for(int i=0; i<p; i++) {
			st = new StringTokenizer(br.readLine());
			int set = Integer.parseInt(st.nextToken());
			int money = Integer.parseInt(st.nextToken());
			
			store[i] = new Store(set, money);
		}
		
		dp[0]=0;
		for(int i=1; i<=n; i++) {
			for(int j=0; j<p; j++) {
				if(i - store[j].set >= 0) {
					dp[i] = Math.min(dp[i], dp[i-store[j].set] + store[j].money);
				}
			}
		}
		
		System.out.println(dp[n]);
	}
}

그래서 틀린 테스트케이스를 여러 번 검토하고, 문제를 다시 읽어봤더니...

여러 개의 상점에서 물건을 최소 n개 구매하기 위해서 드는 최소 비용을 구하는 프로그램을 작성해보세요.

그렇다. n이라는 수를 딱 맞출 필요가 없었다.

이 조건 하나로 답이 틀리게 되면서 멘붕이 빠졌던 것이다...

그래서 if문 조건에 else문을 추가해 n을 넘어가도 상관없도록 고쳤다.

그리고 이 조건과 더불어 DP 식도 조금 수정했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Store implements Comparable<Store>{
	int set;
	int money;
	
	public Store(int set,int money) {
		this.set = set;
		this.money =money;
	}
	
	public int compareTo(Store s) {
		return s.money - this.money;
	}
}
public class Main {
	//dp 문제
	static int MAX_NUM = 1000000001;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int p = Integer.parseInt(st.nextToken());
		
		Store[] store = new Store[p];
		int[] dp = new int[n+1];
		Arrays.fill(dp, MAX_NUM);
		
		for(int i=0; i<p; i++) {
			st = new StringTokenizer(br.readLine());
			int set = Integer.parseInt(st.nextToken());
			int money = Integer.parseInt(st.nextToken());
			
			store[i] = new Store(set, money);
		}
		
		dp[0]=0;
		for(int i=0; i<=n; i++) {
			for(int j=0; j<p; j++) {
				if(i + store[j].set <= n) {
					dp[i + store[j].set] = Math.min(dp[i + store[j].set], dp[i] + store[j].money);
				}
				else {
					dp[n] = Math.min(dp[n], dp[i]+store[j].money);
				}
			}
		}
		
		System.out.println(dp[n]);
	}
}

문제 자체는 DP를 몇번 풀다보면 접할 수 있는 문제 스타일이다.

만약 본인이 문제를 못풀겠거나 어느 부분이 문제인지 모르겠다면 문제를 다시 한번 읽어보는 습관을 가지자. (나부터 제발)

6주차까지의 코드트리 후기

길다면 길고 짧다면 짧은 6주까지 코드트리로 거의 매일 학습했다.

좋은 점은 알고리즘에 대해 미리 조금 공부하고 문제를 접할 수 있었다는 것과, 틀렸을 시 틀린 해당 테스트케이스를 볼 수 있다는 것이 가장 좋았다. (이 덕분에 고친 문제가 정말 많다!)

단점은 학생 인증 당시 조금 애를 먹었다는거? 딱히 생각나는 건 없는듯하다.

문제를 많이 푼 것도 아니고, 어려운 문제를 접하면서 익히는 시간을 가진 것도 아니지만, 내가 공부해왔던 여러 알고리즘을 다시 짚고 넘어갈 수 있었다는 점에서 충분히 만족스러웠다.

코드트리 조별과제 레포트 제출로 일주일, 일주일 생명 연장권 늘려가며 했는데, 생각보다 얻어간 것이 많았다.

겨울방학때도 코드트리 조별과제가 한번 더 있었으면 좋겠다.

업로드중..

무엇보다 꾸준히 코드트리 레포트를 작성해서 나한테 자극과 동기를 줬던 친구에게도 감사하다.

없었으면 중간에 포기했을 수도 있을 것 같은데, 꾸준히 코드트리를 상기시켜줘서 덕분에 끝까지 바지끄댕이 잡고 여기까지 올 수 있었다.

JYC

열심히 하기 1일차

이전 포스트

[코드트리 조별과제] 6주차 - 누적합 / TreeSet / DP