[백준 / JAVA] 2467. 용액(G5) https://www.acmicpc.net/problem/2467 괜시리 브루트포스로 한번 풀어보고 싶어지는 문제이다.당연히 틀리고 min값을 이정표로 투포인터를 지정했다가 또 틀렸다. 방향성은 맞는 것 같은데 왜 틀렸는가 장정 일주일 동안 고민 끝에 min값이 아니라 이전 계산값을 기준으로 포인터를 움직여야 한다는 것을 깨달았다. import java.io.*;import java.util.*;public class Main { static BufferedReader br; static StringTokenizer st; static StringBuilder sb; public static void main(String[] args) throws Exception { br = new Buffered.. [백준 / JAVA] 2166. 다각형의 면적(G5) https://www.acmicpc.net/problem/2166 https://ggaebap.tistory.com/140 [JAVA] 신발끈 공식좌표평면상의 좌표로 구성된 다각형의 면적을 구하는 공식이다. 좌표값이 다갹형을 구성하는 시계 또는 반시계 방향으로 주어져야 사용 가능하고 변이 교차하는 경우는 사용할 수 없어 쓰임새ggaebap.tistory.com 너 이 공식 알아? 모르면 틀려야지를 시전하는 내가 싫어하는 유형의 문제이다. import java.io.*;import java.util.*;public class Main { static BufferedReader br; static StringTokenizer st; static StringBuilder sb; pub.. [백준 / JAVA] 10942. 팰린드롬?(G4) https://www.acmicpc.net/problem/10942 이거 왜 단순구현으로 풀림? 시간초과 나오면 2차원 배열로 구간 값을 저장해서 시도했을 것 같은데 그게 정답이라 하더라도 DP라고 보기엔 애매한 느낌이다.(브루트포스 아닌가...) import java.io.*;import java.util.*;public class Main { static BufferedReader br; static StringTokenizer st; static StringBuilder sb; public static void main(String[] args) throws Exception { br = new BufferedReader(new InputStreamReader(.. [JAVA] 그래프와 다익스트라 DFS를 쓰면 시간 초과가 나고, BFS를 쓰면 메모리 초과가 나서 문제 분류를 보면 DP거나 다익스트라였던 적이 있는가?고통받은 김에 정리해봤다. class Graph { Deque[] dqArr; // 연결 노드를 저장할 자료구조 int nodeCount; // 노드 개수 public Graph(int nodeCount) { // 그래프 선언 this.nodeCount = nodeCount; dqArr = new Deque[nodeCount + 1]; for (int i = 0; i (); } void addEdge(int start, int dest, int cost) { // 그래프에 간선 추가 dqArr[start].add(new Node(dest, cost)); } .. [백준 / JAVA] 2638. 치즈(G3) https://www.acmicpc.net/problem/2638 bfs한번 사방탐색 한번이면 풀 수 있는 데다가 맵 크기도 작아서 골드 3 답지 않은 문제이다. import java.io.*;import java.util.*;public class Main { static BufferedReader br; static BufferedWriter bw; static StringTokenizer st; static StringBuilder sb; public static void main(String[] args) throws Exception { br = new BufferedReader(new InputStreamReader(System.in)); st = new StringTokenizer(br.. [백준 / JAVA] 1987. 알파벳 (G4) https://www.acmicpc.net/problem/1987 싸피 때 비슷한 문제를 풀었던 기억이 있다. 벽 부수고 이동하기 시리즈인데 핵심은 탐색을 할 때 탐색하는 주체에 상태를 저장하는 것이다. 이 문제에선 해당 알파벳을 지났는지 여부를 배열로 객체 안에 넣었다. 이제 골드 문제 4개를 날먹할 수 있을 것이다. import java.io.*;import java.util.*;public class Main { static BufferedReader br; static BufferedWriter bw; static StringTokenizer st; static StringBuilder sb; public static void main(String[] args) thr.. [백준 / JAVA] 9935. 문자열 폭발 (G4) https://www.acmicpc.net/problem/9935 처음엔 디큐(남들은 데크라고 함) 두 개를 써서 풀려고 했다. 두 디큐를 왔다갔다 하면서 뒤에서 빼줬다. 어차피 문자열 100만자 해봤자 200만 바이트 즉 2메가인데 메모리는 생각 자체를 안했다. 그리고 메모리가 터졌다. 내 속도 터졌다. 일주일이 지났다. 기부니가 안조아서 종일 누워있다가 스트레스 하나라도 해소할 겸 문제를 열었다. 디큐는 가변 메모리구조나 하나를 쓰든 두개를 쓰든 똑같겠지만 디큐를 하나만 써봤다. 메모리 초과가 났다. ArrayList 디큐가 LinkedList보다 메모리를 적게 쓴대서(속도는 더 느린걸로 암) 바꿨다. 시간초과가 났다.(2차위기) 코드를 다 지우고 문제의 비밀을 파헤쳤다. 이 문제의 비밀은 입력을 .. [백준 / JAVA] 19238. 스타트 택시 (G2) https://www.acmicpc.net/problem/19238 어렵지 않고 풀이도 바로 보이는 문제이다. 아마 승객 탑승 지점과 도착 지점을 저장하는 방식 정도만 사람마다 다를 것 같다.나는 탑승 지점 지도를 따로 만들었는데, 2차원 맵에 인덱스를 저장하고 싶을 때 문제에 벽 같은 조건이 들어가 있어 곤란하다면 맵을 분리하면 편하다.(어차피 벽이 쓰이는 곳은 bfs에서 뿐임)도착 지점은 리스트로 저장했는데, 도착 지점은 중복될 수 있다는 점이 이 문제의 유일한 함정 같았다. 이걸 고려 안 해서 틀리는 경우가 있을진 모르겠다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Ma.. 이전 1 2 3 4 5 다음
