고양멍멍이

[문제링크]

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. 동전으로 특정 액수를 만들어야하는 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. Cycle을 탐색하는 DFS문제

1. 여러 칸들을 선택했을때, index와 내용이 같으려면 해당 칸들 사이에 cycle이 발생해야한다

• ex. (1,3), (3,5), (5,1)이 있다면, 1->3->5->1로 cycle이 발생하게 된다
• ex2. (2,1), (1,3), (3,5), (5,1)의 경우, 2->1->3->5->1로 2가 누락되니 cycle이 아니다

2. 각 칸별로 DFS를 돌며 자기 자신으로 돌아올 수 있는지, 즉 cycle 발생 여부를 탐색한다

• 발생까지 거친 node들은 전부 Queue에 저장한다

3. Cycle이 발생했다면, 해당 node들은 cycle에 속한다는 의미로 방문 처리해 DFS 재탐색을 막는다

• 또한 오름차순으로 정렬되도록 PriorityQueue를 사용해 저장한다

4. 모든 node에 대한 DFS 탐색이 종료되었다면, PQ의 size와 그 원소를 차례대로 출력한다

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

public class Main{
	static int[] num;
	static boolean[] isVisit;
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//dfs, 사이클 생성 탐색
		
		int N = pint(br.readLine());
		num = new int[N+1];
		boolean[] isPartOfCycle = new boolean[N+1];
		
		for (int i = 1; i <= N; i++) {
			num[i]=pint(br.readLine());
		}
		
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		Queue<Integer>qu = new LinkedList<>();
	
		for(int i=1; i<=N; i++) {
			if(isPartOfCycle[i])continue;
			
			isVisit = new boolean[N+1];
			//do search
			if(dfs(i,i, qu)) {
				for(Integer element : qu) {
					pq.offer(element);
					isPartOfCycle[element]=true;
				}
			}
			qu.clear();
		}
		
		System.out.println(pq.size());
		while(!pq.isEmpty())System.out.println(pq.poll());
	}
	
	static boolean dfs(int fst, int cur, Queue<Integer>qu) {
		
		if(cur==fst && isVisit[cur])return true;
		if(isVisit[cur])return false;
		qu.offer(cur);
		isVisit[cur]=true;
		return dfs(fst, num[cur], qu);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 가능한 적은 누적 숫자로 목표 지점에 도달하는 문제. BFS

1. 기본적인 큐를 이용한 BFS를 진행한다

2. cache 배열을 관리해, 어떠한 지점에 도달한 숫자의 최솟값을 저장한다

• 더 큰 숫자로 해당 지점에 도달한 경우, 더 이상 진행할 가치가 없다는 뜻. 소거한다
• cache 배열 초깃값은 문제 조건상 최댓값이 125*125*9 = 대략 14만이니, 그보다 큰 수 아무거나 입력한다

3. 어떤 지점에 같은 시점에 도달했을 경우, cache 배열이 여러번 갱신되며 큐에 같은 지점이 중복 삽입된다

• isCached boolean 배열을 관리해, 중복 삽입을 막는다
• Queue 기능을 하면서 Set인게 있나..? 있으면 좋을것같다

4. 모든 탐색이 끝난 후, 목표 지점인 [N][N] (배열 인덱스로는 [N-1][N-1]) 지점의 cache 값이 정답

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

public class Main{
	static int[][] dir = {
		{1,0},{0,1},{-1,0},{0,-1}
	};
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int probCnt=1;
		while(true) {
			int N = pint(br.readLine());
			if(N==0)break;
            
			int[][]map = new int[N][N];
			int[][]cache = new int[N][N];
			boolean[][]isCached = new boolean[N][N];
			
			for (int i = 0; i < N; i++) {
				Arrays.fill(cache[i], 100000000);
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j]=pint(st.nextToken());
				}
			}
			
			Queue<int[]> qu = new LinkedList<int[]>();
			qu.offer(new int[] {0,0});
			isCached[0][0]=true;
			cache[0][0]=map[0][0];
			
			while(!qu.isEmpty()) {
				int[] cur = qu.poll();
				isCached[cur[0]][cur[1]]=false;
				
				for(int d=0; d<4; d++) {
					int nx = cur[0]+dir[d][0];
					int ny = cur[1]+dir[d][1];
					
					if(nx<0||nx>=N||ny<0||ny>=N)continue;
					
					if(cache[nx][ny] > map[nx][ny]+cache[cur[0]][cur[1]]) {
						cache[nx][ny] = map[nx][ny]+cache[cur[0]][cur[1]];
						if(!isCached[nx][ny]) {
							isCached[nx][ny]=true;
							qu.offer(new int[] {nx,ny});
						}
					}
				}
			}
			sb.append("Problem ").append(probCnt++).append(": ").append(cache[N-1][N-1]).append("\n");
			
		}
		System.out.println(sb);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 수학, 기하학 문제

1. P1, P2, P3를 이은 선이 시계방향인지 아닌지 알려면 P1-P2, P1-P3선의 기울기를 비교하면 된다

• 위 그림과 같이, 1-2-3처럼 반시계방향일때는 1-2보다 1-3의 기울기가 크고,
• 반대로 1-2-3'처럼 시계방향일때는 1-2보다 1-3이 작다

2. 두 점으로부터 기울기는 간단하게 (y2-y1)/ (x2-x1) 로 얻을 수 있다

• 하지만 나누기 연산으로 정확도 문제가 발생하게 된다

3. 필요한것은 두 기울기의 비교이지 정확한 값이 아니므로, 양 측에 (x2-x1) * (x3-x1)을 곱해줘서 정수로 비교한다

• (y2-y1) / (x2-x1) ○ (y3-y1) / (x3-x1) 에서
• (y2-y1) * (x3-x1) ○ (y3-y1) * (x2-x1) 으로

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 x1 = pint(st.nextToken());
		int y1 = pint(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int x2 = pint(st.nextToken());
		int y2 = pint(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int x3 = pint(st.nextToken());
		int y3 = pint(st.nextToken());
		
		int line1 = (y3-y1)*(x2-x1); // 1-3
		int line2 = (y2-y1)*(x3-x1); // 1-2
		if(line1 == line2)System.out.println(0);
		else if(line1 > line2)System.out.println(1);
		else System.out.println(-1);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 두 포인터 문제

1. 두 포인터 사용을 위해 전체 입력값을 정렬해준다

• Arrays.sort는 최악 N제곱으로 나오는 함수이므로, Collections.sort를 이용했다

2. 양 끝 값을 초기 포인터로, 두 값의 차이를 초기 합(min)로 지정한다

3. 현재 포인터가 가리키는 용액의 합이 현재 min보다 작다면, 새로운 min으로 지정하고 포인터를 저장한다

4. 현재 포인터 용액의 합이 양수라면 + 용액이 약해져야하고, 음수라면 - 용액이 약해져야한다

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		ArrayList<Integer> num = new ArrayList<>(N);
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			num.add(pint(st.nextToken()));
		}
		
		Collections.sort(num);
		
		int fst=0, snd=N-1;
		int min = Math.abs( num.get(fst)+num.get(snd) );
		int minMinus=num.get(fst), minPlus=num.get(snd);
		
		while(fst<snd) {
			int cur = num.get(fst)+num.get(snd);
			if(Math.abs(cur)<min) {
				min = Math.abs(cur);
				minMinus=num.get(fst); minPlus=num.get(snd);
			}
			
			if(cur<0) {
				fst++;//- 용액 약화
			}
			else {
				snd--;//+ 용액 약화
			}
		}
		System.out.println(minMinus+" "+minPlus);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}