고양멍멍이

[문제링크]

0. 모든 친구가 얼리-어답터라면 자신도 어답터가 된다

• 얼리-어답터가 아닌 두 사람이 친구라면, 이 둘은 어떤 일이 있어도 얼리-어답터가 되지 못한다

1. 어떤 사람(노드)를 기준으로, 이 사람이 얼리 어답터가 아니려면 이 사람과 친구인 모든 사람이 얼리-어답터여야만 한다

2. 반대로, 어떤 사람이 얼리-어답터이라면 친구의 얼리-어답터 유무는 중요하지 않다

• 친구의 친구가 얼리 어답터가 아니라면 문제가 생기겠지만, 이건 해당 친구 노드를 처리할 때 처리하고, 우선 직접 연결된 친구만 고려한다

3. 친구 없는 사람이라면, 자신이 얼리 어답터인지/아닌지에 조건이 붙지 않는다

4. 특정 사람(노드)을 root로 삼는 subtree 기준으로,

• 이 사람이 얼리-어답터이기 위한 최소 어답터 필요량
  • 3번 정의에 따르면, 친구(자식 노드)의 얼리-어답터 유무는 중요하지 않다
• 얼리어답터가 아니기 위한 최소 어답터 필요량
  • 2번 정의에 따르면, 모든 친구(자식)은 얼리-어답터여야 한다
• 이 두가지를 반환한다
• leaf 노드는 제한이 없으므로 얼리 어답터일때 1, 아닐때 0을 반환한다

5. 즉, 특정 사람(노드)이 얼리-어답터일 때 필요한 최소 어답터 수는

• 모든 자식들의 얼리/not-얼리 결과값 중 작은것의 합계 + 1(자기 자신) 이 된다

6. 특정 사람(노드)이 얼리-어답터가 아닐 때 필요한 최소 어답터 수는

• 모든 자식을듸 얼리 결과값의 합계 가 된다

7. 이 과정을 leaf 노드부터 시작해 root노드까지 진행하면, root가 얼리-어답터일때 / 아닐때 각각의 최솟값을 구할 수 있다

• 둘 중 작은 값을 반환한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static boolean[] isVisit;
	static List<List<Integer>> tree;
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = pint(br.readLine());
		tree = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			tree.add(new LinkedList<Integer>());
		}
		for (int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken()) - 1;
			int m = pint(st.nextToken()) - 1;
			
			tree.get(n).add(m);
			tree.get(m).add(n);
		}
		
		isVisit = new boolean[N];
		int curNode=0;
		isVisit[curNode]=true;
		int[] ans = rec(curNode);
		System.out.println(ans[0]>ans[1]?ans[1]:ans[0]);
	}
	
	static int[] rec(int curNode) {
		if(curNode!=0 && tree.get(curNode).size()==1) {
			return new int[] {1,0};
		}
		int iAmEA=1;
		int iAmNotEA=0;
		for(int nextNode : tree.get(curNode)) {
			if(isVisit[nextNode])continue;
			isVisit[nextNode]=true;
			int[] tmp = rec(nextNode);
			
			iAmEA += Math.min(tmp[1],tmp[0]);
			iAmNotEA += tmp[0];
		}
		
		return new int[]{iAmEA,iAmNotEA};
	}
	
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 두 문자열에 공통으로 등장하는, 가장 길고 연속적인 문자열(LCS) 찾기 (DP)

1. 두 문자열의 각 index i, j 번 문자가 동일했다면 해당 지점의 LCS 길이는?

• 각 문자열의 i-1, j-1번 까지의 LCS + 1이다

2. 예시) abcd 와 bcd의 경우 각 4, 3번째 문자 d가 겹친다

• 이때 LCS 길이는 abc와 bc 두 문자열의 LCS 길이 + 1이다
• abc와 bc는 c가 겹치므로 ab와 b의 LCS + 1,
• ab와 b는 b가 겹치므로 a와 ""의 LCS + 1이다
• a와 ""의 LCS는 0이므로 ab와 b는 1, abc와 bc는 2, abcd와 bcd는 3의 LCS를 가진다
• 다음에 abcde와 bcde를 계산할 때 위 결과를 활용해 3+1 = 4를 얻을 수 있다 <- DP

3. DP로 모든 경우에 대해 LCS를 계산하며, 가장 긴 max값만 저장 후 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char[] fst = br.readLine().toCharArray();
		char[] snd = br.readLine().toCharArray();
		int[][]map = new int[fst.length+1][snd.length+1];
		int max=0;
		for (int i = 1; i < fst.length+1; i++) {
			for (int j = 1; j < snd.length+1; j++) {
				if(snd[j-1]==fst[i-1]) {
					map[i][j]=map[i-1][j-1]+1;
					max = Math.max(max, map[i][j]);
				}
			}
		}
		System.out.println(max);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 사다리게임의 모든 시작점이 자기 자신의 지점으로 끝나도록 조작하는 문제

1. 문제 조건에 3보다 큰 값이면 -1을 출력하게 되어 있으므로, 3까지만 검사해도 된다

2. 재귀를 통해 모든 가능한 경우의 수를 진행한다

• 현 위치와 좌/우 양쪽에 다 사다리가 없으면, 사다리를 설치한다 (isBridgeBuildAble)

3. 설치한 사다리가 3개가 되면, 문제의 조건인 i번 선수가 i번으로 가게 되는지 검사한다 (isLadderValid)

• 하나라도 실패하면 실패이므로, 즉시 반환한다

4. 설치한 사다리가 3개보다 적더라도 답이 나올 수 있다

• 1, 2개의 사다리에도 valid 여부를 검사한다
• 재귀함수의 인자에 사다리 설치 여부를 나타내는 isChanged flag를 두어 사다리 상태가 변경되었을때만 검사한다

5. 나온 결과값이 있다면 출력, 없다면(fail) -1을 출력한다

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

public class Main {
	
	static int fail = 500;
	static int[][] map;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int h = pint(st.nextToken());
		
		map = new int[h][n-1];
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			map[pint(st.nextToken())-1][pint(st.nextToken())-1]=1;
		}
		int ans = rec(0, 0, true);
		
		System.out.println(ans==fail?-1:ans);
	}
	
	static int rec(int cnt, int cur, boolean isChanged) {
		int ret = fail;
		int x = cur/map[0].length;
		int y = cur%map[0].length;
		if(isChanged && cnt<=3) {
			if(isLadderValid(map)) {
				return cnt;
			}
		}
		if(cnt>=3 || x>=map.length) {
			return fail;
		}
		
		//put if possible
		if(isBridgeBuildAble(map, x, y)) {
			map[x][y]=1;
			ret = Math.min(ret, rec(cnt+1, cur+2, true));
			map[x][y]=0;
		}

		//don't put
		ret = Math.min(ret, rec(cnt, cur+1, false));

		return ret;
	}
	
	static boolean isBridgeBuildAble(int[][]map, int x, int y) {
		if(map[x][y]==1
			|| (y-1>=0 && map[x][y-1]==1)
			|| (y+1<map[0].length && map[x][y+1]==1)) {
			return false;
		}
		return true;
	}
	
	static boolean isLadderValid(int[][] map) {
		for(int i=0; i<map[0].length; i++) {
			int cur = i;
			for (int j = 0; j < map.length; j++) {
				if(cur < map[0].length && map[j][cur]==1)cur++;
				else if(cur-1 >= 0 && map[j][cur-1]==1)cur--;
			}
			if(cur != i)return false;
		}
		
		return true;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 내구도/데미지 값을 고려해서 가능한 많은 계란을 깨는 문제

1. 재귀를 사용해서 모든 경우의 수를 진행한다

• 현재 계란이 깨지지 않았다면, 이걸로 다른 깨지지 않은 계란을 친다
• 깨졌다면, 그냥 넘어간다
• 다음번 계란으로 넘어가서 반복한다
• 모든 계란에 대해 시도했다면, 종료하고 깬 계란 수를 관리한다
• 계산 편의, 효율을 위해 깨진 계란의 수를 인자로 관리한다

2. 위 과정에서 나온 값들 중 최댓값을 저장, 출력

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int cnt = pint(br.readLine());
		int[][]egg = new int[cnt][2];
		
		for(int i=0; i<cnt; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int S = pint(st.nextToken());
			int W = pint(st.nextToken());
			egg[i][0]=S;
			egg[i][1]=W;
		}
		
		System.out.println(rec(egg, 0, 0));
	}
	
	static int rec(int[][]egg, int curEgg, int breaked) {
		if(curEgg>=egg.length) {
			return breaked;
		}
		
		if(egg[curEgg][0]<=0) {
			return rec(egg, curEgg+1, breaked);
		}
		
		int ans=breaked;
		for(int i=0; i<egg.length; i++) {
			if(egg[i][0]<=0 || i==curEgg)continue;
			
			egg[curEgg][0]-=egg[i][1];
			egg[i][0]-=egg[curEgg][1];
			
			int tmpBreaked=0;
			tmpBreaked+= egg[curEgg][0]<=0?1:0;
			tmpBreaked+= egg[i][0]<=0?1:0;
			
			ans=Math.max(ans, rec(egg,curEgg+1,breaked+tmpBreaked));
			
			egg[curEgg][0]+=egg[i][1];
			egg[i][0]+=egg[curEgg][1];
		}
		return ans;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 상어와 가장 먼 칸에서의 상어와의 거리를 구하는 문제

1. 이동 방향이 8방향이므로, dir 배열을 8방향으로 구성한다

2. 상어를 기준점으로 주변 칸을 bfs로 탐색한다

• 위치와 거리 정보를 저장하는 class를 만들어 사용한다
• 탐색하며 거리 정보를 칸에 저장한다
• 탐색 중 특정 지점에 현재 거리보다 작거나 같은 값이 저장되있다면, 다른 상어가 더 가깝게 있다는 뜻이므로 탐색을 정지한다

3. 모든 상어로부터 bfs가 종료되면, 가장 거리가 먼 칸을 탐색, 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int[][] dir = new int[][] {
		{1,0},{1,1},{0,1},{-1,1},
		{-1,0},{-1,-1},{0,-1},{1,-1}
	};
	static int[][] distanceMap;
	static int[][] map;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		map = new int[n][m];
		distanceMap = new int[n][m];
		
		for(int i = 0; i < map.length; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < map[0].length; j++) {
				map[i][j] = pint(st.nextToken());
				distanceMap[i][j] = Integer.MAX_VALUE;
			}
		}

		int ans = 0;
		for(int i = 0; i < map.length; i++) {
			for(int j = 0; j < map[0].length; j++) {
				if(map[i][j]==1) {
					dfs(i,j);
				}
			}
		}

		for(int i=0; i<map.length; i++) {
			for(int j=0; j<map[0].length; j++) {
				if(ans<distanceMap[i][j])ans=distanceMap[i][j];
			}
		}
		System.out.println(ans);
	}
	
	static void dfs(int x, int y) {
		Queue<point>qu = new LinkedList<>(); 
		qu.offer(new point(x,y,0));
		distanceMap[x][y] = 0;
		
		while(!qu.isEmpty()) {
			point cur = qu.poll();
			
			for(int d=0;d<dir.length;d++) {
				int nx = cur.x + dir[d][0];
				int ny = cur.y + dir[d][1];
				int depth = cur.depth + 1;
				
				if(nx<0 || nx >= map.length || ny<0 || ny>=map[0].length || distanceMap[nx][ny]<=depth) {
					continue;
				}
				
				distanceMap[nx][ny] = depth;
				qu.offer(new point(nx,ny,depth));
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	

}

class point{
	int x;
	int y;
	int depth;
	public point(int x, int y, int depth) {
		super();
		this.x = x;
		this.y = y;
		this.depth = depth;
	}
}

[문제링크]

0. 동전으로 특정 액수를 만들어야하는 DP 문제

1. n-1번 동전까지 고려한 가짓수 정보가 있다면, n번 동전의 가짓수를 구할 수 있다

• 냅색 문제와 비슷하다

2. n-1번 동전까지의 정보가 있다면, X원짜리 n번 동전으로 k원을 만드는 가짓수는

• n번 동전 1개 선택 = n-1번 동전까지로 k-X를 만드는 가짓수
• n번 동전 2개 선택 = n-1번 동전까지로 k-2*X를 만드는 가짓수
• n번 동전 3개 선택 = n-1번 동전까지로 k-3*X를 만드는 가짓수
• ...

3. 첫번째 동전에서부터 1~k원을 만드는 가짓수를 각각 만들어나간다

• dp 테이블에 누적시켜 계산한다
• 예시) 1, 2원짜리로 10원을 만들려고 하면
  • 1원으로 가능한 모든 액수 가짓수는 한가지뿐이다
  • 2원까지 고려하면,
  • dp[2] = dp[2] + dp[2-2] = 1 + 1 =2
  • dp[4] = dp[4] + dp[4-2] = 1 + 2 =3
  • dp[6] = dp[6] + dp[6-2] = 1 + 3 =4
  • dp[8] = dp[8] + dp[8-2] = 1 + 4 =5
  • dp[10] = dp[10] + dp[10-2] = 1 + 5 =6

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int k = pint(st.nextToken());
		int[] coin = new int[n];
		int[] dp = new int [k+1];
		dp[0]=1;
		
		for (int i = 0; i < n; i++) {
			coin[i] = pint(br.readLine());
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = coin[i]; j < k+1; j++) {
				dp[j] += dp[j-coin[i]];
			}
		}
		System.out.println(dp[k]);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 최소한의 갯수로 목표 금액을 맞추는 문제

1. 모든 고액권은 소액권의 n배수로 떨어지므로, 항상 가장 큰 액수부터 선택하는게 유리하다

• 그리디 알고리즘

2. 목표 금액을 초과하지 않는 선에서, 가능한 많은 금액을 고액권부터 채워나간다

3. 목표 금액이 완성되면, 최종 갯수를 출력

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int k = pint(st.nextToken());
		
		int[]money = new int[n];
		for (int i = 0; i < n; i++) {
			money[i]=pint(br.readLine());
		}
		int cnt=0, idx=n-1;
		while(k!=0) {
			cnt+=k/money[idx];
			k%=money[idx--];
		}
		System.out.println(cnt);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 가장 큰 음식물 덩어리의 크기 구하기

• 상하좌우로 연결되 있을 경우 한 덩어리로 본다

1. 음식물의 여부를 boolean 배열로 표현한다

2. 탐색 중 음식물 발견시, dfs 탐색으로 진입한다

• 이미 탐색한 음식물 제거 (현재 위치 false로 변경)
• 상하좌우 4방향 각각으로 음식물이 있으면 진행한다
• 최종적으로 연결된 모든 음식물을 지우고, 그 크기를 반환

3. 모든 음식물 덩어리중 가장 큰 값 유지, 출력

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int k = pint(st.nextToken());
		boolean[][]map = new boolean[n][m];
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			map[pint(st.nextToken())-1][pint(st.nextToken())-1]=true;
		}
		int ans=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j])ans=Math.max(ans, dfs(map,i,j));
			}
		}
		System.out.println(ans);
	}
	
	static int dfs(boolean[][]map, int i, int j) {
		int area=1;
		map[i][j]=false;
		if(i+1<map.length && map[i+1][j])area+=dfs(map,i+1,j);
		if(j+1<map[0].length && map[i][j+1])area+=dfs(map,i,j+1);
		if(i-1>=0 && map[i-1][j])area+=dfs(map,i-1,j);
		if(j-1>=0 && map[i][j-1])area+=dfs(map,i,j-1);
		return area;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}