은비블로그

[백준] 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. 잘린 나무 획득..

[백준] 1463 : 1로 만들기 (JAVA)

https://www.acmicpc.net/problem/1463 [풀이과정]DP문제. N을 index로 두고DP[N]를1 ) 3으로 나뉠 때 -> DP[N/3] + 12 ) 2로 나뉠 때 -> DP[N/2] + 1 3 ) -1 할 때 -> DP[N-1] + 13가지 중 가장 작은 값으로 갱신하며 채우기. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. 1을 뺀다. */public class Main{ static Bu..

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/11726 [풀이과정]전형적인 DP 문제다. 점화식으로 풀면 됨.직접 타일을 그려보면  f(n-1)의 가짓수에 세로 타일을 하나씩 붙이고 + f(n-2)의 가짓수에 가로 타일 2개가 붙은 모양임f(0) = 1, f(1) = 1 이고f(n) = f(n-2) + f(n-1) [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/*2xn 크기의 직사각셩을 1x2,2x1 타일로 채우는 방법의 수 구하기 */public class Main { static BufferedReader br = new BufferedReader(new Inp..

https://www.acmicpc.net/problem/30470 [풀이과정]stack을 사용하였고 max가 갱신될 때마다 stack에 저장된 값들을 확인하면서 길이를 갱신하며 pop, push를 해주었는데 틀림. 로직은 맞는 것 같은데 왜 틀린지 잘 모르겠음.정답코드는 max 갱신 시마다 값을 확인하는 로직을 없앰. 새로 추가되는 통나무가 항상 제일 긴 통나무이고 max 값을 기준으로 통나무 길이가 갱신되는 것이기 때문에 max값만 저장해준 후 sum 값을 구할 때 로직 실행해켜주면 됨. [코드]import java.io.*;import java.util.*;public class Main { static BufferedReader br = new BufferedReader(new InputSt..

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/2631 [풀이과정]전형적인 LIS 문제였다. N이 200으로 작아서 O(N^2)인 DP 방식으로 풀이했음.N이 커지면 O(nlogn)인 이분탐색으로 풀이해야 한다. 현재 탐색 중인 번호의 이전 번호들을 보면서 더 크면 DP[현재 번호] = DP[이전 번호 중 가장 큰 값을 가진 번호] + 1을 해주는 것  [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;/*N명의 아이들1번부터 N번. 옮기는 순서를 최소로 하여 일렬로 정렬 */..

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/22869 [풀이과정]단순히 도달여부를 확인하기만 하면 되는 문제.O(N^2)이 2500만이어서 DFS로 풀었다가 시간초과가 발생했다. 단순히 N^2이 아닌 실제로 호출되는 함수가 컸던 부분이 원인이었음.DP를 이용해서 도달 가능한 부분만을 true로 삼아 경로를 확인하는 방식으로 호출 횟수를 줄임. [코드]import java.util.*;import java.lang.*;import java.io.*;/*사용하는 힘은 항상 양수.오른쪽으로 갈 때 사용해야 하는 힘이 K가 넘지 않을 때 이동 가능끝까지 도착이 되는지의 유무 계산*/class Main { static BufferedReader br = new BufferedReader(new..

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