1) 문제https://www.acmicpc.net/problem/1351 2) 해결이 문제는 메모이제이션을 활용한 동적 계획법(DP, Dynamic Programming) 을 사용하여 해결할 수 있습니다.기본적인 아이디어는 재귀(Recursion) + 메모이제이션(Memoization) 을 사용하는 것입니다.문제 풀이 접근기본 점화식 정의A[i] = A[i/P] + A[i/Q] (단, A[0] = 1)이 점화식을 그대로 재귀적으로 구현하면 중복 계산이 발생하여 시간 초과가 발생할 가능성이 높습니다.메모이제이션을 활용한 최적화중복 계산을 방지하기 위해 해시맵(HashMap) 자료구조를 사용한 메모이제이션을 활용합니다.이미 계산된 값을 저장하여 불필요한 연산을 줄입니다.입력 범위 고려N의 최대 값이 10¹..
coding_test
1) 문제https://www.acmicpc.net/problem/2225 2) 풀이코드 설명입력 받기: N과 K를 입력으로 받습니다.DP 배열 초기화: dp[i][j]는 i개의 수로 합이 j가 되는 경우의 수를 저장하는 배열입니다. 이 배열을 K + 1과 N + 1 크기로 생성합니다.초기 조건: dp[0][0] = 1로 설정합니다. 이는 0개를 사용해서 합이 0이 되는 방법은 1가지라는 의미입니다.DP 테이블 채우기:i가 1부터 K까지 반복됩니다. 즉, i개를 사용해서 합을 만들 때를 고려합니다.j가 0부터 N까지 반복됩니다. 즉, 합이 j일 때를 고려합니다.k는 0부터 j까지 반복되며, dp[i][j]는 dp[i-1][j-k]를 더하는 방식으로 점차 채워집니다. 이 과정에서 k는 한 번에 더할 수 있..
1) 문제https://www.acmicpc.net/problem/9251 2) 해결코드 해석입력 처리:Scanner를 사용하여 두 개의 문자열을 입력받음DP 테이블 초기화:dp[i][j]는 str1[0...i-1]과 str2[0...j-1]의 LCS 길이를 저장함따라서 dp 배열의 크기는 (len1+1) x (len2+1)로 설정함DP 점화식 적용:두 문자열의 각 문자를 비교하면서 LCS를 구함str1[i-1] == str2[j-1]이면, dp[i][j] = dp[i-1][j-1] + 1다르면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])결과 출력:dp[len1][len2]에 LCS의 길이가 저장되므로 이를 출력함이 코드는 시간 복잡도가 O(N×M)O(N \times M)O(N..
1) 문제https://www.acmicpc.net/problem/11053 2) 해결법이 문제는 Longest Increasing Subsequence (LIS, 최장 증가 부분 수열) 문제로,동적 계획법(DP) 을 사용하여 해결 가능문제 풀이 방법DP 배열 정의:dp[i] : i번째 원소를 마지막 원소로 하는 가장 긴 증가하는 부분 수열의 길이를 저장점화식 유도:dp[i] = max(dp[j]) + 1 (0 ≤ j 즉, 현재 값 A[i]보다 작은 A[j]를 찾고, 그 dp[j] 값 중 최대값을 찾아 1을 더함초기값 설정:모든 dp[i] 값을 1로 초기화 (각 원소는 최소한 자기 자신만으로 길이 1의 부분 수열이 됨).최댓값 찾기:dp 배열에서 가장 큰 값을 출력import java.util.*;pub..
1) 문제https://www.acmicpc.net/problem/1003 2) 풀이코드 설명:DP 테이블 (dp[41][2]) 사용dp[i][0] : fibonacci(i)를 호출했을 때 0이 출력된 횟수dp[i][1] : fibonacci(i)를 호출했을 때 1이 출력된 횟수fibonacciPrecompute() 함수로 DP 테이블 채우기dp[0]과 dp[1]을 초기값으로 설정dp[i]는 dp[i-1]과 dp[i-2] 값을 이용해 채움입력 처리 및 출력 최적화여러 테스트 케이스가 주어지므로 StringBuilder를 이용하여 최적화import java.io.*;public class Main { static int[][] dp = new int[41][2]; // 0과 1의 출력 횟수를 저장하..
1) 문제https://www.acmicpc.net/problem/195982) 풀이해석 및 코드 설명입력 처리 및 이벤트 정렬입력으로 받은 (start, end)를 각각 (start, 1), (end, -1)로 변환하여 리스트에 저장합니다.정렬 기준:시간이 다르면 시간 순 정렬 (오름차순)시간이 같으면 종료(-1)를 먼저 정렬→ 종료를 먼저 처리해야 동일한 시간에 종료 후 시작하는 경우를 올바르게 처리할 수 있습니다.스위핑(Sweep) 알고리즘currentRooms(현재 사용 중인 회의실 수) 변수 사용이벤트 리스트를 순회하면서 currentRooms를 업데이트최대 회의실 개수를 maxRooms에 저장최종 결과 출력maxRooms를 출력하면 최소 회의실 개수가 됩니다.시간 복잡도 분석정렬: O(N lo..
1) 문제https://www.acmicpc.net/problem/1946 2) 풀이접근 방식서류심사 성적 기준으로 정렬서류심사 성적을 기준으로 오름차순 정렬합니다.그러면 앞에서부터 탐색할 때, 이전에 확인한 지원자보다 서류 성적이 낮은 경우만 확인하면 됩니다.면접 성적 비교첫 번째 지원자의 면접 성적을 기준으로 설정합니다.이후 지원자들의 면접 성적을 비교하면서, 현재까지의 최고 성적보다 낮은 경우 탈락 처리합니다.면접 성적이 더 높다면 해당 지원자를 선발하고, 최고 면접 성적을 업데이트합니다.결과 출력각 테스트 케이스별로 선발할 수 있는 최대 인원을 출력합니다.import java.io.*;import java.util.*;public class Main { public static void m..
1) 문제https://www.acmicpc.net/problem/17503 2) 풀이코드 해석입력 받기 (BufferedReader 활용)N, M, K 값을 읽고, Beer 객체 배열을 생성하여 K개의 맥주 정보를 저장합니다.정렬 (도수 레벨 기준 오름차순)Arrays.sort(beers, Comparator.comparingInt(b -> b.alcoholLevel));도수가 낮은 맥주부터 선택할 수 있도록 정렬합니다.우선순위 큐 (PriorityQueue) 사용PriorityQueue minHeap = new PriorityQueue();최소 힙을 사용하여 현재 선택한 N개 맥주 중 선호도가 가장 낮은 것을 제거합니다.맥주 선택 및 조건 충족 확인하나씩 minHeap에 추가하면서 선호도 합을 누적 ..
