zzanzu/acmicpc

앨-고-리-듬-🔑

개발 블로그(medium)

acmicpc's Issues

여름엔 식중독...

조심합시다.

3649번 / 로봇 프로젝트 / Greedy

• 이 문제는 시간 초과나 런타임 에러를 어떻게 줄이느냐가 관건이다

• 일단은 막대기 배열을 오름차순으로 정렬해주고,

• 맨 처음으로 생각할 수 있는 방법은,

1. 맨 왼쪽을 고정시켰다고 생각하고 오른쪽에서 점점 왼쪽으로 이동시키며 합을 구해본다
2. 그래도 없다면 맨 왼쪽 인덱스를 1 증가시켜서 1번 과정으로 돌아간다.

강사님의 심플한 대답(고수는 간결하다)

while(start < end) {
    int sum = length[start] + length[end];
    
    if(length > N) {
        end--:
    } else if(length < N) {
        start++;
    } else {
        find = true;
        break;
    }
}

if(find == true) {
    sysout(yes ~~);
else {
    sysout("danger");
}

2621번 / 카드 게임 / 카운팅 기법

카드의 색깔과 숫자를 보고 5장의 카드의 색깔과 숫자의 특징들을 가지고 문제를 풀게 된다.
따라서 카드의 색깔과 숫자의 특징들을 저장하는 배열을 각각 만들고, 각 인덱스는 출현 횟수를 세게 된다.

이런 방식으로 카드의 색깔(color)와 숫자(num)에 대한 각 횟수를 카운트한 배열을 만든다.

List, 배열 내부의 객체를 정렬하기

객체 배열 정렬하기

• Comparable : 비교할 수 있게 해주는 놈, 클래스 정의를 할 때 implement하고 만들어준다.

        Employee[] data = new Employee[5];
		
	data[0] = new Employee(1,2);
	data[1] = new Employee(5,4);
	data[2] = new Employee(4,5);
	data[3] = new Employee(3,3);
	data[4] = new Employee(2,1);
    
        ...
        Arrays.sort(data); 
}

class Employee implements Comparable<Employee> { // 'Employee는 Employee와 비교 가능하다'의 의미
	int rank1;
	int rank2;
	
	public Employee(int rank1, int rank2) {
		this.rank1 = rank1;
		this.rank2 = rank2;
	}

	@Override
	public String toString() {
		return "Employee [rank1=" + rank1 + ", rank2=" + rank2 + "]";
	}

	@Override
	public int compareTo(Employee arg0) {
		// this - 나 자신 , arg0 - 비교 대상
		return Integer.compare(this.rank1, arg0.rank1); // 나 자신(this)와 다른 것(arg0)을 비교한다
	}
	
	
}

• Comparator : 비교해주는 놈

Arrays.sort(data, new Comparator<Employee>() {
	@Override
	public int compare(Employee arg0, Employee arg1) {
		return Integer.compare(arg0.rank1, arg1.rank1);
	}
});

or
// comparator를 매번 생성하기 번거로우니까 미리 만들어놓고 쓰기
Comparator<Employee> cc =  new Comparator<Employee>() {
	@Override
	public int compare(Employee arg0, Employee arg1) {
		return Integer.compare(arg0.rank1, arg1.rank1);
	}
};

Arrays.sort(data, cc);

class Employee {
	int rank1;
	int rank2;
	
	public Employee(int rank1, int rank2) {
		this.rank1 = rank1;
		this.rank2 = rank2;
	}

	@Override
	public String toString() {
		return "Employee [rank1=" + rank1 + ", rank2=" + rank2 + "]";
	}
	
	
}

리스트 정렬하기

public class SortingTest {

	public static void main(String[] args) {
		Employee[] data = new Employee[5];
		
		data[0] = new Employee(1,2);
		data[1] = new Employee(5,4);
		data[2] = new Employee(4,5);
		data[3] = new Employee(3,3);
		data[4] = new Employee(2,1);
		
		System.out.println(Arrays.toString(data));
		
		Comparator<Employee> cc =  new Comparator<Employee>() {
			@Override
			public int compare(Employee arg0, Employee arg1) {
				return Integer.compare(arg0.rank1, arg1.rank1);
			}
		};
		
		ArrayList<Employee> list = new ArrayList<>();
		for(int i = 0; i < data.length; i++) {
			list.add(data[i]);
		}
		
		System.out.println(data);
		list.sort(cc);
	}

}

class Employee {
	int rank1;
	int rank2;
	
	public Employee(int rank1, int rank2) {
		this.rank1 = rank1;
		this.rank2 = rank2;
	}

	@Override
	public String toString() {
		return "Employee [rank1=" + rank1 + ", rank2=" + rank2 + "]";
	}
	
	
}

• 리스트 관련된 함수들은 Collections.~~~
• 배열 관련된 함수들은 Arrays.~~~

1987번 / 알파벳 / 백트래킹

• 오늘은 백트래킹 방법에 대해서 배웠다. DFS하는 거랑 방법이 비슷한데, 기존의 DFS는

DFS

1. 방문 체크
2. 연결된 길 찾기
3. 갈 수 있는 길 찾기
4. 간다

라고 한다면,

백트래킹

백트래킹은 처음과 마지막에 단계가 추가되었다.

0. 방문 종료 조건 체크
1. 방문 체크
2. 연결된 길 찾기
3. 갈 수 있는 길 찾기
4. 간다
5. 방문 체크 해제

• 방문 종료 조건은 문제마다 다르기 때문에 이거를 잘 고려한 파라미터들을 생각해내야한다
• 5번 방문 체크 해제는 for문이 끝나고(연결된 길들 모두 검색 후) 실행되어져야한다!

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Problem1987 {
	static Set<Integer> set;
	static int R, C;
	static int[][] map;
	
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		set = new HashSet<>();
		
		R = sc.nextInt();
		C = sc.nextInt();
		
		map = new int[R][C];
		
		for(int i = 0; i < R; i++) {
			String temp = sc.next();
			
			for(int j = 0 ; j < C; j++) {
				map[i][j] = temp.charAt(j);
			}
		}
		
		set.add(map[0][0]);
		dfs(0, 0, 1);
		
		System.out.println(max);
		
	}
	
	static void dfs(int x, int y, int count) {
		// 0. 종료 체크
		if(count > max) {
			max = count;
		}
		
		// 1. 방문 체크
		set.add(map[y][x]);
		// 2. 연결된 길 체크
		for(int i = 0; i < 4; i++) {
			int targetX = x + dx[i];
			int targetY = y + dy[i];
			
			// 3. 갈 수 있는 길 체크
			if(targetX >= 0 && targetX < C && targetY >= 0 && targetY < R) {
				if(!set.contains(map[targetY][targetX])) {
					// 4. 간다
					dfs(targetX, targetY, count+1);
				}
			}
		}
		// 5. 방문 체크 해제
		set.remove(map[y][x]);
	}

}

원래대로라면 visited 배열을 선언해서 탐색한 알파벳을 표시해주고
종료 여부를 체크하기위해 이걸 보고 매번 체크했을 것이다.

하지만 강사님께서 Set라는 자료구조를 소개해주셨고,
이것의 특징은 자료를 저장할 때(add) 중복을 허락하지 않고 저장하기 때문에
이 문제에 적합하다고 하셨다. 특히 contains()함수를 통해 set에 내가 탐색하는 알파벳이
기존에 저장되었는지(탐색하였는지) 확인하기 쉽기 때문에 코드를 구현하기 더 간단해졌다.

Set<Integer> set = new HashSet<>();

set.add(추가할 데이터);

set.contains(찾고자하는 데이터); // 있는지 없는지 체크

set.remove(지우고자하는 데이터);

분발하세요!

앨-고-리-듬-화-이-팅

1759번 / 암호 만들기 / 백트래킹

• 백트래킹
• 탐색을 종료하고 바로 이전 분기로 돌아가는 타이밍에 방문 체크를 해지해야한다! ( == for문 종료 시점)

package example04;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Problem1759 {
	static int L, C;
	static Character[] data;
	static boolean[] visited;
	static LinkedList<String> result;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		L = sc.nextInt();
		C = sc.nextInt();

		data = new Character[C];
		visited = new boolean[C];

		for (int i = 0; i < C; i++) {
			String temp = sc.next();
			data[i] = temp.charAt(0);
		}
		
		Arrays.sort(data);
		result = new LinkedList<String>();

		for (int i = 0; i < data.length - 3; i++) {
			if (isVow(data[i])) {
				Password pwd = new Password(data[i], 1, 0, 1, "" + data[i]);
				dfs(pwd);
			} else {
				Password pwd = new Password(data[i], 1, 1, 0, "" + data[i]);
				dfs(pwd);
			}
		}
		
		for(String r : result) {
			System.out.println(r);
		}
		
	}

	public static void dfs(Password pwd) {
		Password currentPwd = pwd;

		// 0. 종료 조건 체크
		if (currentPwd.depth == L) { // 이부분을 4로 했었네;;
			if (currentPwd.con >= 2 && currentPwd.vow >= 1) {
				// 결과 저장
				result.add(currentPwd.pwd);
			}
		}

		// 1. 방문 체크
		visited[check(currentPwd.current)] = true;

		// 2. 연결된 길
		for (int i = check(currentPwd.current); i < data.length; i++) {
			// 3. 갈 수 있는 길
			if (visited[i] == false) {
				// 4. 간다.
				if (isVow(data[i])) {
					Password nextPwd = new Password(data[i], currentPwd.depth + 1, 
							currentPwd.con, currentPwd.vow + 1, currentPwd.pwd + data[i]);

					dfs(nextPwd);
				} else {
					Password nextPwd = new Password(data[i], currentPwd.depth + 1,
							currentPwd.con + 1, currentPwd.vow, currentPwd.pwd + data[i]);

					dfs(nextPwd);

				}
			}
		}
                // 백트래킹!
		visited[check(currentPwd.current)] = false;

	}

	// data 배열내에서 해당 문자의 index를 리턴한다.
	public static int check(char c) {
		for (int i = 0; i < data.length; i++) {
			if (c == data[i]) {
				return i;
			}
		}
		return -1;
	}

	// 모음 체크
	public static boolean isVow(char c) {
		if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
			return true;
		}

		return false;
	}

}

class Password {
	char current;
	int depth;
	int con; // 자음
	int vow; // 모음
	String pwd;

	public Password(char current, int depth, int con, int vow, String pwd) {
		this.current = current;
		this.depth = depth;
		this.con = con;
		this.vow = vow;
		this.pwd = pwd;
	}

	@Override
	public String toString() {
		return "Password [current=" + current + ", depth=" + depth + ", con=" + con + ", vow=" + vow + ", pwd=" + pwd
				+ "]";
	}

}

11403번 / 경로찾기 / BFS

public class Problem11403 {
	static int N;
	static int[][] map;
	static int[][] result;
	static boolean[] visited;
	static Queue<Integer> queue;
	static boolean[] isExist;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		map = new int[N+1][N+1];
		result = new int[N][N];
		visited = new boolean[N+1];
		queue = new LinkedList<>();
		isExist = new boolean[N+1];
		
		for(int y = 1; y <= N; y++) {
			
			for(int x = 1; x <= N; x++) {
				map[y][x] = sc.nextInt();
				
				if(map[y][x] == 1) isExist[y] = true;
			}
		}
		
		for(int y = 1; y <= N; y++) {
			visited = new boolean[N+1];
			
			if(isExist[y] == true) {
                                  // 0. 큐에다가 시작 지점 넣어주기
				queue.add(y);
                                  // 0. 시작 지점 방문 체크하기
//				visited[y] = true; // 방문체크하는 타이밍이 관건이군
				
				while(queue.isEmpty() == false) {
                                          // 1. 큐에서 꺼내오기
					int current = queue.poll();
				        // 2. 연결된 길 찾기
					for(int i = 1; i <= N; i++) {
                                                   // 3. 갈 수 있는 길 찾기
						if(map[current][i] == 1 && visited[i] == false) {
                                                            // 4. 큐에 넣기
							queue.add(i);
							visited[i] = true; // 여기서 방문체크!
							result[y-1][i-1] = 1;
						}
					}
				}
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print(result[i][j] + " ");
			}
			System.out.println();
		}
		
		
	}

}

2178번 / 미로 탐색 / DFS

https://www.acmicpc.net/problem/2178

우선은 DFS로 풀어봄.

	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
...
		// 2. 연결된 길을 찾는다.(상하좌우, 4가지) dx, dy를 사용하는 것에 집중!
		for(int i = 0; i < 4; i++) {
			int targetX = x + dx[i];
			int targetY = y + dy[i];
			

• 한 위치에서 상,하,좌,우를 탐색하기 위해 현재 위치 (x, y)에 미리 정의한 탐색 좌표 이동거리 dx, dy를 정의해서 for문안에서 탐색

• 채점 상으로는 시간 초과

기존 코드

package example02;

import java.util.Arrays;
import java.util.Scanner;

public class Problem2178 {
	static int N, M;
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		sc.nextLine();
		
		// 그래프의 노드의 번호가 1,2,3 이런게 아니라서 그냥 N,M 써줌
		map = new int[N][M];
		visited = new boolean[N][M];
		
		// 여기서 int로 String의 한 글자를 받아보는 방식 ㅇㅇ
		for(int y = 0; y < N; y++) {
			String temp = sc.nextLine();
			
			for(int x = 0; x < M; x++) {
				if(temp.charAt(x) == '1') {
					map[y][x] = 1;
				} else {
					map[y][x] = 0;
				}
			}
		}
		
		dfs(0, 0, 1);
		System.out.println(min);
	}
	
	public static void dfs(int x, int y, int current) {
		// 0. 목적지 도달 여부 체크 , 이 부분을 생각 못함!
		if(y == N-1 && x == M-1) {
			if(current < min) {
				min = current;
			}
			return; // 쓸데없는 길 탐색 안하게 해줌
		}
		// 1. 방문 기록을 남긴다.
		visited[y][x] = true;
		
		// 2. 연결된 길을 찾는다.(상하좌우, 4가지) dx, dy를 사용하는 것에 집중!
		for(int i = 0; i < 4; i++) {
			int targetX = x + dx[i];
			int targetY = y + dy[i];
			
			if(targetX >= 0 && targetX < M && targetY >= 0 && targetY < N) {
				// 3. 갈 수 있는 길을 찾는다.
				if(map[targetY][targetX] == 1 && visited[targetY][targetX] == false){
					// 4. 간다
					dfs(targetX, targetY, current+1);
				}				
			}
		}
		// 5. 방문 해지
		visited[y][x] = false;
	}

}

근데 여기서 visited를 int형으로 바꿔서 각 칸이 방문이 되었을 때 거기를 지나간 당시의 거리(current)를 저장하게 된다. 그러면 다음번에 그 칸을 지나가게 되었을 때의 current와 visited(이전의 방문시 거리)를 비교한다.

public static void dfs(int x, int y, int current) {
		// 0. 목적지 도달 여부 체크 , 이 부분을 생각 못함!
		if(y == N-1 && x == M-1) {
			if(current < min) {
				min = current;
			}
			return; // 쓸데없는 길 탐색 안하게 해줌
		}
		// 1. 방문 기록을 남긴다.
		visited[y][x] = current;
		
		// 2. 연결된 길을 찾는다.(상하좌우, 4가지) dx, dy를 사용하는 것에 집중!
		for(int i = 0; i < 4; i++) {
			int targetX = x + dx[i];
			int targetY = y + dy[i];
			
			if(targetX >= 0 && targetX < M && targetY >= 0 && targetY < N) {
				// 3. 갈 수 있는 길을 찾는다.
				if(map[targetY][targetX] == 1){
					if(visited[targetY][targetX] == 0 || visited[targetY][targetX] > current+1)
					// 4. 간다
					dfs(targetX, targetY, current+1);
				}				
			}
		}
		// 5. 방문 해지
//		visited[y][x] = 0;
	}

• '1. 방문 기록을 남긴다' 단계에서 방문 여부를 저장하는 것이 아니라, 해당 위치까지의 거리를 저장한다
  그렇게 되면 다음번에 해당 위치를 다시 한 번 방문하게 되었을 때, 이 값(visited)을 current와 비교하여 탐색을 더 할지 결정하게 된다.

• 방문 해지는 하지 않는다!

10953번 / 입출력 / 콤마( , ) 입력받기

언제 배열을 쓸지, List를 쓸지, Queue를 써야할까?

ArrayList?
LinkedList?
Queue?

각각의 특징, 사용법에 대해 공부해보자

7576번 / 토마토 / BFS

• 시간초과 코드

package example03;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Problem7576 {
	static int N, M;
	static int[][] visited; // 익은 시기의 시간
	static int[][] map;
	static Queue<Position3> queue;
	
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		M = sc.nextInt();
		N = sc.nextInt();
		map = new int[N][M];
		visited = new int[N][M];
		queue = new LinkedList<>();
		
		for(int y = 0 ; y < N; y++) {
			for(int x = 0; x < M; x++) {
				map[y][x] = sc.nextInt();
			}
		}
		
		// 썩은토마토가 있는 위치 큐에 저장
		for(int y = 0 ; y < N; y++) {
			for(int x = 0; x < M; x++) {
				if(map[y][x] == 1) {
					Position3 pos = new Position3(x, y, 1);
					visited[y][x] = 1;
					queue.add(pos);
				}
			}
		}
		
		while(queue.isEmpty() == false) {
			Position3 currentPos = queue.poll();
			visited[currentPos.y][currentPos.x] = currentPos.time;
			
			if(max < currentPos.time) {
				max = currentPos.time;
			}
			
			for(int i = 0; i < 4; i++) {
				int targetX = currentPos.x + dx[i];
				int targetY = currentPos.y + dy[i];
				
				if(targetX >= 0 && targetX < M && targetY >= 0 && targetY < N) {
					if(map[targetY][targetX] != -1 && map[targetY][targetX] == 0) {
						if(visited[targetY][targetX] == 0) {
							Position3 nextPos = new Position3(targetX, targetY, currentPos.time + 1);
							queue.add(nextPos);
						}
					}
				}
			}
			
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(visited[i][j] == 0 && map[i][j] == 0) {
					System.out.println(-1);
					return;
				}
			}
		}
		
		System.out.println(max-1);
		
		
	}

}

class Position3 {
	int y;
	int x;
	int time;
	
	public Position3(int x, int y, int time) {
		this.y = y;
		this.x = x;
		this.time = time;
	}
}

• 해결한 코드의 수정 부분

while(queue.isEmpty() == false) {
	Position3 currentPos = queue.poll();
			
	if(max < currentPos.time) {
		max = currentPos.time;
	}
			
	for(int i = 0; i < 4; i++) {
		int targetX = currentPos.x + dx[i];
		int targetY = currentPos.y + dy[i];
		
		if(targetX >= 0 && targetX < M && targetY >= 0 && targetY < N) {
			if(map[targetY][targetX] != -1 && map[targetY][targetX] == 0) {
				if(visited[targetY][targetX] == 0) {
					Position3 nextPos = new Position3(targetX, targetY, currentPos.time + 1);
					queue.add(nextPos);
					
					visited[targetY][targetX] = currentPos.time+1;
				}
			}
		}
	}
			
}

• 원인은 BFS를 본격적으로 실행하는 while문에 있었다.
• 여기서 visited는 해당 위치의 토마토가 썩은 순간의 시간을 저장하게 되는데, 이것을 큐에 저장(queue.add)하는 순간에 저장할 것인지, 아니면 while문이 시작되는 순간에 currentPos의 time변수에 접근하여 변화시켜줄 것인지가 관건이었다.

11724번 / 연결 요소의 개수 / BFS

package bfs;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Problem11724 {
	static int N, M;
	static boolean[][] map;
	static boolean[] visited;
	static boolean[] check;
	static Queue<Integer> queue;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		map = new boolean[N+1][N+1];
		visited = new boolean[N+1];
		check = new boolean[N+1];
		queue = new LinkedList<>();
		
		for(int i = 0; i < M; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			
			map[u][v] = true;
			map[v][u] = true;
			check[u] = true;
			check[v] = true;
		}
		
		int count = 0;
		for(int i = 1; i <= N; i++) {
			if(check[i] == true && visited[i] == false) {
				// 0. 큐에다가 시작 지점 넣어주
				queue.add(i);
				// 0. 시작지점 방문 기록 남기
				visited[i] = true;
				
				while(queue.isEmpty() == false) {
					// 1. 큐에서 꺼내오기
					int current = queue.poll();
					
					// 2. 연결된 길들 찾기
					for(int j = 1; j <= N; j++) {
						// 3. 갈 수 있는 길 찾기
						if(map[current][j] == true && visited[j] == false) {
							// 4. 큐에 넣기(갈 수 있는 곳)
							queue.add(j);
							// 5. 방문 체크(갈 수 있는 곳)
							visited[j] = true;
						}
					}
				}
				count++;
			} else if(check[i] == false) {
				count++;
			}
		}
		
		System.out.println(count);
	}

}

• 기본적인 BFS 문제
• DFS로도 풀 수 있을듯
• else if 부분을 생각 못해서 2번 틀림 : 아무 간선도 연결 안된 경우에도 count를 증가시켜줘야된다.

• else if 부분이 없다면 2를 출력하게된다. 따라서 check[]가 false인 부분은 아무 간선도 연결이 안된 노드이므로 이것을 체크해서 count를 증가시켜주면 된다.

근데 너무 복잡하게 짰다...

[공지] 이찬주 DFS특강 1학점 신청 (~8/9)

많은 신청 바랍니다.

1205번

배열.indexOf( )
배열.lastIndexOf( ) 사용하기