개요
이번엔 진짜로 합격해야한다..는 굳건한 마음으로 지금까지 공부해왔던 내용들을 정리하는 글을 작성해보고자 한다.
정리가 필요한 내용을 꼽아보자면 다음과 같다.
1.템플릿처럼 내 머릿속에 저장해야하는 코드들 정리하기
(BFS,DFS,Union Find,최소신장트리,조합관련 코드)
2.지금까지 공부해온 내용들 정리
(핵심은 지금까지 풀어온 문제들 중 이후 활용할 수 있을만한 스킬들을 정리하는 것)
두가지 모두 필자의 개인적인 견해가 듬뿍 담겨있으니 참고만 하시라.
템플릿 코드
BFS & DFS
DFS
깊이 우선 탐색은 하나의 노드가 연결되어있다면 해당 노드를 계속 파고드는 것이다.
그림을 보면,방문하려는 노드가 맨 마지막이거나, 이미 방문했다면 return되어 돌아오는 것을 볼 수 있다.
return 되어 돌아오게 되면,인접리스트에서 다른노드를 방문한다.
이와 같은 행동을 반복한다
BFS
너비 우선 탐색은 현재 노드와 연결된 모든 노드들을 큐에 저장해나가는 방식이다.
즉, 하나의 depth에 있는 모든 노드가 자기랑 연결된 리프노드를 큐에 저장해나가며 놓치는 노드 없이 모두 탐색해나가는 방법이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* @author onyoo
* @performance
* @category
* @note
* @see
* @since 2023/11/14
**/
public class bfs와dfs {
static int N,M,V;
static ArrayList<Integer>[] list;
static boolean[] visited;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
V = Integer.parseInt(st.nextToken());
list = new ArrayList[N+1];
for(int i=0;i<N+1;i++) list[i] = new ArrayList<>();
for(int m=0;m<M;m++){
st = new StringTokenizer(br.readLine()," ");
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
list[start].add(end);
list[end].add(start);
}
for(int i=0;i<N+1;i++) Collections.sort(list[i]);
visited = new boolean[N+1];
dfs(V);
sb.append("\n");
visited = new boolean[N+1];
bfs(V);
System.out.println(sb);
}
static void dfs(int start){
sb.append(start+" ");
visited[start] = true;
for(int value : list[start]){
if(visited[value]) continue;
visited[value] = true;
dfs(value);
}
}
static void bfs(int start){
Queue<Integer> que = new ArrayDeque<>();
que.add(start);
visited[start] = true;
while(!que.isEmpty()){
int curr = que.poll();
sb.append(curr + " ");
for(int value : list[curr]){
if(visited[value]) continue; // 방문여부
visited[value] = true;
que.add(value);
}
}
}
}
조합
중복없는 조합은 중복되는 원소 없이 정해진 갯수를 뽑는 것을 말한다.
조합이니 만큼 순서가 달라도 똑같은 경우의 수라는 것을 명심하자.
다른 수를 뽑아나가기 위해서 시작지점을 계속 변화시켜주는 것이 필요하다.
시작 지점을 하나씩 올려가면서,원하는 개수만큼을 뽑아나가며 원하는 걸 다 뽑으면 재귀식을 종료하자.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* @see
* @since 2023/11/14
**/
public class N과M {
static int N,M;
static int[] selected,number;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken()); //1~N 까지의 자연수
M = Integer.parseInt(st.nextToken()); //수열의 길이
st = new StringTokenizer(br.readLine()," ");
number = new int[N];
selected = new int[M];
for(int n=0;n<N;n++){
number[n] = Integer.parseInt(st.nextToken());
}
Arrays.sort(number);
dfs(0,0,new boolean[N]);
System.out.print(sb);
}
static void dfs(int start,int depth,boolean[] visited){
if(depth == M){
for(int m=0;m<M;m++){
sb.append(selected[m] + " ");
}
sb.append("\n");
return;
}
for(int i=start;i<number.length;i++){
if(visited[i]) continue;
selected[depth] = number[i];
visited[i] = true;
dfs(i+1,depth+1,visited);
visited[i] = false;
}
}
}중복조합
중복조합은 원소가 중복되어도 괜찮다는 소리이다.
아래의 문제의 경우, 1,2 두가지의 경우가 있고. 여기에서 마을의 개수만큼 뽑아야한다.
이럴 경우, 1을 선택할 경우 2를 선택할 경우 두가지만 필요하기 때문에
1 선택, 2 선택으로 코드를 구성했다.
arr[depth] = 1;
dfs(depth+1,arr); // 선거구 1
arr[depth] = 2;
dfs(depth+1,arr); // 선거구 2똑같은 depth지만, 두개 모두 선택할 수 있다.
왜냐하면 중복이 허용되는 중복 조합이기 때문이다.
import javax.swing.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* @see
* @since 2023/11/14
**/
public class 게리맨더링 {
static int N,min;
static int[] people;
static ArrayList<Integer>[] list;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
min = Integer.MAX_VALUE;
people = new int[N+1];
st = new StringTokenizer(br.readLine()," ");
for(int n = 1 ; n < N + 1 ; n++){
people[n] = Integer.parseInt(st.nextToken());
}
list = new ArrayList[N+1];
for(int n=0;n<N+1;n++) list[n] = new ArrayList<>();
for(int n = 1 ; n < N + 1 ; n++){
st = new StringTokenizer(br.readLine()," ");
int cnt = Integer.parseInt(st.nextToken());
for(int c=0;c<cnt;c++) list[n].add(Integer.valueOf(st.nextToken()));
}
dfs(1,new int[N+1]);
System.out.println(min == Integer.MAX_VALUE ? -1 : min);
}
static void dfs(int depth,int[] arr){
if(depth == arr.length){
int gu1 = 0;
int gu2 = 0;
for(int i=1;i<arr.length;i++){
if(arr[i] == 1) gu1 += people[i];
else gu2 += people[i];
}
if(gu1 == 0 || gu2 == 0) return;
//하나로 치우쳐진 선거구는 out
if(Math.abs(gu1-gu2) >= min) return;
// 최솟값이 아니라면 보지도 않는다
visited = new boolean[N+1];
int cnt = 0;
for(int i=1;i<list.length;i++){
if(visited[i]) continue;
cnt += bfs(i,arr);
}
if(cnt != 2) return;
min = Math.min(min,Math.abs(gu1-gu2));
return;
}
//여기가 중복조합
arr[depth] = 1;
dfs(depth+1,arr); // 선거구 1
arr[depth] = 2;
dfs(depth+1,arr); // 선거구 2
}
static int bfs(int start,int[] type){
Queue<Integer> que = new ArrayDeque<>();
que.add(start);
visited[start] = true;
int t = type[start];
while(!que.isEmpty()){
int curr = que.poll();
for(int value : list[curr]){
if(visited[value] || type[value] != t) continue;
visited[value] = true;
que.add(value);
}
}
return 1; // 무사히 빠져나오면 1을 리턴
}
}순열
순열의 경우 순서가 보장되어있다는 점이 다르다.
순열의 방문여부를 확인하여, 중복되지 않는지 체크하고 1 3 과 3 1 은 다르기 때문에 다른 처리를 할 필요가 없다 그대로 뽑아주면 된다
(순열의 경우,이전 숫자보다 큰 숫자가 나오도록 조절하여 1 3 이 나온 히구 3 1 나오지는 않도록 한다)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* @see
* @since 2023/11/14
**/
public class N과M {
static int N,M;
static int[] selected;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken()); //1~N 까지의 자연수
M = Integer.parseInt(st.nextToken()); //수열의 길이
selected = new int[M];
dfs(0,selected,new boolean[N+1]);
System.out.println(sb);
}
static void dfs(int depth,int[] selected,boolean[] visited){
if(depth == M){
for(int value : selected) sb.append(value + " ");
sb.append("\n");
return;
}
for(int i=1;i<N+1;i++){
if(visited[i]) continue;
visited[i] = true;
selected[depth] = i;
dfs(depth+1,selected,visited);
visited[i] = false;
}
}
}
중복순열
중복 순열의 경우 똑같은 원소를 여러번 뽑아도 되지만,원소의 배열이 중복되는 경우가 없게 구현해야한다.
방문 체크 할 필요 없이. 원소를 순서대로 얻어가면된다.
public static void permutation(int[] arr, int[] out, int depth, int r){
if(depth == r){
for(int num: out) System.out.print(num);
System.out.println();
return;
}
for(int i=0; i<arr.length; i++){
out[depth] = arr[i];
permutation(arr, out, depth+1, r);
}
}
public static void main(String[] args){
int[] arr = {1, 2, 3};
int r = 2;
permutation(arr, new int[r], 0, r);
}
부분집합
부분집합은 주어진 원소에서 몇개만큼 고르는지 알려주지않는다.
0개를 고를수도,1개를 고를수도 n개를 고를수도 있다..
이 문제의 경우 2차원 배열에서 두 곳을 선택해야한다.
두곳이 어디가 될지는 모르고 조건에 맞는 두곳을 선택해야한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* @see
* @since 2023-10-12
**/
public class Solution {
static int T,N,M,C;
static int[][] map;
static int[] selected;
static int sumA,sumB;
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int t=1;t<T+1;t++){
st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new int[N][N];
selected = new int[2];
answer = Integer.MIN_VALUE;
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<N;j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0,0);
System.out.printf("#%d %d \n",t,answer);
}
}
static void dfs(int depth,int idx){
if(depth == 2){
// 두 일꾼이 수확할 벌집의 번호를 모두 선택했다.
// 유효한 좌표인지 검사하기
if(selected[0] >= selected[1] - (M-1)) return;
// 겹치지 않는지 체크한다
if((selected[0] + M - 1) / N != selected[0] / N || (selected[1] + M - 1) / N != selected[1] / N) return;
// 같은 열에 있는 통이 아니라면 리턴한다
int honey = getMaxHoney(selected[0],selected[1]);
answer = Math.max(honey,answer);
return;
}
for(int i=idx;i<N*N;i++){
// 뒤는 굳이 볼 필요 없다
// 순서가 의미 없기 때문
selected[depth] = i;
dfs(depth+1,i+1);
}
}
static int getMaxHoney(int a,int b){
sumA = 0;
for(int r=1;r<=M;r++){
// r개를 뽑는다
combination(a,a+M,r,0,0,0,1);
}
sumB = 0;
for(int r=1;r<=M;r++){
combination(b,b+M,r,0,0,0,2);
}
return sumA + sumB;
}
static void combination(int start,int end,int r,int sum,int rev,int depth,int type){
if(depth == r){
// r개를 뽑는다
if(sum > C) return;
if(type == 1) sumA = Math.max(sumA,rev);
else sumB = Math.max(sumB,rev);
return;
}
for(int i=start;i<end;i++){
int honey = map[i/N][i%N];
combination(i+1,end,r,sum+honey,rev+(int)Math.pow(honey,2),depth+1,type);
}
}
}정리
지금까지 순열 조합 중복순열 중복조합 부분집합에 대해서 알아보았다.
각각의 단어의 의미를 이해하고 dfs 재귀에 대해서 깊이 이해하고있다면.
방문체크,시작값 늘려주기 등등을 통해 간단하게 다양한 경우의 수를 구할 수 있다는 것을 알 수 있다.
위와 같은 경우의 수를 구해야하는 코드의 경우 남의 코드를 외우기 보다는 본인만의 코드를 만든 다음 본인에게 맞는 코드를 작성해가며 체화하는 것이 적절할 것 같다.
Union Find
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* 유니온 파인드로 풀어보기
* @see
* @since 2023-10-11
**/
public class Solution {
static int T;
static int N, M; // 노드의 수, 간선의 개수
static int[] parent; // 부모노드를 저장 할 배열
static int answer; // 정답을 저장할 변수
public static void main(String[] args) throws IOException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parent = new int[N+1]; // 1부터 저장할 것이기 때문에 하나 더 크게 저장해줍니다
answer = 0;
for(int i=1;i<=N;i++) parent[i] = i;
for (int m = 0; m < M; m++) {
st = new StringTokenizer(br.readLine(), " ");
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());
union(parent,i,j); // 변수를 입력 받을때마다 union 연산을 통하여 연결해줍니다
}
for(int i=1;i<=N;i++){
if(parent[i] == i) answer++;
}
//자기자신을 가리키는 노드의 개수 = 무리의 개수
//자기자신을 가리키는 노드가 대표 부모이기 때문이다.
System.out.printf("#%d %d \n",t+1,answer);
}
}
// union find
// union method
static void union(int[] parent,int x,int y){
// a와 b를 합쳐준다
// 부모를 같게 만들어준다
// 부모를 끝까지 찾아내서 부모를 같게 해주기
x = find(parent,x);
y = find(parent,y);
if(x < y) parent[y] = parent[x];
else parent[x] = parent[y];
}
// find method
static int find(int[] parent,int x){
// 부모 인자를 찾아준다
if(x == parent[x]) return x; // 자기자신을 부모로 가지고 있는 노드 일 경우
//자기 자신을 리턴한다
else return parent[x] = find(parent,parent[x]);
}
}
최소신장트리
다익스트라
다익스트라의 경우 코드의 형태를 알고있어야 한다.
항상 최솟값을 가지고 있어야한다 -> PQ or DP 라는 것을 기억하자
아래의 문제의 경우 항상 작은 값을 가지게 만들어야 한다.
아래의 경우에는 visited 배열을 선언하면 안된다. 현재가는 경로가 지금 당장 제일 작은 값을 가질지라도 현재가는 경로의 일부를 지라는 경로가 더 작은 값을 가질지도 모르기 때문에 visited 배열을 사용하여 최솟값을 못구하는 불상사는 없어야 하기 때문이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* @see
* @since 2023/11/15
**/
public class 젤다 {
static class Point implements Comparable<Point> {
int x,y;
int value;
public Point(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
@Override
public int compareTo(Point o) {
return this.value - o.value;
}
}
static int N,min;
static int[][] map;
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int idx = 1;
while(true){
N = Integer.parseInt(br.readLine());
if(N == 0) break;
map = new int[N][N];
min = Integer.MAX_VALUE;
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<N;j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
//가장 최소값으로 가는 경우
int answer = bfs();
System.out.printf("Problem %d: %d\n",idx++,answer);
}
}
static int bfs(){
Queue<Point> pq = new PriorityQueue<>();
int[][] dp = new int[N][N];
for(int n=0;n<N;n++) Arrays.fill(dp[n],Integer.MAX_VALUE);
pq.add(new Point(0,0,0));
dp[0][0] = map[0][0];
while(!pq.isEmpty()){
Point curr = pq.poll();
if(curr.x == N-1 && curr.y == N-1) min = Math.min(min,curr.value);
for(int i=0;i<4;i++){
int nx = curr.x + dx[i];
int ny = curr.y + dy[i];
if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if(dp[nx][ny] > dp[curr.x][curr.y] + map[nx][ny]){
dp[nx][ny] = dp[curr.x][curr.y] + map[nx][ny];
pq.add(new Point(nx,ny,dp[nx][ny]));
}
}
}
return dp[N-1][N-1];
}
}
꿀팁 모음
- N * N 배열에서, 몇개를 선택하는 부분집합 혹은 경우의 수를 구해야하는 경우라면.
2차원 배열을 1차원으로 펼쳐놓고 생각하자.
이를테면 3 * 3 짜리 2차원배열이 있다고 가정하자.
0 1 2
3 4 5
6 7 8
가 이렇게 있다. 여기에서 우리가 원소 두개를 뽑는다고 하자. 이때 2차원 배열에서 선택하려고 들지말고.
2차원 배열의 원소에게 번호를 붙여주는 것이다.
지금의 경우에는 이쁘게 숫자가 붙어있다.
정사각형 형태의 2차원 배열은 N의 크기(넓이,높이)를 이용하여 인덱스를 결정 할 수 있다
숫자를 이용하여 위치를 구할 수 있다.
4번 자리에 있는 수의 위치는 어디일까.
4 / 3 -> 1행 4 % 3 -> 1열
즉,수의 인덱스 정보를 이용하여 위치정보를 알아낼 수 있다는 것이다.
단, 이 방법의 경우 N * N의 경우에만 해당하니까 주의하도록 하자.
2.방향좌표를 잘 이용하자. 평소의 경우라면 방향좌표의 순서를 상관하지 않아도 된다. 그러나, 이러한 경우는 방향좌표의 순서를 정해주면 매우 편하게 풀리는 경우가 있다.
바로,이 문제이다 디저트 카페
이 문제의 경우, 대각선 모양으로 이동하게 되어있으며, 이동궤적의 모양이 항상 사각형의 형태를 가져야 한다. 이럴 경우. 모양을 고정해야하기 때문에. 시계방향 혹은 반시계 방향으로 가되,항상 다음 방향 좌표를 향해 나가도록 설정해주면 사각형을 만들어야 한다는 조건은 쉽게 만족 할 수 있다.
반갑습니다 ! 백엔드 개발 공부를 하고있습니다.