은비블로그

https://www.acmicpc.net/problem/14940 [풀이과정]메모리 초과 이유1. 각 지점을 출발점으로 해서 도착지점까지의 거리를 구하고, 이때 이미 구해진 지점이 있으면 depth랑 해당 값을 더해주고 탐색 마치는 로직으로 구현했는데 메모리 초과가 떴음. 매 지점마다 queue를 생성하고 탐색해서 그런 듯.도착지점을 시작점으로 두고 나머지 지점까지의 거리를 구하면 됨.  2. visited 체크를 queue에서 뽑을 때 하고 있었음. 상하좌우 탐색하는 로직 내부에 넣어야 하는데 이런 실수 다신 하지 말자 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import j..

https://www.acmicpc.net/problem/15666 [풀이과정]중복되는 부분을 어떻게 해결해야 하는지 고민하다가 시간이 오래 걸렸음.DFS로 재귀호출 시에 for문 시작 index를 이전 DFS와 같게 하되 배열[index]의 값이 다른 경우에만 값을 sb에 넣게 했다.이렇게 해야 중복 없는 수열이 나옴. [코드]import java.util.*;import java.lang.*;import java.io.*;/*N개 중 M개 고르기중복 가능오름차순*/class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringBuilder sb = new Stri..

https://www.acmicpc.net/problem/2668 [풀이과정]시작 index와 끝 배열값이 같으면 되는 문제다. (사이클) [코드]import java.util.*;import java.io.*;/*세로 두 줄, 가로로 N개의 표첫째 줄은 1, 2, 3, ..., N둘째 줄은 N이하의 정수첫째 줄에서 숫자를 뽑으면 뽑힌 정수들이 이루는 집합과뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이일치함정수를 최대한 많이 뽑는 방법을 찾기 */public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringBuilder sb = n..

https://www.acmicpc.net/problem/16637 [풀이과정]리스트 두 개를 사용해서 괄호 있는 계산, 없는 계산 나눠서 DFS로 풀었다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;/*길이가 N. 정수, 연산자로 이루어져 있음.연산자 우선순위는 모두 동일함.단, 괄호 안의 식은 먼저 계산해야 하고 중첩된 괄호는 사용할 수 없음괄호를 추가해 만들 수 있는 식의 결과의 최댓값 구하기 */public class Main { static BufferedRea..

https://www.acmicpc.net/problem/1240 [풀이과정]BFS로 풀었다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;/*N개의 노드로 이루어진 트리M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력 */public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static..

https://www.acmicpc.net/problem/1068 [풀이과정]노드 삭제 후 그냥 탐색하면 되는데 복잡하게 생각했던 것 같다.항상 간단하게 생각하는 습관을 들이자 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;/*트리가 주어졌을 때 노드 하나를 지우면남은 트리에서 리프 노드의 개수를 구하기리프노드 : 자식의 개수가 0인 노드 */public class Main { static BufferedReader br = new BufferedReader(new Inpu..

https://www.acmicpc.net/problem/7569 [풀이과정]이전에 풀었던 2차원 토마토 문제를 3차원으로 늘린 것 뿐인 문제였다.https://www.acmicpc.net/problem/7576근데 row랑 column 헷갈려서 헤맸는데, 다음부턴 더 꼼꼼하게 풀기 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;/*M*N*H 크기의 상자익은 토마토의 인접(위,아래,왼쪽,오른쪽,앞,뒤)한 토마토는 익게 됨.보관된 토마토가..

https://www.acmicpc.net/problem/17070 [풀이과정]DFS 로 풀었다. 처음엔 파이프 길이가 2이고 벽을 긁지 말란 말에 벽과 수평으로 움직이지 말란 건가 혼란스러웠지만 그냥 오른쪽 끝 부분을 옮기면서 이동 가능 여부(빈 칸인지)만 확인하면 됐다.DP로 풀 수 있다는데 나중에.. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*크기가 N*N인 집파이프는 회전 가능하며 2개 칸을 차지.-, |, \ 방향 가능. 파이프는 →, ↘, ↓ 으로 이동.빈 칸만 차지하며 벽을 긁으면 안됨.회전은 45도만 가능..

https://www.acmicpc.net/problem/24230 [풀이과정]N의 크기가 20만이었기 때문에 시간 복잡도가 N^2이 되면 시간초과가 일어난다.복잡도를 줄이려고 처음엔 값 변경을 하지 않고 부모와 색이 다른지 안 다른지 확인하는 방법을 생각하려 했는데,그냥 부모랑 색이 다르면 색칠 횟수 +1 해주면 되는 문제였다. 그럼 복잡도가 O(N)임.그리고 문제 예시가 순차적이었어서 무방향 그래프인 걸 놓쳤다. 그래서 엄청 헤맸다.이 부분은 잘 숙지해서 다음엔 놓치지 않기. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import..

https://www.acmicpc.net/problem/2206[풀이과정]처음엔 DFS로 풀었는데, 값이 너무 커서 BFS로 풀었다.3차원 배열을 사용해서 해당 위치에 벽을 부수고 도착했을 때와 벽을 부수고 도착하지 않았을 때를 나누어서 탐색했다. [BFS 코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;/*N*M 맵. 0은 이동 가능 한 곳, 1은 이동할 수 없는 벽이 있는 곳(1,1)에서 (N,M)의 위치까지 최단 경로로 이동.시작하는..