DP12

[BOJ_25418] 정수 a를 k로 만들기 📌 문제 링크: https://www.acmicpc.net/problem/25418 25418번: 정수 a를 k로 만들기 7(A), 8(연산 1), 9(연산 1), 18(연산 2), 19(연산 1), 38(연산 2), 76(연산 2), 77(연산 1)이 최소 연산이므로 정답은 7이다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: dp를 잘하지 못해서 dp 문제를 푸는 것을 좋아하지 않지만, 꾸준한 연습으로 dp 문제도 잘 풀고, dp 문제를 좋아할 수 있으면 좋겠다. 🚩 Idea: dp 배열(리스트)에는 각 원소를 만들기 위한 최소 연산 횟수를 저장한다. 1을 더하거나 2를 곱해서 나온 정수를 인덱스로 하는 배열의 값이 0이라면 연산을 통해 최초로 얻은 값이라는 의미이므.. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 11. 15.

[BOJ_8394] 악수 📌 문제 링크: https://www.acmicpc.net/problem/8394 8394번: 악수 첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다. www.acmicpc.net ❌ 내 풀이(Failure) : ✅ 내 풀이(Success) : 🧐 Review: 점화식을 구하는 것은 어렵지 않았지만, 문제를 통과하기까지 코드를 몇 번이나 수정하였다. 처음 시간 초과로 문제를 틀린 이후에 코드를 수정해서 제출했지만, 계속해서 시간 초과가 발생하였다. 그래도 거의 다 풀었다는 생각에 답안을 확인하기보다 예전에 문제를 풀었을 때의 기억을 되짚어 보며 해결 방법을 생각해 보았다. 고민해 본 결과 이전에 '형변환은 생각보다 시간이 오래 걸린다'라는 글을 블로그에서 본 것 같다.. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 9. 27.

[BOJ_1003] 피보나치 함수 📌 문제 링크: https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 쉬운 dp문제이다. fibonacci(4) 까지만 확인해도 규칙을 쉽게 파악할 수 있다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 10. 18.

[BOJ_1912] 연속합 📌 문제 링크: https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net ✅ 내 풀이(Success) : ✅ 참고용 풀이(Sucess) : 🧐 Review: 평소처럼 문제의 유형을 확인하고 해당 유형에 맞게 풀이를 고민해봤지만 어떻게 이 문제를 dp로 풀어야 할지 감이 오지 않았다. dp 문제를 이제 막 10문제를 풀어본 상태라서 기존에 내가 풀었던 방법인 입력값으로 주어진 수열에서 규칙성을 찾아 점화식을 도출하는 방법은 이 문제에 적용할 수 없기 때문에 점화식을.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 11.

[BOJ_9625] BABBA 📌 문제 링크: https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 버튼을 누르지 않았을 때(dp 배열의 0번째 원소)는 A의 개수는 1이고, 버튼을 한 번 눌렀을 때(dp 배열의 1번째 원소)는 A의 개수는 0이 되고, B의 개수는 1이 된다. 2번째 원소부터 그 이전 두 개의 항의 원소의 값을 더해 A와 B의 개수를 구할 수 있다. 처음에는 'A'와 'B'를 이용해 문자열을 직접 더하고 dp 배열의.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 7.

[BOJ_2193] 이친수 📌 문제 링크: https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 위와 같이 경우의 수를 나열하면서 규칙성을 찾는다. 🚩 Idea: 1. dp문제로 경우의 수를 나열해보면서 규칙성을 찾는다. 2. 규칙성을 이용해 점화식을 세운다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 6.

[BOJ_9095] 1, 2, 3 더하기 📌 문제 링크: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 어제 풀었던 dp 문제가 재미있어서 오늘도 dp 문제를 풀어봤다. 규칙성은 5번째 원소까지 경우의 수를 구하고 이전 항들과의 비교를 통해 찾을 수 있었다. 🚩 Idea: 1. dp문제로 경우의 수를 나열해보면서 규칙성을 찾는다. 2. 규칙성을 이용해 점화식을 세운다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 6.

[BOJ_2579] 계단 오르기 📌 문제 링크: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 처음 문제를 접근했을 때는 모든 경우의 수를 나열해서 규칙성을 찾았다. 여섯 개의 계단을 오르는 경우까지 확인을 해보니 규칙성을 발견했고 점화식을 세울 수 있었다. 문제의 결괏값으로 계단 오르기 게임에서 얻을 수 있는 최고 점수를 반환해야 되는데, 해당 부분은 모든 경우의 수의 점수를 계산하고, 해당 데이터에 max값을 반환해주는 식으로 문제를.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 7. 5.

[BOJ_1793] 타일링 📌 문제 링크: https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: n의 값에 따라 타일의 경우의 수를 체크하는데 n=5일 때 경우의 수를 잘못 구해서 점화식을 잘못 작성하게 되었고, 그래서 몇 번 틀렸던 문제이다. DP 문제를 풀 때는 보다 세심하게 경우의 수를 확인하도록 연습해야겠다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 6. 17.

[프로그래머스] 2 x n 타일링 📌 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/12900 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✅ 내 풀이(Sucess) : 🧐 Review: 백준에서 이 문제와 완전히 똑같은 문제를 푼 적이 있어서 이 문제를 해결하는 것이 어렵지 않았다. 차이점이 있다면 백준에 있는 문제는 n의 범위가 최대 1,000이라 결괏값을 리턴할 때 % 연산을 해도 시간 초과가 발생하지 않지만, 프로그래머스의 이 문제는 n의 범위가 최대 60,000이라서 결괏값을 반환할 때 % 연산을 한다면 시간 초과가 발생.. 알고리즘 문제 풀이: 파이썬/Programmers 2022. 6. 17.

이전 1 2 다음

티스토리툴바