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

문제 크기가 N•N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하는 것이다. 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 그 다음줄 부터 N개의 줄에 행렬의 각 원소가 주어진다. 예제 입력 2 5 1 2 3 4 예제 출력 69 558 337 406 문제 해결 어디서 힌트를 얻을 수 있을까? '제곱'이라는 키워드에 중점을 둬서 이 문제를 풀어야 한다. 거듭 제곱 문제를 풀 때 제곱의 수를 반으로 줄여서 곱하는 것은 똑같은 결과를 가져다 주는 것을 알 수 있다. N^B = N^(B/2) * N^(B/2) 이렇게 계속 반으로 줄이다 보면 더 이상 줄이지 못하는 기저 사례가 나오게 되고 처리해 주면 된다. 만약 홀수가..

알고리즘/문제 2023. 6. 10. 00:14

문제 문자열이 하나와 폭발 문자열이 하나 주어진다. 문자열에 폭발 문자열이 포함되고 있는 경우, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 이때 폭발 문자열이 남지 않을 때 까지 이를 반복하여 최종적으로 남은 문자열을 출력하는 문제다. 만약 아무런 문자도 남지 않은 경우 "FRULA"를 출력한다. 입력 두 개의 문자열이 차례대로 입력된다. 예제 입력 mirkovC4nizCC44 C4 예제 출력 mirkovniz 문제 해결 어디서 힌트를 얻을 수 있을까? 애초에 이 문제는 문제 설명 자체에서 힌트를 준 것이나 다름이 없다. 폭발 문자열를 만났을 때 해당 문자열은 없애고 새로 만들어진 문자열을 다시 검사하고 또 이를 반복하는 것이기 때문이다. 이를 그대로 ..

알고리즘/문제 2023. 6. 10. 00:07

문제 N-Queen 문제는 크기가 N•N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성해라. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 15) 예제 입력 8 예제 출력 92 문제 해결 어디서 힌트를 얻을 수 있을까? '퀸', '서로 공격할 수 없게', 그리고 '방법의 수'라는 것을 보고 이 문제는 단순 구현 문제라는 것을 알 수 있었다. 우선 첫 줄에 퀸을 어디에 놓느냐 그리고 다음 줄에 퀸을 어디에 놓느냐에 따라 그 다음줄에 놓을 수 있는 퀸이 놓여지지 않는 곳을 결정할 수 있다. 즉, 해당 위치에 퀸을 놓았을 때와 안 놓았을 때로 구분되는데 이러한 문제는 백트래킹으로 쉽게 풀 수 있다. 퀸이 공격하는 방향은 상, ..

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

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

문제 전위 순회하는 이진 트리가 주어진다. 이를 통해 후위 순회한 결과를 출력한다. 입력 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 10^6보다 작은 양의 정수이다. 노드의 수는 10,000개 이하이다. 예제 입력 50 30 24 5 28 45 98 52 60 예제 출력 5 28 24 45 30 60 52 98 50 문제 해결 어디서 힌트를 얻을 수 있을까? 전위 순회라는 말에서 우리는 이것을 분할 정복으로 문제를 풀 수 있다는 것을 눈치챌 수 있다. 전위 순회는 (루트)(왼쪽 자식)(오른쪽 자식) 순으로 출력하는 순회 방법으로 맨 처음 출력되는 것이 루트라는 것을 알 수 있다. 또한, 이는 이진 트리이기 때문에 루트를 기준으로 왼쪽은 더 작은 값 오른쪽은 더 큰 값이라는 것을 알 ..

알고리즘/문제 2023. 6. 4. 23:30