은비블로그

[백준] 2805 : 나무자르기 (JAVA)

https://www.acmicpc.net/problem/2805 [풀이과정]나무 길이를 골라야 하는데 길이의 최댓값이 너무 커서 이분탐색을 사용했다.1. 나무를 정렬2. 가장 긴 나무길이를 high로 두고 이분탐색 시작 3. 충족하는 길이가 나오면 결과값을 갱신해주며 low 값 갱신 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Collections;import java.util.StringTokenizer;/*나무 M미터가 필요.1. 높이 H를 지정 -> 한 줄에 연속해있는 나무 모두 절단2. 잘린 나무 획득..

https://www.acmicpc.net/problem/1654 [풀이과정]이분탐색 문제다.오랜만에 풀어서 로직이 헷갈렸는데 mid 값 갱신 시 +1, -1 해주기. low는 0으로 두지 말기. 두 가지 복기하자. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*K개의 랜선 보유 - 길이가 다 다름N개의 같은 길이의 랜선으로 만들기 위해 K개의 랜선을 자르기(ex. 300cm : 140cm 두 개를 위해 20cm 버려야 함)N개보다 많이 만드는 것도 N개를 만드는 것에 포함.만들 수 있는 최대 랜선의 길이 구하기 */pub..

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/17140 [풀이과정]Node class가 Comparable 인터페이스를 상속하게 함.PriorityQueue를 사용해서 정렬해가며 배열 재구성 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashMap;import java.util.Map;import java.util.PriorityQueue;import java.util.StringTokenizer;/*크기가 3X3인 배열 A1. R연산 : 배열 A의 모든 행에 대해 정렬 수행. 행의 개수 >= 열의 개수인 경우 적용2. C연산 : 배열 A..

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/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..