고양멍멍이

[문제링크]

0. 모든 leaf 노드에 말이 있으며, 한 번에 하나씩 부모로 올리는 게임

• 모든 leaf 노드의 차수의 합에 따라 승/패를 알 수 있다 (짝수면 선공 패배, 홀수면 선공 승리)

1. 시작 노드는 1번으로 고정이므로, BFS를 이용해 모든 노드를 탐색, leaf 여부 및 depth를 저장한다

2. BFS를 진행할 때

• 연결된 노드에 이미 depth 정보가 있다면 : 이미 방문한 노드, 즉 부모 노드이다
• depth 정보가 없다면 : 방문하지 않은 노드, 자식 노드이므로 현재 depth +1을 해당 노드의 depth로 저장한다

3. 탐색이 종료된 후 leaf로 마킹된 노드들을 찾아 depth를 전부 합산, 2의 배수인지에 따라 정답을 출력한다

※ BFS가 아닌 DFS로 진행했다면, leaf 노드 여부/깊이를 따로 저장하지 않고 즉시 판단, 처리 가능하므로 더 편했을것 같다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
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());
		
		int[] depth = new int[N];
		boolean[] isLeaf = new boolean[N];
		ArrayList<LinkedList<Integer>> graph = new ArrayList<>();
		
		for (int i = 0; i < N; i++) {
			graph.add(new LinkedList<>());
			depth[i]=-1;
		}
		
		for (int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a=pint(st.nextToken())-1;
			int b=pint(st.nextToken())-1;
			graph.get(a).add(b);
			graph.get(b).add(a);
		}

		Queue<Integer> qu = new LinkedList<>();
		int curNode=0;
		int curDepth=0;
		
		depth[curNode]=curDepth;
		qu.offer(curNode);
		isLeaf[curNode]=true;
		
		while(!qu.isEmpty()) {
			curNode=qu.poll();
			
			for(int nextNode : graph.get(curNode)) {
				if(depth[nextNode]!=-1)continue;
				
				depth[nextNode]=depth[curNode]+1;
				isLeaf[nextNode]=true;
				isLeaf[curNode]=false;
				qu.offer(nextNode);
			}
		}
		
		
		int ans=0;
		for(int i=0; i<depth.length; i++) {
			if(isLeaf[i])ans+=depth[i];
		}
		
		System.out.println(ans%2==0?"No":"Yes");
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 모든 선생님의 시야(일직선)를 피하도록 장애물을 설치할 수 있는지 묻는 문제

• 맵의 크기가 최대 6*6으로 작고, 선생님의 수도 5 이하로 적으니 brute-force로 해결 가능하다

1. setWall 재귀를 3번 진행하며 가능한 모든 조합으로 벽을 설치한다

2. 3개의 벽이 설치됬다면, 모든 선생님 기준으로 4방향 검사, 학생이 보이는지 검사한다

• 학생의 수(최대 30)에 비해 선생의 수(최대 5)가 적기 때문

3. 단 한 선생님이라도 학생이 보인다면 실패이므로, 결과값을 &로 누적한다

• = 모든 선생님이 학생을 보지 못했을 때만, true를 반환한다

4. 단 한 조합이라도 학생이 보이지 않았다면 성공이니, 결과값을 |로 누적한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
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 = Integer.parseInt(br.readLine());
		int[][]map = new int[N][N];
		List<int[]> teachers = new ArrayList<int[]>(); 
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j < N; j++) {
				map[i][j]=pint(st.nextToken().charAt(0));
				if(map[i][j]==2) {
					teachers.add(new int[] {i,j});
				}
			}
		}
		
		System.out.println(setWall(0, 0, map, teachers)? "YES":"NO");
		
		
	}
	
	static boolean setWall(int level, int cur, int[][]map, List<int[]>teachers) {
		if(level==3) {
			//set 3 wall, verify
			boolean safe = true;
			for(int[] teacher : teachers) {
				// every teacher can't find student == safe
				safe &= !findStudent(map, teacher);
			}
			return safe;
		}
		
		int N = map.length;
		boolean returnV = false;
		for(int idx = cur; idx<N*N; idx++) {
			if(map[idx/N][idx%N] == 0) {
				map[idx/N][idx%N]=3; // set wall
				returnV |= setWall(level+1, cur+1, map, teachers); // recursivly check
				map[idx/N][idx%N]=0; // remove wall
			}
		}
		
		return returnV;
	}
	
	static boolean findStudent(int[][]map, int[]pos) {
		int x=pos[0], y=pos[1]+1;
		while(y<map.length && map[x][y]==0)y++;
		if(y < map.length && map[x][y]==1)return true;
		
		y=pos[1]-1;
		while(y >= 0 && map[x][y]==0)y--;
		if(y >= 0 && map[x][y]==1)return true;
		
		x=pos[0]+1; y=pos[1];
		while(x<map.length && map[x][y]==0)x++;
		if(x < map.length && map[x][y]==1)return true;
		
		x=pos[0]-1;
		while(x >= 0 && map[x][y]==0)x--;
		if(x >= 0 && map[x][y]==1)return true;
		
		return false;
	}
	
	static int pint(Character s) {
		if('S' == s)return 1;
		else if('T' == s)return 2;
		else return 0;
	}
}

[문제링크]

0. 완전 이진 트리를 중위 순회한 결과가 주어졌을때, 원래의 트리를 복원하는 문제

1. 완전 이진 트리의 특성상, 왼쪽 subtree와 오른쪽 subtree의 크기가 동일하다

• 중위 순회는 왼쪽 - 자신 - 오른쪽 순서로 이루어지므로, 정 가운데 번호가 항상 root노드이다

2. 시작-끝 값으로 subtree 정보를 유지하면서, 가운데(root) 정보를 저장하며 재귀를 진행한다

• 재귀의 깊이에 따라 각 list에 저장
• subtree의 크기가 0이되면 종료한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
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());
		int[] node = new int[(int)Math.pow(2, N)-1];
		ArrayList<LinkedList<Integer>> list = new ArrayList<>();
		for(int i=0; i<N; i++) {
			list.add(new LinkedList<>());
		}
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < node.length; i++) {
			node[i]=pint(st.nextToken());
		}
		
		rec(list, node, 0, node.length, 0);
		
		for(int i=0; i<N; i++) {
			for(Integer e : list.get(i)) {
				System.out.print(e+" ");
			}System.out.println();
		}
	}
	
	static void rec(ArrayList<LinkedList<Integer>> list, int[] node, 
			int fst, int lst, int depth) {
		
		if(fst==lst)return;
		int mid = (fst+lst)/2;
		
		list.get(depth).add(node[mid]);
		
		rec(list, node, fst, mid, depth+1);//left
		rec(list, node, mid+1, lst, depth+1);//right
	}
	
	
	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);
	}
}

[문제링크]

0. 아이의 위치를 최소한으로 바꾸면서 순서를 정렬하는 방법 = 이미 정렬된 가장 긴 문자열을 찾고, 그 나머지를 이동하면 된다

• 가장 긴 증가하는 부분 수열(LIS)을 구하면 된다

1. DP를 통해 이전까지 진행한 결과들 중 현재 순서보다 작으면서 그 값이 제일 큰 값을 구한다

2. 해당 값 +1이 현재 지점까지의 LIS이다

3. LIS를 마지막까지 구한 후, 가장 큰 LIS 길이를 구한다

4. 해당 LIS에 속하지 않는 아이들을 이동하면 된다. 즉, (전체 아이 수 - LIS길이) = (이동해야하는 아이 수)

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));
		
		int N = pint(br.readLine());
		int[] num = new int[N];
		int[] dp = new int[N];
		for (int i = 0; i < N; i++) {
			num[i]=pint(br.readLine());
		}
		int lis=0;
		for (int i = 0; i < N; i++) {
			int max=0;
			for (int j = 0; j < i; j++) {
				if(num[j] < num[i]  && max<dp[j])max=dp[j];
			}
			dp[i]=max+1;
			lis = Math.max(dp[i], lis);
		}
		System.out.println(N-lis);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}