가장 긴 증가하는 부분 수열 (Longest Increase Sequence)
안녕하세요. 이번 포스팅에서는 가장 긴 증가하는 부분 수열문제를 해결해 보도록 하겠습니다. 우선 가장 기본적인 포맷은 다음과 같습니다. 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로 해결할 수도 있는데, 이번 포스팅에서는 dp를 사용하지 않고 풀어보도록 하겠습니다. #include using namespace std; int n, res; int ..
[C++/Algorithm] 순열과 조합 구현하기
이번 포스팅에서는 C++로 순열과 조합을 구현해보려 한다. 1. 순열 순열은 '순서'의 개념이 존재하는 조합이다 가령 [1, 2, 3] 중 3개의 원소로 만들 수 있는 모든 순열의 집합은 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 이렇게 6개의 순열이 나올 수 있고, 간단하게 3!로 그 수를 구할 수 있다. 컴퓨터로 순열을 구현하는 방법에는 몇 가지가 있는데, 가장 기본적으로 DFS 방식, 즉 재귀적으로 방문처리를 이용하여 순열을 구할 수 있다. // Permutation DFS로 구현 #include using namespace std; void Permutation(int visited[3], vector & vec, vecto..
