은비블로그

[백준] 1654 : 랜선자르기 (JAVA)

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

[백준] 11726 : 2 x n 타일링 (JAVA)

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

[백준] 30470 : 호반우가 학교에 지각한 이유 3 (JAVA)

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

[백준] 14940 : 쉬운 최단거리 (JAVA)

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

https://school.programmers.co.kr/learn/courses/30/lessons/299305 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr [풀이과정]COALESCE 메서드 사용.[코드]SELECT A.ID, COALESCE(COUNT(B.ID), 0) AS CHILD_COUNTFROM ECOLI_DATA A LEFT JOIN ECOLI_DATA B ON A.ID = B.PARENT_IDGROUP BY A.IDORDER BY A.ID;

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