은비블로그

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/1477 [풀이과정]1. 휴게소를 세워서 길이를 비교해 최솟값을 갱신하는 방식2. 적당한 길이로 휴게소를 배치해보고 M개를 충족하는 것 중 가장 작은 값 찾기 2번의 방식으로 답을 구성했고, 이분탐색 방식을 적용했다. [시간복잡도]1. 오름차순 정렬 : O(N logN)2. 이진탐색(needIncreaseDistance) : O(N logL)2-1. 이진탐색 : O(log L)2-2. needIncreaseDistance : O(N) 총 O(N logN) + O(N logL) [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;imp..

https://www.acmicpc.net/problem/2467 [풀이과정]투포인터로 풀었다.0과 가까운 값을 갱신하는 것과 포인터 위치를 변경하는 것의 조건을 각기 다르게 둬야 했는데, 한 번에 처리해서 틀렸다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;/*산성 용액 특성값 1 ~ 10억알칼리성 용액 특성값 -10억 ~ -1두 용액을 혼합하여 0에 가장 가까운 용액 만들기 */public class Main { static BufferedReader br = new Bu..

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/5052 [풀이과정]N이 10,000이어서 문자의 길이를 오름차순으로 정렬 후 비교해줬다.처음엔 StringBuilder를 사용하고 subString, equals 메서드를 사용해서 비교를 해줬는데 시간초과가 났다.그래서 고려한 부분은 1. 정렬 기준길이가 아닌 사전순으로 정렬을 했다. 예로 ["123", "1234", "234"] 이렇게 정렬이 되기 때문에, 앞 뒤의 두 문자열만 비교해주면 쉽게 정답을 알 수 있다.-> Arrays.sort는 O(N logN)의 시간복잡도-> 2개씩 비교하므로 총 N-1의 비교 횟수를 가져서 O(N)의 시간복잡도 2. 접두어 확인 로직String의 startsWith메서드를 사용해서 복잡성을 완화했다. 그래서 O..

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/14921 [풀이과정]완탐으로 하기엔 N이 10만이어서 불가능했다.O(N)의 투포인터로 구현했음.일단 오름차순으로 나열한 후 양끝의 값들을 비교하며 0과의 차이가 가장 적은 걸 찾아줬다.이때 더한 값이 음수라면 오른쪽 포인터를 이동시켜줬고, 양수라면 왼쪽 포인터를 이동시켜줬다.0과의 차이는 절댓값으로 비교해줘야 했지만 실제 출력되는 것은 음수인지 양수인지도 표기해야 했으므로 비교만 절댓값으로 해줬다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Strin..

https://www.acmicpc.net/problem/1043 [풀이과정]예시를 꼭 봐야 문제 이해가 가능한 문제였다.결국은진실을 아는 사람이 한 명이라도 있으면 해당 파티의 참석자는 모두 진실을 안다고 가정하기-> 파티 참석 순서 상관없음.이 조건이었고, 정석적인 유니온 파인드 문제였다. 진실을 아는 사람들과 같은 파티에 참석한 사람들을 모두 같은 그룹으로 묶어주며 진행했다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;/*진실을 아..

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도만 가능..