본문 바로가기

Algorithm

(130)
[C++] 백준 11053번 : 가장 긴 증가하는 부분 수열 (S2) #문제 www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net #풀이 & 학습한 내용 시간복잡도를 O(N)으로 구현하려 시도했지만 실패하고 O(N^2)로 구현했다. dp배열에 그 위치를 수열의 마지막으로 갖는 최대 증가하는 부분 수열의 길이를 저장했다. j가 1부터 i까지 움직이며 p[j]dp[i] 조건이 만족되면 갱신되도록 for문을 구성했다. 그리고 문제에서 구하는 최댓값은 dp배열의..
[C++] 백준 2193번 : 이친수 (S3) #문제 www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net #풀이 & 학습한 내용 이번 문제에서 dp배열을 int로 선언하면 "틀렸습니다"가 나온다. long long으로 dp배열을 선언하여 문제를 해결했다. 마지막에 나올 수 있는 수는 0또는 1이고 2차원 배열을 통해 N자리 이친수의 마지막 수가 0인 경우는 dp[N][0]에, 1인 경우는 dp[N][1]에 경우의 수를 저장했다. 그리고 마지막 수가 0인 경우는 바로 앞에 0,1 모두 올 수 있고,..
[C++] 백준 10844번 : 쉬운 계단 수 (S1) #문제 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 int형 범위를 항상 조심하자. int 최대는 대략 2,000,000,000이다(0 3개가 3번). 마지막에 sum을 더할 때도 int의 범위를 넘을 수 있으므로 long long으로 선언해줘야 한다. 이때 백준에서 "틀렸습니다"로 나오기 때문에 헤맬 수 있으므로 조심하자. 모듈로 연산의 성질 (A + B)%C = (A%C + B%C)%C도 항상 생각하자. 문제를 분석할 때 특수한 케이스가 0과 9임을 파악할 수 있다. 마지막에 오는 수에 대해 그 수에 맞는 index에 경우의 수를 저장해 문제..
[C++] 백준 15990번 : 1, 2, 3 더하기 5 (S3) #문제 www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 중복이 안 되게 해야 하므로 마지막이 어떤 수인지에 대해 구분을 하여 경우의 수를 저장해주어야 한다. 2차원 배열을 선언하여 마지막에 더해지는 수 1, 2, 3에 대해 그 인덱스에 맞는 곳에 경우의 수를 저장한다. 인덱스를 0부터 해도 되지만 마침 마지막에 더해지는 수가 1 ,2, 3이므로 편하게 인덱스 또한 1,2,3일 때에 해당되도록 해서 헷갈리는 일이 없게 했다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13..
[C++] 백준 11052번 : 카드 구매하기 (S1) & 16194번 : 카드 구매하기 2 (S1) #문제 www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net #풀이 & 학습한 내용 마지막에 뽑는게 몇 장짜리 팩인지에 대해 접근했다. 직접 예시를 손으로 써가며 dp에 활용할 수..
[C++] 백준 15988번 : 1, 2, 3 더하기 3 (S2) #문제 www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 int 범위의 최대는 2,147,483,647이다. 대략 2,000,000,000으로 기억해두자. 문제에서 dp배열을 int로 선언하면, dp[i - 1] + dp[i - 2] + dp[i - 3]을 계산할 때, int범위의 최댓값을 벗어날 수 있다. 따라서 dp배열을 long long으로 선언해야 한다. 모듈로 연산의 성질인 (A + B)%C = (A%C + B%C)%C도 기억해두자. 이때, (A%C + B)%C도 가능하다는 점도..
[C++] 백준 9095번 : 1, 2, 3 더하기 (S3) #문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 마지막에 올 수 있는 수는 1,2,3 중 하나이다. 그리고 마지막 수를 빼면 같은 문제로 문제의 크기만 n-1, n-2, n-3이 되므로 dp를 이용한다. 이때 dp배열의 초깃값으로 dp[1]=1, dp[2]=2, dp[3]=4를 넣어주고 반복문으로 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]을 통해 dp[10]까지 계산한다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #inclu..
[C++] 백준 11727번 : 2×n 타일링 2(S3) #문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net #풀이 & 학습한 내용 기존 2×n 타일링 문제에서 마지막에 올 수 있는 경우가 하나 추가된 문제이다. 타일의 마지막은 2x1타일 하나, 1X2타일 2개, 2X2타일 1개가 가능하다. 각각에 따른 문제는 같은 문제로 사이즈만 n-1, n-2, n-2일때와 같다. dp배열의 초기값으로 n=1일 때 1, n=2일 때 3을 넣어줬다. 그리고 dp[i] = (dp[i - 1] + 2 * dp[i - 2])를 통해 for문으로 순차적으로 dp..