dynamic programming
-
🔗문제 보러가기 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 🧑💻풀이 과정 동적 계획법(Dynamic Programming)과 위상 정렬(Topological Sort)를 사용해 풀 수 있습니다. 진입 차수가 0인 노드(v)에서 다른 인접 노드(other)로 향할 때, 다음 로직만 추가해주면 됩니다. *constructionTimes[i] : i 번째 건물의 건설 시간 *answers[i] : 먼저 지어야 하는 건물을 짓고 난 후, i 번째 건물까지 짓는 데 걸리는 최소 시간 answers[o..
[BOJ] 1516번 | 게임 개발 (C++)🔗문제 보러가기 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 🧑💻풀이 과정 동적 계획법(Dynamic Programming)과 위상 정렬(Topological Sort)를 사용해 풀 수 있습니다. 진입 차수가 0인 노드(v)에서 다른 인접 노드(other)로 향할 때, 다음 로직만 추가해주면 됩니다. *constructionTimes[i] : i 번째 건물의 건설 시간 *answers[i] : 먼저 지어야 하는 건물을 짓고 난 후, i 번째 건물까지 짓는 데 걸리는 최소 시간 answers[o..
2023.12.19 -
🔗문제 보러가기 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🧑🏻💻풀이 과정 N자리 숫자에서 일의 자리가 0 ~ 9로 끝나는 계단 수들의 개수를 알아봅시다. 먼저, \( N = 1\)일 때는 다음과 같습니다. [ N = 1 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9 0 1 1 1 1 1 1 1 1 1 [ N = 2 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9 1 1 2 2 2 2 2 2 2 1 [ N = 3 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i..
[BOJ] 10844번 | 쉬운 계단 수 (C++)🔗문제 보러가기 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🧑🏻💻풀이 과정 N자리 숫자에서 일의 자리가 0 ~ 9로 끝나는 계단 수들의 개수를 알아봅시다. 먼저, \( N = 1\)일 때는 다음과 같습니다. [ N = 1 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9 0 1 1 1 1 1 1 1 1 1 [ N = 2 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9 1 1 2 2 2 2 2 2 2 1 [ N = 3 일 때 ] i = 0 i = 1 i = 2 i = 3 i = 4 i..
2023.08.26 -
🔗문제 보러가기 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 🧑🏻💻풀이 과정 Dynamic Programming 문제입니다. \( n = 1\), \( n = 2\), ... 일 때의 경우의 수를 한 번 점검해보면, 패턴이 보이는 것을 알 수 있습니다. /* - 어떤 한 행에 있어서 가질 수 있는 경우의 수는 다음과 같은 3가지 [][], [o][], [][o] */ [][][o][][][o] n = 1 : 1 1 1 n = 2 : 3 2 2 n = 3 : 7 5 5 n = 4 : 17 12 12 ... [ ][ ]의 경우의 수는 n - 1번째의 [ ][ ] + [o][ ] + [ ][o] 값입니다. [o][ ]과 [ ][o]의 경우의 ..
[BOJ] 1309번 | 동물원 (C++)🔗문제 보러가기 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 🧑🏻💻풀이 과정 Dynamic Programming 문제입니다. \( n = 1\), \( n = 2\), ... 일 때의 경우의 수를 한 번 점검해보면, 패턴이 보이는 것을 알 수 있습니다. /* - 어떤 한 행에 있어서 가질 수 있는 경우의 수는 다음과 같은 3가지 [][], [o][], [][o] */ [][][o][][][o] n = 1 : 1 1 1 n = 2 : 3 2 2 n = 3 : 7 5 5 n = 4 : 17 12 12 ... [ ][ ]의 경우의 수는 n - 1번째의 [ ][ ] + [o][ ] + [ ][o] 값입니다. [o][ ]과 [ ][o]의 경우의 ..
2023.08.24 -
🔗문제 보러가기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 🧑🏻💻풀이 과정 DP(Dynamic Programming)로 풀 수 있습니다. 알고리즘은 다음과 같습니다. 1. (0, 0)부터 시작하여 0행과 0열에 대해 누적합을 저장해 나가며, 초기화를 해줍니다. 예제 입력 1번을 예로 들면 다음과 같이 합니다. // 원본 입력 데이터 1 2 3 4 0 0 0 5 9 8 7 6 // 누적합 적용 후 1 3(2+1) 6(3+3) 10(6+4) 1 (0+1) 0 0 5 10(9+1) 8 7 6 2..
[BOJ] 11048번 | 이동하기 (C++)🔗문제 보러가기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 🧑🏻💻풀이 과정 DP(Dynamic Programming)로 풀 수 있습니다. 알고리즘은 다음과 같습니다. 1. (0, 0)부터 시작하여 0행과 0열에 대해 누적합을 저장해 나가며, 초기화를 해줍니다. 예제 입력 1번을 예로 들면 다음과 같이 합니다. // 원본 입력 데이터 1 2 3 4 0 0 0 5 9 8 7 6 // 누적합 적용 후 1 3(2+1) 6(3+3) 10(6+4) 1 (0+1) 0 0 5 10(9+1) 8 7 6 2..
2023.08.23 -
🔗문제 보러가기 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 🧑🏻💻풀이 과정 피보나치 함수를 호출했을 때, \( n = 0 \) 또는 \( n = 1 \)일 때의 0과 1의 출력 개수를 세야 합니다. (즉, 위 문제에서 주어진 소스 코드에서 if(n == 0)과 if (n==1)에 해당할 경우) 1. Top-down 방식으로 DP 배열을 통해 중복 계산 최소화 방법 시도 (실패) 피보나치 함수를 재귀로 구현했을 때의 문제점이 바로 중복 계산입니다. 중복 계산이 이루어지기에 시간이 터무니없이 많이 걸리는 것이고, 이것을 개선하기 위해 DP 배열을 사용하여 이미 계산된 N이라면 계산하지 않는 것이죠. 하..
[BOJ] 1003번 | 피보나치 함수 (C++)🔗문제 보러가기 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 🧑🏻💻풀이 과정 피보나치 함수를 호출했을 때, \( n = 0 \) 또는 \( n = 1 \)일 때의 0과 1의 출력 개수를 세야 합니다. (즉, 위 문제에서 주어진 소스 코드에서 if(n == 0)과 if (n==1)에 해당할 경우) 1. Top-down 방식으로 DP 배열을 통해 중복 계산 최소화 방법 시도 (실패) 피보나치 함수를 재귀로 구현했을 때의 문제점이 바로 중복 계산입니다. 중복 계산이 이루어지기에 시간이 터무니없이 많이 걸리는 것이고, 이것을 개선하기 위해 DP 배열을 사용하여 이미 계산된 N이라면 계산하지 않는 것이죠. 하..
2023.08.21 -
🔗문제 보러가기 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 🧑🏻💻풀이 과정 \( n = 1\)부터 하나씩 그려보면, 피보나치 수열의 규칙이 생깁니다. \( n = 1\)과 \( n = 2\)를 베이스로 삼아, \( n = 3\)부터는 \( n - 2\)와 \( n - 1\)을 가지고 조합해 나가는 방식이다 보니, 피보나치 수열과 같은 규칙이 생기는 것 같네요. ✏️ 소스 코드 및 결과 #include #include using namespace std; void SetFastIO() { ios::sync_with_stdio(..
[BOJ] 11726번 | 2xn 타일링 (C++)🔗문제 보러가기 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 🧑🏻💻풀이 과정 \( n = 1\)부터 하나씩 그려보면, 피보나치 수열의 규칙이 생깁니다. \( n = 1\)과 \( n = 2\)를 베이스로 삼아, \( n = 3\)부터는 \( n - 2\)와 \( n - 1\)을 가지고 조합해 나가는 방식이다 보니, 피보나치 수열과 같은 규칙이 생기는 것 같네요. ✏️ 소스 코드 및 결과 #include #include using namespace std; void SetFastIO() { ios::sync_with_stdio(..
2023.08.21 -
🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨💻풀이 과정 입력으로 주어지는 배열 크기가 최대 \( 100,000 \times 4 \) 이기 때문에 DFS으로는 시간 초과가 걸릴 것 같더라구요. 유망하지 않은 부분은 가치지기를 하면 시간을 줄일 수 있겠지만, 기준을 어찌해야 할 지 모르겠었습니다. 그리디(Greedy)로도 현재 선택지가 최선의 선택지라는 보장이 없기에 못 사용하구요. 그래서 동적 프로그래밍(Dynamic Programming)을 한 번 사용해 봤습니다. 땅(land)의 첫 행은 dp에 그대로 저장해둔다. 현재 행과 열을..
[Programmers] Lv2. 땅따먹기 | C++🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨💻풀이 과정 입력으로 주어지는 배열 크기가 최대 \( 100,000 \times 4 \) 이기 때문에 DFS으로는 시간 초과가 걸릴 것 같더라구요. 유망하지 않은 부분은 가치지기를 하면 시간을 줄일 수 있겠지만, 기준을 어찌해야 할 지 모르겠었습니다. 그리디(Greedy)로도 현재 선택지가 최선의 선택지라는 보장이 없기에 못 사용하구요. 그래서 동적 프로그래밍(Dynamic Programming)을 한 번 사용해 봤습니다. 땅(land)의 첫 행은 dp에 그대로 저장해둔다. 현재 행과 열을..
2023.06.22 -
🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨💻풀이 전략 입력 데이터 범위가 최대 10만 인 걸 고려하면, 재귀로는 절대 못 구하니 DP(Dynamic Programming)으로 풀었습니다. 1234567로 나눈 나머지를 리턴하라는 걸로 보아, 오버플로우를 조심해야겠다고 생각했구요. ✏️소스 코드 및 결과 #include using namespace std; const int DIVISION = 1234567; int solution(int n) { vector F(n + 1); F[0] = 0; F[1] = 1; for (int i..
[Programmers] Lv2. 피보나치 수 | C++🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨💻풀이 전략 입력 데이터 범위가 최대 10만 인 걸 고려하면, 재귀로는 절대 못 구하니 DP(Dynamic Programming)으로 풀었습니다. 1234567로 나눈 나머지를 리턴하라는 걸로 보아, 오버플로우를 조심해야겠다고 생각했구요. ✏️소스 코드 및 결과 #include using namespace std; const int DIVISION = 1234567; int solution(int n) { vector F(n + 1); F[0] = 0; F[1] = 1; for (int i..
2023.06.12