deulee의 개발 노트

문제 수열 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

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

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

문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 문제이다. 전위 순회 : (루트)(왼쪽 자식)(오른쪽 자식) 중위 순회 : (왼쪽 자식)(루트)(오른쪽 자식) 후위 순회 : (왼쪽 자식)(오른쪽 자식)(루트) 입력 첫째 줄에 이진 트리의 노드의 개수 N이 주어진다. (1 = 0) preOrder(varr[S][1]); } void inOrder(int S) { if (varr[S][0] >= 0) inOrder(varr[S][0]); std::cout = 0) inOrder(varr[S][1]); } void postOrder(int S) { if (varr[S][0..

알고리즘/문제 2023. 5. 24. 21:10

문제 삼각형이 주어지고 위에서 아래로 내려오는데, 이때 그냥 내려오거나 오른쪽 대각선으로 내려가야만 한다. 이런 상황에서 합이 최대가 되는 경로에 있는 수의 합을 출력해라. 입력 첫째 줄에 삼각형의 크기 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