Algorithm

✨ 알고리즘 분류 : 다이나믹 프로그래 https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net   🪡 문제에서 요구하는 조건 정리 - 연속합은 연속하는 수열들의 합이다- 연속합 중 제일 큰 값을 출력   🧶 풀이과정  이 문제는 간단하게 정리가 가능하다.1 2 3 4 5 의 위치가 있고 현재 3의 위치에서 바라봤을 때 이전까지의 합 + 현재 위치의 수를 더한 것과 현재 위치의 수를 비교하고, 둘 중 높은 값을 누적해나가면 된다. 라고 써도 조금 헷갈릴 수 있으므..

✨ 알고리즘 분류 : 다이나믹 프로그래밍 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net  🪡 문제에서 요구하는 조건 정리 - 증가하는 부분 수열을 구하고, 가장 긴 값을 가져온다- 가장 긴 값과 함께 수열에 들어있는 값도 출력한다.   🧶 풀이과정  이 문제는 이전의 문제를 참고하고 있기 때문에 이전 문제를 참고하여 풀 수 있다.2024.04.25 - [Algo..

✨ 알고리즘 분류 : 다이나믹 프로그래밍 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net    🪡 문제에서 요구하는 조건 정리 - 수열 중 증가하는 수열을 찾기- 증가하는 수열 중 가장 긴 값 찾기   🧶 풀이과정  언제나 dp는 점화식 찾기 50분 풀이 10분 도합 60분이라는 극악의 시나리오를 만들어버린다. 이번에도 그랬다 ㅎㅎ;우선 그려서 생각하면 다음과 같다 ..

✨ 알고리즘 분류 : 다이나믹프로그래밍 https://www.acmicpc.net/problem/2193 2193번: 이친수0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않www.acmicpc.net    🪡 문제에서 요구하는 조건 정리 - 이친수는 0으로 시작하지 않으면서, 11이 들어가지 않는 이진수이다.- 이진수의 개수를 출력  🧶 풀이과정  내가 이진법을 잘 모르는 탓에 그려가면서 풀이를 진행했다.  적은 것을 토대로 봤을 때, 6자리의 이친수일 경우4자리수에 01을, 5자리수에 0을..

✨ 알고리즘 분류 : 다이나믹 프로그래밍 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - 계단은 인접한 자리의 수의 차이가 모두 1인 수이다. - 0으로 시작하는 수는 계단 수가 아니다. - 길이가 n인 수 중 계단 수는 모두 몇 개인지 구하라 🧶 풀이과정 계단 수는 인접한 모든 자리의 수 차이가 1인 수라고 하면, 이걸 어떻게 구할 수 있을까? 이럴 때는 우선 그려보자. 여기까지만 봐도 알겠지만 1. 마지막 자리가 0일 경우 이전 자릿수는 무조건 1이어야 한다. (10, 210, 3210 등등등등) 2. 마지막 자리가 9..

✨ 알고리즘 분류 : 다이나믹 프로그래밍 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - 1, 2, 3을 이용하여 합으로 나타내는 방법의 총 합을 계산 - 같은 수가 두번 이상 반복되면 안 됨 🧶 풀이과정 1,2,3 더하기의 응용 버전이다 2024.04.12 - [Algorithm] - [058] 9095. 1,2,3 더하기 [058] 9095. 1,2,3 더하기 ✨ 알고리즘 분류 : 다이나믹 프로그래밍 https://www.acmicpc.net/problem..

✨ 알고리즘 분류 : 다이나믹프로그래밍 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - 카드를 사기 위해 지불해야 하는 금액 중 제일 적은 값 출력 - 카드 개수의 합 = n 🧶 풀이과정 저번에 최대값을 구하는 것의 반대로, 최솟값을 구하는 것이다. 2024.04.16 - [Algorithm] - [059] 11052. 카드 구매하기 [059] 11052. 카드 구매하기 ✨ 알고리즘 분류 : 다이나믹 프로그래밍 ..

✨ 알고리즘 분류 : 다이나믹 프로그래밍 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - 구매하고자 하는 양에 맞는 금액의 최댓값을 구하기 - 카드팩 n개는 1씩 오름형태 - 적거나 넘치면 안 됨 🧶 풀이과정 최댓값을 구하는 건 또 오랜만이라 잠깐 헤메는 시간을 가졌다. 결국, 최솟값과 같이 전까지의 결과물과 비교하여 높은 것을 넣으면 되는데, min이 아니라 max값을 담는 것과 같다고 생각하면 된다. 그러니까 카..

✨ 알고리즘 분류 : 다이나믹 프로그래밍 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하기 - 합을 나타낼 때에는 수를 1개 이상 사용해야 한다. 🧶 풀이과정 쉬운 dp 문제인데, 역시 나는 숫자를 써가면서 정리했다. 1 ) 1 2) 1+1 , 2 3) 1+1+1, 1+2, 2+1, 3 여기서 보면 대에충 감이 오는데, 0을 1이라고 할 경우에(왜냐면 1, 2, 3은 0+각각의 수) 2는 1에 1을 더하고, 0에 2를 더하는 2개. 3은 1에 + 2,..