https://www.acmicpc.net/problem/2096   맨 처음 풀었을떄 코드 :  bfs -> 메모리초과import org.w3c.dom.Node;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public static int N; public static int[][] map; public static int max = Integer.MIN_VALUE; public static int min = Integer.MAX_VALUE; public static Queue queue = new LinkedList(); public ..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모www.acmicpc.net   문제를 보고 .replace()같은 라이브러리를 쓰면 무조건 시간초과가 날것이 뻔했으므로O(N)혹은 최대 O(KN) (K = 36)안에 문제를 해결하는 방법을 찾다가문자열 수식에서 괄호의 유효성을 체크하는 문제가 떠올라서스택으로 풀었다. 처음에 한번 풀다가 틀렸었는데 틀린 이유는 모든 문자를 일단 스택에 집어넣어야한다는점을 간과했다. 나는 PS를 할때 자바를 사용하는데 그 이유는 클..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연www.acmicpc.net   단순히 모든 node에대해 dfs / bfs를 수행해도 통과할수있는 문제  1) - 단순 bfs + 브루트포스import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public static int N; public static int ans;..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그www.acmicpc.netimport java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public static int N; public static int V; public static ArrayList[] adjacentList; public stat..

https://www.acmicpc.net/problem/1753 1753번: 최단경로첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가www.acmicpc.net   방문노드체크 + 우선순위 큐 + 다익스트라 로 최대한 그리디하게 풀지않으면 메모리초과가 난다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.lang.reflect.Array;import java.util.*;public class Main { public static..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존www.acmicpc.net    1)번 케이스 : (1 -> v1)  + (v1 -> v2) + (v2 -> N)2)번 케이스 : (1-> v2) + (v2 -> v1) + (v1 -> N) 각각의 케이스는 다익스트라로 구해주고 1) ,2)중 최솟값을 찾으면된다. 이거까지 스스로 다 생각해놓고, 이상한거에서 헤메다가 계속 틀림ㅜㅜ  import java.io.BufferedReade..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x www.acmicpc.net    처음에 순수 DP로 풀었으나 실패해서 BFS + DP(??) 를 활용해서풀었다 import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public cla..

https://www.acmicpc.net/problem/9019 9019번: DSLR네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에www.acmicpc.net   처음에그냥 Queue에 D S R L 으로 커맨드 하나씩 붙혀서 넣었더니메모리 초과가 났다. 메모리 초과라는것은큐에 들어가는 아이템의 수가 과도하게 많다는뜻인데, 처음에는 RL , LR과같이 R과 L이 연속으로붙어있으면 결국 제자리이기떄문에 그것을 걸러주었다. 하지만 시간초과가 해결이안되었다. 구글링을해보니숫자가 결국엔 0~ 9999이기떄문에 visited[10000]으로 중복수를 걸..