본문 바로가기

Algorithm (PS)63

[백준] 2252. 줄세우기(Java) [위상정렬] 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 알고리즘 위상정렬 풀이 1. 진입 차수가 0인 정점을 큐에 삽입한다. 2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다. 4. 큐가 빌 때 까지 2~3번 반복. 코드 package com.company; import java.io.*; import java.util.*; publi.. 2023. 7. 25.
[백준] 1922 (Java) [MST 알고리즘] 문제 https://www.acmicpc.net/problem/1922 알고리즘 크루스칼 알고리즘 풀이 가중치가 짧은 순으로 정렬을 해주고 UnionFind를 통해 그래프를 연결해준다. 그 과정에서 가중치를 더하며 정답을 구한다. 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; public class Test_Cruskal { static in.. 2023. 7. 25.
[백준] 1717 집합의 표현(Java) [Union-Find] 문제 https://www.acmicpc.net/problem/1717 알고리즘 Union-Find 풀이 대표적인 union-find 문제이다. parent를 얻어오는 함수, parent를 합치는 함수, parent가 동일한지 확인하는 함수를 구현한 후 입력 받는 flag에 따라 parent를 합치거나 출력한다. 코드 package com.company; import java.io.*; import java.util.StringTokenizer; public class Test_UnionFind { static int N, M; static int[] parent; public static void main(String args[]) throws IOException { BufferedReader bf .. 2023. 7. 24.
[백준 9663] N-Queen (Java) [백트래킹] 문제 https://www.acmicpc.net/problem/9663 알고리즘 백트래킹 풀이 특정 규칙을 파악하면 바로 풀 수 있는 문제이다. 15x15의 모든 경우의 수를 파악하게 된다면 15!이므로 시간초과가 나게 된다. 따라서 특정 조건에 맞는다면 재귀를 타게하고 조건에 맞지 않는다면 스킵하면 백트래킹 처리를한다. 체스를 놓을 때마다 각 행에 대해 퀸의 위치를 마킹하고, 만약 전에 놓았던 퀸이 있다면 퀸을 놓을 수 있는 위치를 파악하며 문제를 풀이한다. 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Test_Bac.. 2023. 7. 20.
[백준 1753] 최단경로(Java) 다익스트라 문제 https://www.acmicpc.net/problem/1753 알고리즘 다익스트라 (우선순위 큐 사용) 풀이 이 문제는 가중치가 1이 아니고 음의 가중치도 아니기 때문에 다익스트라를 이용하여 풀이 할 수 있다. 먼저 모든 노드의 거리를 무한으로 초기화 한다. 그리고 우선순위 큐를 사용하여 간선의 거리가 짧은 것부터 나오도록 해주어 시작점부터 다른 노드까지의 최소 거리를 구한다. 코드 package com.company; import java.io.*; import java.util.*; public class Test_dijstra { static int V,E; static int start; static int[] dist; static List[] graph; static final int.. 2023. 7. 19.
[백준 14501]. 퇴사 (Java) - 완전탐색 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 알고리즘 완전탐색 풀이 완전탐색을 통해 상담할 수 있는 모든 경우의 수를 구한다음 최대 값을 구해주어 풀었다. 1개 의 상담에 대해 선택 O/X하는 2가지의 경우가 존재하므로 전체 N개 상담에 대한 최대 경우의 수 = 2^n => 32,768이다. 조건 값이 적어서 그렇지 많게 되면 dp로 풀어야한다. 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.. 2023. 7. 17.

티스토리툴바