코딩테스트 준비612 [백준] 11054번 - 가장 긴 바이토닉 부분 수열 [Java] https://www.acmicpc.net/problem/11054 1. 아이디어 앞에서 뒤로 LIS를 구하고 뒤에서 앞으로 LIS를 구하면 간단하게 해결할 수 있다.2. 문제풀이 아이디어처럼 서로 다른 방향으로 LIS를 구한 후 같은 인덱스를 비교해보면 두 LIS의 길이의 합 - 1 이(자기 자신 제외) 바이토닉 부분 수열의 길이가 되는 점을 활용해서 구현했다. 이때 뒤에서 앞으로 LIS를 구해야하고 앞에서 뒤로 LDS를 구하는 것이 아님에 주의해야했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Buffered.. 2025. 1. 13. [백준] 11722번 - 가장 긴 감소하는 부분 수열 [Java] https://www.acmicpc.net/problem/11722 1. 아이디어 대표적인 LIS 알고리즘 문제로 다이나믹 프로그래밍을 활용해서 해결할 수 있다.2. 문제풀이 이전 가장 긴 증가하는 부분 수열 문제에서 증가만 감소로 바뀐 문제로 안쪽 for문의 비교 부분만 바꾸면 간단하게 구현할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeniz.. 2025. 1. 13. [백준] 11053번 - 가장 긴 증가하는 부분 수열 [Java] https://www.acmicpc.net/problem/11053 1. 아이디어 대표적인 LIS 알고리즘 문제로 다이나믹 프로그래밍을 활용해서 해결할 수 있다.2. 문제풀이 dp 배열은 수열과 같은 위치의 인덱스에 해당 수를 포함하는 가장 큰 증가하는 부분 수열의 길이를 저장한다.구현은 2중 for문을 활용하면 간단하게 해결할 수 있는데 첫 for문으로 dp 배열을 쭉 돌고 안쪽 for문은 이전 원소들에 대해 현재 수열의 수보다 작은 수를 발견하면 현재 수의 LIS와 해당 수의 LIS를 비교 갱신하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args.. 2025. 1. 13. [백준] 16401번 - 과자 나눠주기 [Java] https://www.acmicpc.net/problem/16401 1. 아이디어 과자 길이에 대한 매개 변수 이분 탐색을 활용하면 해결할 수 있다.2. 문제풀이 이분 탐색은 나눌 길이를 찾고 count 메서드는 찾은 길이로 줄 수 있는 과자 개수를 구하도록 구성했다.같은 개수를 줄 수 있을 때 최대 길이를 구해야하므로 N개보다 적은 개수가 나오는 직전 길이를 구하는 Upper Bound로 계산 후 -1을 해서 N개가 나오는 최대 길이를 구하도록 했다. 이때 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없으면 0을 출력해야 하는데 이분 탐색에서 mid 값이 0이 되는 순간이므로 이때는 1을 반환하도록 조건 처리를 했다.3. 코드 import java.io.*;import java.util.*;pub.. 2025. 1. 13. [백준] 2805번 - 나무 자르기 [Java] https://www.acmicpc.net/problem/2805 1. 아이디어 나무 높이에 대한 매개 변수 이분 탐색을 활용하면 해결할 수 있다.2. 문제풀이 이분 탐색은 자를 높이를 찾고 cut 메서드는 찾은 선택한 높이로 잘랐을 때 얻을 수 있는 나무를 구하도록 구성했다.얻을 수 있는 나무가 M 이상일 때 높이의 최댓값을 구해야 하는 것은 얻을 수 있는 나무가 M미만인 순간 높이의 최댓값에서 1을 빼서 M 이상을 얻을 수 있는 높이의 최댓값을 구하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 1. 13. [백준] 1654번 - 랜선 자르기 [Java] https://www.acmicpc.net/problem/1654 1. 아이디어 랜선에 대한 매개 변수 이분 탐색을 활용하면 해결할 수 있다.2. 문제풀이 이분 탐색은 랜선의 길이를 찾고 count 메서드는 찾은 랜선의 길이로 잘랐을 때 랜선의 개수를 구하도록 구성했다.랜선의 개수가 동일한 길이가 여러 개일 때 최대 길이를 찾아야 하므로 매개변수 이분 탐색의 Upper Bound로 N개를 만들 수 있는 최대 길이를 초과하는 최초 길이를 구하고 1을 빼서 값을 구하는 방식으로 구현했고 랜선의 길이가 int형 최대 범위와 일치해서 이분 탐색을 할 때 최초 high 값을 이보다 크게 설정해줘야 했다.3. 코드 import java.io.*;import java.util.*;public class Main {.. 2025. 1. 13. [백준] 10816번 - 숫자 카드 2 [Java] https://www.acmicpc.net/problem/10816 1. 아이디어 Map 자료구조로 간단하게 해결할 수 있다.2. 문제풀이 주어진 정수를 몇 개 가지고 있는지 구해야 하는 문제로 key에 정수, value에 해당 정수의 개수를 저장하는 HashMap을 활용하면 간단하게 해결할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter .. 2025. 1. 13. [백준] 10815번 - 숫자 카드 [Java] https://www.acmicpc.net/problem/10815 1. 아이디어 Set 자료구조로 간단하게 해결할 수 있다.2. 문제풀이 주어진 정수가 상근이가 가지고 있는 숫자 카드에 적혀있는지 여부만 판단하면 되므로 HashSet을 활용해 포함 여부만 판단하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new B.. 2025. 1. 13. [백준] 2473번 - 세 용액 [Java] https://www.acmicpc.net/problem/2473 1. 아이디어 기존 두 용액 문제에서 용액의 수가 하나 더 늘어난 문제로 반복문 내에서 투 포인터 알고리즘을 돌리는 방식으로 세 용액을 다룰 수 있다.([코딩테스트 준비/백준] - [백준] 2470번 - 두 용액 [Java])2. 문제풀이 용액 하나를 고정시키고 투 포인터 알고리즘을 돌리면 세 용액을 다룰 수 있다. 이때 고정시킨 용액을 반복문으로 처리하면 되며 세 용액의 합을 구하는 과정에서 int형 오버플로우가 발생하는 것에 대비해 그냥 long 타입 배열로 관리했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(Stri.. 2025. 1. 13. [백준] 2470번 - 두 용액 [Java] https://www.acmicpc.net/problem/2470 1. 아이디어 기존 용액 문제에서 입력 값이 정렬되지 않은 채로 주어지는 문제로 정렬 후 투 포인터 알고리즘으로 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 2467번 - 용액 [Java])2. 문제풀이 기존 방식에서 정렬만 추가하면 해결할 수 있었다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2025. 1. 13. [백준] 2467번 - 용액 [Java] https://www.acmicpc.net/problem/2467 1. 아이디어 투 포인터 알고리즘으로 간단하게 해결할 수 있다.2. 문제풀이 용액을 배열로 입력 받은 후 맨 왼쪽에 포인터 하나, 맨 오른쪽에 포인터 하나를 뒀다.이후 두 포인터가 위치한 용액의 특성값의 합을 구해서 절댓값을 씌웠을 때 현재까지 구한 특성값보다 작으면 정답 용액을 갱신하고 작지 않으면 특성값의 합이 양수면 오른쪽 포인터를 왼쪽으로, 음수면 왼쪽 포인터를 오른쪽으로 이동시켜줬다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Buffer.. 2025. 1. 12. [백준] 27435번 - 파도반 수열 2 [Java] https://www.acmicpc.net/problem/27435 1. 아이디어 파도반 수열 문제에서 N의 범위가 매우 커진 문제로 이전과 달리 거듭제곱의 분할 정복과 점화식의 행렬 변환으로 해결해야 한다.([코딩테스트 준비/백준] - [백준] 9461번 - 파도반 수열 [Java])2. 문제풀이 일단 해당 문제를 풀기 위해서 점화식을 행렬로 표현할 수 있어야 한다.파도반 수열은 a(n) = a(n-2) + a(n-3)의 점화식을 갖는데 이를 다음과 같이 행렬의 거듭제곱으로 표현할 수 있다. $\begin{pmatrix}a_{n}\\ a_{n-1}\\ a_{n-2}\end{pmatrix} =\begin{pmatrix}a_{n-2}+a_{n-3}\\ a_{n-1}\\ a_{n-2}\end{pmatrix.. 2025. 1. 12. 이전 1 ··· 22 23 24 25 26 27 28 ··· 51 다음
