알고리즘/백준

문제 출처 : https://www.acmicpc.net/problem/12852 소요 시간 : 풀이(55m) + 더 좋은 풀이(15m) 문제 시도 & 풀이 일단 DP로 풀었다. package coding.DP3; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class bj_12852 { static Point[] points; public static void main(String[] args) throws IOException { int N = read(); solve(N, 0); printResult(N); } static ..

문제 출처 : https://www.acmicpc.net/problem/1450 소요 시간 : 풀이(1h) 문제 시도 투 포인터의 최종 문제로 난이도가 상당했다. 일단 일반적인 접근법인 start, end의 두 기준으로 투 포인터를 구현했는데, 풀다보니 해당 문제는 경우의 수까지 고려해야 하는 문제라는 걸 알게 되었고, 결국 다른 사람의 풀이를 참고했다. 풀이 해당 문제의 접근법은 다음과 같다. N을 반으로 나누어 start ~ N/2, N/2 ~ end 범위에서 각각 완전탐색을 하여 만들 수 있는(C 이하) 모든 무게를 찾아 각각 배열(aSum, bSum)에 담는다. aSum, bSum 중 하나를 기준으로 이진탐색을 수행해야 하기에 기준이 아닌 다른 배열을 오름차순으로 정렬한다. aSum 각각의 모든 ..

문제 출처 : https://www.acmicpc.net/problem/1806 소요 시간 : 시도(40m) + 풀이(30m) 문제 시도 문제를 제대로 이해하지 않고 '그냥 투 포인터 쓰면 되겠지' 하면서 정렬하기 시작하면서 꼬이기 시작했고, 결국 40분을 온전히 낭비하고 장렬히 실패했다. 아래는 문제가 뭔지도 모르고 바보 같이 작성한 코드다. // n (수열 요소 범위) : 1 ~ 10,000 // N (수열 길이) : 10 ~ 100,000 // S (목표 합) : 1 ~ 100,000,000 import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws IOException { Buffer..

문제 출처 : https://www.acmicpc.net/problem/1504 소요 시간 : 시도(1h 30m, 실패) + 풀이(20m) 문제 시도 기존에 이미 방문했던 정점도 다시 방문 가능하다는 점에서 플로이드-와샬 알고리즘 써도 풀리지 않을까 싶어 시도해봤다. /* 원래의 '최단 경로'라면 그냥 BFS로 이동하기 때문에 정점과 간선에 대한 중복을 허용하지 않지만 이 문제의 경우 반드시 방문해야 하는 특정 정점으로 인해 중복을 허용한다는 점이 가장 중요해보인다. BFS를 시도하되, 1번 정점에서 특정 정점에 도착할 때, 중간에 방문해야 하는 특정 정점에 모두 방문했는지 확인한다. int[][] matrix = new int[N+1][N+1]; */ import java.io.*; import jav..

문제 출처: 11404번: 플로이드 (acmicpc.net) 소요 시간: 시도(1h 30m 이상) 문제 시도 문제 분류는 '최단 경로'이지만 다른 문제에서 BFS만으로 풀 수 있었기에 BFS로 풀어보려고 했는데, 갈 수 없는 지점을 찾기 위한 과정을 찾는 방법을 알아내지 못해 결국 실패했다. 풀이 이 문제는 플로이드-와샬 알고리즘을 사용하는 기초 문제로, 주의해야 했던 점은 도시에 대한 중복 접근이 가능하기 때문에 기존 BFS처럼 방문 여부 집합인 visited를 쓰지 않는다는 것이었다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader..

문제 출처 : https://www.acmicpc.net/problem/16928 소요 시간 : 1h 30m (시도) 문제 시도 그냥 평소 풀던 대로 BFS를 적용했다. import java.io.*; import java.util.*; public class Main { private static int[] board = new int[101]; private static int[] cross = new int[101]; private static Queue queue = new LinkedList(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStre..

문제 출처 : https://www.acmicpc.net/problem/7562 소요 시간 : 풀이(1h) 문제 풀이 바로 이전 문제인 `백준 1697: 숨바꼭질`의 풀이법과 동일해서 어떻게 풀어야하는지는 바로 알았다. 대신 저번 문제는 무력하게 다른 답안을 참고해서 풀었기 때문에 이전에 푼 풀이를 그대로 하드코딩하는 건 무용하다고 생각해 내가 스스로 점검해나가며 풀어보려고 시간이 좀 걸렸다. import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { private static int[][] board; private stati..

문제 출처: https://www.acmicpc.net/problem/1697 소요 시간: 시도(1h) + 풀이(30m) 문제 시도 처음엔 DFS를 시도해봤지만 바로 실패했다. 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static int end; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sys..

문제 출처 : https://www.acmicpc.net/problem/24444 소요 시간 : 시도(30m) + 풀이(20m) 문제 시도 문제에서 주어진 Pseudo 코드를 기반으로 코드를 작성했다. import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { private static BufferedReader br; private static StringTokenizer st; private static boolean[] visited; private static ArrayList graph; private static Qu..

문제 출처: https://www.acmicpc.net/problem/24480 소요 시간: 시도 & 풀이(10m) 문제 풀이 앞서 풀었던 깊이 우선 탐색 1의 코드에서 정렬을 오름차순에서 내림차순으로 바꾸면 되는 간단한 문제였다. import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Collections; import java.util.StringTokenizer; import java.util.ArrayList; public class Main { private static int N, M, R; private static int[] visited; priva..