다이나믹 프로그래밍72 [SWEA] 2005번 - 파스칼의 삼각형 [Java] https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5P0-h6Ak4DFAUq 1. 아이디어 2차원 배열로 파스칼의 삼각형을 표현했을 때 위의 두 원소의 합이 아래 원소가 되는 다이나믹 프로그래밍으로 해결했다.2. 문제풀이 위쪽과 왼쪽에 패딩을 준 후 0행 0열을 1로 초기화하면 점화식으로 파스칼의 삼각형을 구할 수 있었다. 이후 순회를 하며 0에서 갱신이 안됐으면 순회를 종료하는 방식으로 출력했다.3. 코드 import java.io.*;public class Solution { public static void main(String[] args) throws IOException {// Buf.. 2025. 2. 13. [프로그래머스] 12900번 - 2 x n 타일링 [Java] https://school.programmers.co.kr/learn/courses/30/lessons/12900 문제 설명가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.타일을 가로로 배치 하는 경우타일을 세로로 배치 하는 경우예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한사항가로의 길이 n은 60,000이하의 자연수 입니다.경우의 수가 많아 질 수 있으므로, 경우의.. 2025. 2. 10. [소프티어] 6257번 - 통근버스 출발 순서 검증하기 [Java] https://softeer.ai/practice/6257 1. 아이디어 (a, b, c)가 스택 정렬이 불가능한 경우는 a, b, c에서 나올 수 있는 6가지 경우의 수 중 a c 인 경우 하나 뿐이다. N이 최대 5000까지여서 3중 for문을 활용한 간단한 구현은 시간 초과가 발생하는데 이를 해결하기 위해 다이나믹 프로그래밍을 활용해 O(N^2)으로 구현했다.2. 문제풀이 스택 정렬이 불가능한 조합을 찾기 위해 dp 테이블을 활용했다. dp 테이블에는 주어진 수 i, j에 대해 i보다 큰 j를 발견했을 때 j 이후로 등장하는 i보다 작은 수의 개수를 저장했다. 이를 위해 열 인덱스를 역순으로 순회하며 바로 이전 값을 채워준 후 i > j면 +1을 해주도록 했다.이후 다시 2중 for문을 순회하며.. 2025. 2. 7. [백준] 14267번 - 회사 문화 1 [Java] https://www.acmicpc.net/problem/14267 1. 아이디어 각 칭찬마다 직원들의 칭찬 수치를 갱신하면 시간 초과가 발생한다. 각 직원마다 최초로 칭찬을 받은 경우 칭찬 수치를 더한 후 한번에 계산하는 방식으로 해결할 수 있다.2. 문제풀이 Bottom-Up 다이나믹 프로그래밍과 DFS 알고리즘으로 해결이 가능했는데 다이나믹 프로그래밍은 주어진 직속상사 정보를 바로 활용해서 현재 직원의 칭찬 수치는 현재 직원이 최초로 받은 칭찬 수치의 합과 현재 직원의 부모 직원이 받은 칭찬 수치이다. 상사의 번호가 직원의 번호보다 항상 작아서 해당 방식으로 해결할 수 있었다. DFS는 그냥 사장부터 탐색하며 파라미터로 칭찬 수치의 합을 들고 다니면 간단하게 해결할 수 있다.3. 코드 packag.. 2025. 2. 6. [백준] 11051번 - 이항 계수 2 [Java] https://www.acmicpc.net/problem/11051 1. 아이디어 이전 이항 계수 문제에서 수의 범위가 커진 문제로 단순한 재귀 대신 다이나믹 프로그래밍을 활용해서 해결할 수 있다.2. 문제풀이 Top-Down, Bottom-Up 두 가지 방식으로 구현했는데 Top-Down 방식은 기존의 재귀 함수에서 행을 N, 열을 K로 하는 2차원 dp 테이블을 설정해서 dp 테이블에 값이 있으면 바로 반환하고 기존의 반환값도 dp 테이블에 저장하는 방식으로 구현했다. Bottom-Up 방식은 똑같은 dp 테이블에서 조합 점화식을 적용해 반복문으로 구하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_TopDown_DP .. 2025. 2. 3. [백준] 2637번 - 장난감 조립 [Java] https://www.acmicpc.net/problem/2637 1. 아이디어 번호와 개수를 갖는 노드를 활용한 위상 정렬과 다이나믹 프로그래밍으로 해결할 수 있었다.2. 문제풀이 장난감의 개수를 간선의 가중치로 생각하는 방향 비순환 그래프에서 위상 정렬로 구현했다. 위상 정렬 과정에서는 카운팅 배열에 장난감 부품의 개수를 저장했는데 노드를 정렬할 때마다 후행 작업에 선행 작업의 개수를 전달하면 부품 수를 전달할 수 있다. 이후 진출차수 배열에서 0인 노드가 기본 부품임을 이용해서 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node { int v; .. 2025. 2. 3. [백준] 2056번 - 작업 [Java] https://www.acmicpc.net/problem/2056 1. 아이디어 위상 정렬과 작업 시간을 저장하는 다이나믹 프로그래밍을 활용하면 해결할 수 있다.2. 문제풀이 위상 정렬 과정에서 선행 작업이 없는 경우 해당 작업 시간을 선행 작업이 있는 경우 선행 작업을 하는데 걸리는 총 시간과 해당 작업을 하는데 걸리는 시간의 합과 현재까지 구한 해당 작업을 하는데 걸리는 총 시간 중 더 큰 값이 해당 작업을 하는데 걸리는 총 시간이 된다. 이를 통해 모든 작업이 각각 완료되는데 걸리는 총 시간을 배열로 구할 수 있었고 이 중 가장 큰 값이 모든 작업을 완료하는데 걸리는 총 시간이 됐다. N번 작업보다 번호가 작은 작업이 더 오래걸릴 수 있음에 주의해야한다.3. 코드 import java.io.*;i.. 2025. 2. 3. [백준] 1516번 - 게임 개발 [Java] https://www.acmicpc.net/problem/1516 1. 아이디어 위상 정렬과 건설 시간을 저장하는 다이나믹 프로그래밍을 활용하면 해결할 수 있다.2. 문제풀이 이전 ACM Craft 문제와 유사한 문제로 동일하게 접근했다.([코딩테스트 준비/백준] - [백준] 1005번 - ACM Craft [Java]) 각 건물의 건설 시간은 dist 배열에 저장했는데 dist 배열은 선행 건물이 없는 건물은 해당 건물의 건설시간으로 초기화하면 되고 선행 건물이 있는 경우 (선행 건물을 건설하는데 걸리는 총 시간 + 해당 건물을 건설하는데 걸리는 시간)과 현재까지 계산된 해당 건물을 건설하는데 걸리는 총 시간 중 큰 값이 해당 건물을 건설하는데 걸리는 총 시간이 된다.3. 코드 import java... 2025. 2. 3. [백준] 1005번 - ACM Craft [Java] https://www.acmicpc.net/problem/1005 1. 아이디어 위상 정렬과 건설 시간을 저장하는 다이나믹 프로그래밍을 활용하면 해결할 수 있다.2. 문제풀이 그림에서 위상 정렬의 힌트를 얻을 수 있어서 위상 정렬로 접근했다. 각 건물의 건설 시간은 dist 배열에 저장했는데 dist 배열은 선행 건물이 없는 건물은 해당 건물의 건설시간으로 초기화하면 되고 선행 건물이 있는 경우 (선행 건물을 건설하는데 걸리는 총 시간 + 해당 건물을 건설하는데 걸리는 시간)과 현재까지 계산된 해당 건물을 건설하는데 걸리는 총 시간 중 큰 값이 해당 건물을 건설하는데 걸리는 총 시간이 된다.3. 코드 import java.io.*;import java.util.*;public class Main { .. 2025. 2. 2. [백준] 15624번 - 피보나치 수 7 [Java] https://www.acmicpc.net/problem/15624 1. 아이디어 이전 피보나치 수 문제에서 수의 크기가 커지고 나머지 출력 조건이 생긴 문제로 모듈러 연산은 중간에 실행해도 결과가 동일한 점을 활용해 dp 계산 과정에서 나머지만 저장하면 된다.([코딩테스트 준비/백준] - [백준] 10870번 - 피보나치 수 5 [Java])2. 문제풀이 아이디어 그대로 구현했다.3. 코드 import java.io.*;public class Main { private static final int MOD = 1_000_000_007; public static void main(String[] args) throws IOException { BufferedReader br = .. 2025. 2. 2. [백준] 10826번 - 피보나치 수 4 [Java] https://www.acmicpc.net/problem/10826 1. 아이디어 이전 피보나치 수 문제에서 N이 최대 10000인 문제로 long 타입의 범위도 넘어간다. 이를 처리하기 위해 큰 수의 연산을 간단하게 할 수 있는 BigInteger 클래스를 활용해서 구현했다.2. 문제풀이 BigInteger 타입 배열을 이용한 다이나믹 프로그래밍으로 해결했고 add 메서드로 덧셈을 수행했다.3. 코드 import java.io.*;import java.math.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new .. 2025. 2. 1. [백준] 10870번 - 피보나치 수 5 [Java] https://www.acmicpc.net/problem/10870 1. 아이디어 이전 피보나치 수 문제에서 N이 0인 경우가 추가된 문제로 역시 다이나믹 프로그래밍을 활용하면 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 2747번 - 피보나치 수 [Java])2. 문제풀이 N이 0일 때 배열을 활용한 다이나믹 프로그래밍은 인덱스 문제가 발생할 수 있는데 N이 최대 20이어서 그냥 20번째 피보나치 수까지 전부 계산 후 출력해도 되지만 N이 0일 때를 예외처리하는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { B.. 2025. 2. 1. 이전 1 2 3 4 5 6 다음
