Algorithm
[백준] 21939 문제 추천 시스템 Version 1 - Java
[백준] 21939 문제 추천 시스템 Version 1 - Java
2022.04.23기준에 맞춰 정렬해 주기 위해 Comparable 인터페이스를 구현한 클래스를 하나 만들고, 클래스를 바탕으로 트리셋에 넣어 주며 구현하면 풀 수 있는 문제이다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); TreeSet ts = new TreeSet(); HashMap hm = new HashMap(); int N = Integer.par..
[백준] 1351 무한수열 - Java
[백준] 1351 무한수열 - Java
2022.04.23해시 맵으로 메모이제이션을 수행해 풀 수 있는 문제이다. 재귀를 제대로 이해했고, 입력의 타입만 잘 맞춰주면 쉽게 풀 수 있다. import java.util.*; import java.io.*; public class Main041{ static Long P; static Long Q; static Long N; static HashMap hm; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Long.par..
[백준] 2002 추월 - Java
[백준] 2002 추월 - Java
2022.04.23들어오는 차와 나가는 차를 해시맵으로 입력받은 후, 키 값들을 리스트로 빼내서 입력 순서대로 정렬해준다. 나가는 차와 들어온 차를 순서대로 비교해, 같지 않을 때와 같을 때를 따로 처리해줬다. 비교할 때 String에 대한 비교이니 equals메서드를 사용하자. import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int N = Integer.parse..
[백준] 19583 싸이버개강총회 - Java
[백준] 19583 싸이버개강총회 - Java
2022.04.23해시셋을 사용해 조건에 맞게 닉네임을 넣어주고 빼 주는 문제이다. 시간 환산을 위해 hour에는 60을 곱해줬다. 입력의 마지막은 EOF로 처리해야 한다. import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st = new StringTokenizer(br.readLine()); String start_time[] = st..
[백준] 13414 수강신청 - Java
[백준] 13414 수강신청 - Java
2022.04.22해시 맵과 Comparator를 사용해 정렬을 구현하는 문제이다. value값에 대해 정렬을 진행해줘야 하고, keySet에 대해 list를 만든 후 Comparator를 통해 정렬했다. 출력할 때 list의 사이즈가 입력받은 N보다 작다면, N을 list의 사이즈로 설정해줘야 한다. (반례 : 2 2\n 00 00 ) import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new Strin..
[백준] 2910 빈도 정렬 - Java
[백준] 2910 빈도 정렬 - Java
2022.04.21해시 맵과 Comparator를 사용해 풀 수 있는 문제이다. 빈도 수가 같을 때는 먼저 나온 순서대로 정렬해야하는데, 이 부분은 클래스를 사용해 처리했다. import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseIn..
[백준] 9375 패션왕 신혜빈 - Java
[백준] 9375 패션왕 신혜빈 - Java
2022.04.21여집합으로 접근하는 편이 더 합리적이다. 문제를 풀 때 의상의 이름은 어차피 중복되지 않으니 별로 중요하지 않다. 의상의 종류에 초점을 맞춰 풀이하자. 해시맵에 의상의 종류를 넣어준다. (중복되면 값을 +1) 입지 않는 경우를 함께 고려해 value+1 을 진행한 후 모든 경우의 수에서 아무것도 입지 않는 경우를 빼주면 된다. import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new S..
[백준] 9663 N-Queen - Java
[백준] 9663 N-Queen - Java
2022.04.18백트래킹을 사용해서 풀 수 있다. import java.util.*; import java.io.*; // 엔퀸 public class Main1 { static int ans; static int N; static int col[]; // 퀸의위치저장용 i , col[i] public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); col = new int[N+1]; backtracking(1); // 1부터 시작해서 백트래킹함 dfs느낌으로 System.out...
[백준] 20301 반전 요세푸스 - Java
[백준] 20301 반전 요세푸스 - Java
2022.04.18Iterator를 사용하면 쉽게 풀 수 있다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()..
[백준] 3078 좋은 친구 - Java
[백준] 3078 좋은 친구 - Java
2022.04.17처음에 풀다가 틀린 코드 먼저 소개하겠다. import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); LinkedList q = new LinkedList(); for(int i=..
최소 신장 트리 - Kruskal (Union Find)
최소 신장 트리 - Kruskal (Union Find)
2022.04.14신장 트리는 그래프에서 모든 노드가 연결되어 있고, 사이클이 없는 그래프를 의미한다. 최소 신장 트리는 신장 트리에서 가중치를 부여하고, 만들 수 있는 신장 트리 중 가중치의 합이 최소인 그래프를 의미한다. 그래프가 주어졌을 때 최소 신장 트리를 찾을 수 있는 알고리즘으로는 크루스칼과 프림 알고리즘이 있다. 먼저 크루스칼 알고리즘에 대해 알아보자. Kruskal 그리디 알고리즘을 기반으로 해 최소 신장 트리를 구한다. 1. 그래프의 모든 노드들을 연결되지 않은 상태로 놓는다. 2. 존재하는 모든 간선들을 비용을 기준으로 정렬하고, 비용이 적은 간선부터 연결을 시작한다. (같은 비용이면 아무거나 선택해도 괜찮음) 3. 연결된 후 노드들의 최상위 노드를 확인 후 최상위 정점이 같으면 연결하지 않고 (사이클이..
최단 경로 - 다익스트라
최단 경로 - 다익스트라
2022.04.13가중치 그래프에서 가중치의 합이 최소가 되도록 하는 특정 경로를 찾는 알고리즘이다. 다익스트라 (Dijkstra) 그래프의 특정 노드에서 출발해 시작 노드를 제외한 나머지 모든 노드들에 대해 최단 경로를 찾는 알고리즘이다. 그림과 같은 그래프에서 A에서 출발해 B까지 가는 최단 경로를 구한다고 생각해보자. (가중치를 거리라고 생각하자) A에서 B로 바로 가면 거리는 8이지만, C를 거쳐 B를 가면 6의 거리로 갈 수 있으니 여기서 최단 경로는 6이다. A에서 출발해 B로 가는 최단 경로를 구해보자. 1. 시작 노드와 연결된 노드들에 대해 가중치를 저장할 배열을 만들고, 가중치를 저장한다. A : [8(B), 1(C), 2(D)] 2. 저장된 가중치 중에서 최솟값이 가리키는 노드를 기준으로 설정하고 해당 ..