deulee의 개발 노트

문제 바이토닉 수열이란 다음의 조건을 만족하는 모든 수열을 의미한다. 수열 S가 어떤 수 S[k]를 기준으로 S[1] S[k + 1] > ... S[N - 1] > S[N] 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하라. 입력 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ A[i] ≤ 1000) 예제 입력 10 1 5 2 1 4 3 4 5 2 1 예제 출력 7 문제 해결 어디서 힌트를 얻을 수 있을까? 가장 긴 바이토닉 부분 수열을 한번 잘 확인할 필요가 있다. 바이토닉 수열이란 결국 어떻게 보면 가장 긴 증가하..

알고리즘/문제 2023. 6. 24. 16:42

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성한다. 예시) A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 숫자들이 주어진다. 예제 입력 6 10 20 10 30 20 50 예제 출력 4 문제 해결 어디서 힌트를 얻을 수 있을까? 우선 '가장 긴'이라는 단어를 보고 이 문제는 최대 값을 구하는 문제라는 것을 알 수 있다. 이 문제를 쉽게 풀 수 없을까? 라는 생각을 해봤고 우선 브루트포스로 문제를 풀어보는 것을 생각해 보았다. 이 문제를 간단하게 브루트포스 알고리즘으로 구현하게 된다면 각 인덱스에서 시작해 가장 긴 증가하는 부분 ..

알고리즘/문제 2023. 6. 24. 15:35

문제 2•N의 배열이 주어진다. 이 배열의 요소 안에는 각각의 값어치를 나타내는 값이 주어진다. 이때, 한 요소와 변을 공유하는 요소는 사용하지 못할 때 사용할 수 있는 요소를 이용하여 최대 값을 구하는 문제이다. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유하지 않는 스티커의 집합을 구하는 문제이다. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 두 줄에는 N개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 예제 입력 2 5 50 10 100 20 40 30 50 70 10 60 7 10 30 10 50 100 20 40 20 40 30 50 60 20 80 예제..

알고리즘/문제 2023. 6. 6. 18:44

문제 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 즉 LCS(Longest Common Subsequence, 최장 공통부분 수열)을 찾아라. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 최대 1000글자로 이루어져 있다. 예제 입력 ACAYKP CAPCAK 예제 출력 4 문제 해결 어디서 힌트를 얻을 수 있을까? 이 문제를 하나하나 비교하면서 문제를 풀게 되면 제한 시간을 초과하게 된다. 즉, 이 문제는 중복적으로 비교하는 것이 너무 많다는 것인데 이를 해결하기 위해 다이나믹 프로그래밍을 사용해야 한다. 하지만 이를 어떻게 적용해야 할 지 감이 안잡히던 중 예제 답을 하나하나 만들어 보기로 했다. 우선 다음의 표를 보도록 하자. 0 A C A Y K P 0 0 0 0 0 0 0 0 C ..

알고리즘/문제 2023. 6. 5. 00:47

문제 nCm을 출력해라. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤100, m ≤ n) 예제 입력 100 6 예제 출력 1192052400 문제 해결 어디서 힌트를 얻을 수 있을까? 'nCm'과 '조합'이라는 키워드를 보았을 때 나는 이항 계수를 떠올렸다. 그리고 수많은 반복되는 중복 문제를 고려하여 다이나믹 프로그래밍도 적용도 생각했다. 그리고 최대 범위의 조합의 수를 고려하면 커다란 범위의 수를 어떻게 처리해야 할 지도 고안해야 했다. 우선 하나하나 해결해보도록 해보자. 우선 이항 계수를 삼각형으로 표현한 파스칼의 삼각형의 점화식을 보도록 하겠다. 위의 점화식에 따라 커다란 틀을 구현할 수 있겠다. 그리고 메모이제이션은 다음과 같이 할 수 있다. (N, M)쌍에 값이 이미 갱신..

알고리즘/문제 2023. 5. 26. 00:29

문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 먼저 첫 줄에 적혀 있는 세 개의 숫자 중에서 하나를 골라 다음 줄로 차례대로 내려간다. 이때 다음의 조건이 있다. 파란 원은 갈 수 있는 공간이고 빨간 X는 갈 수 없는 공간이다. 이렇게 해서 최대 합과 최소 합을 구하는 문제이다. 입력 첫째 줄에 N이 입력된다. (1 N; int x, y, z; for (int i = 0; i > x; dist1[i] = x; dist2[i] = x; } int temp0 = 0, temp2 = 0; for (int i = 1; i > x >> y >> z; temp0 = dist1[0]; te..

알고리즘/문제 2023. 5. 24. 23:55

문제 삼각형이 주어지고 위에서 아래로 내려오는데, 이때 그냥 내려오거나 오른쪽 대각선으로 내려가야만 한다. 이런 상황에서 합이 최대가 되는 경로에 있는 수의 합을 출력해라. 입력 첫째 줄에 삼각형의 크기 n(1 > N; for (int i = 0; i > board[i][j]; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cache[i][j] = -1; } } std::cout

알고리즘/문제 2023. 5. 24. 17:56