중점 1. 불규칙적인 배열에서 최대의 부분 수열의 합을 구한다. 2. 반복되는 구조의 로직이 존재한다. https://wnehgus101.tistory.com/entry/백준-11053번-가장-긴-증가하는-부분-수열-C-풀이 11053번 가장 긴 증가하는 부분 수열 / C++ 풀이 중점 1. 불규칙적인 배열에서의 최대 부분 수열 찾기 2. 짧은 시간 내에 전체 배열의 속성을 찾아보아야 하는 문제 이중 반복문을 통해서 모든 배열의 속성에 대해서 매번 최대 부분 수열을 탐색 wnehgus101.tistory.com 위 문제와 동일한 풀이 방식이다. DP알고리즘을 이용한 최대, 최소를 구하는 문제는 많은 경험치가 중요하다고 생각한다. 위 문제와는 다르게 DP 배열에 저장될 수 있는 값은 입력 받는 값 자체이다..
coding-test
중점 1. 불규칙적인 배열에서의 최대 부분 수열 찾기 2. 짧은 시간 내에 전체 배열의 속성을 찾아보아야 하는 문제 이중 반복문을 통해서 모든 배열의 속성에 대해서 매번 최대 부분 수열을 탐색하는 방법이 있다. 하지만 효율적이지 못하고 시간 제한에 관한 문제도 있다. 따라서 DP 알고리즘을 사용할 수 있다. DP 알고리즘을 이용한 최대 혹은 최소를 찾는 문제들의 공통적인 특징은 점화식을 이용해서 값을 저장하는 배열에 저장되는 값은 그 당시의 최대 혹은 최소값이라는 것이다. 따라서 해당 값을 이용한다면 최대 혹은 최소값을 찾을때 n-2(예를 들면)번째의 최대, 최소값에 현재 n번째의 경우의 수만 더해주는 방식이라는 것이다. n번째의 최대, 최소 값을 구하기 위해서 다시 0번부터 loop를 돌 필요가 없다는..
중점 1. 각각의 동전의 개수가 한계가 없다는 점 2. 동전의 최소 수를 구해야 한다는 점 그리디 알고리즘을 이용하여서 항상 최적의 선택을 하면 선택들의 집합이 최종 답이 되는 구조이다. 따라서 오름 차순으로 입력 된 동전의 가치를 반복문을 통해서 역으로 내려오며 최종 값에서 가능 한 만큼 제외한다. 해당 방법을 반복한다면 최소로 필요한 동전의 개수를 알 수 있다. 동전 개수의 한계가 없기에 얼마나 많은 동전을 선택하는지에 대한 문제가 없다. 정답 코드 #include using namespace std; int n, k; int a[15]; int main(void){ ios::sync_with_stdio(0); cin.tie(0); int ans = 0; cin >> n >> k; for(int i ..
중점 1. DP 알고리즘 사용을 위한 문제 분석 2. 오버플로우 방지하기 위 문제에 대해서 분석을 하자면 n번째에 오는 수에 따라서 n-1번째의 수는 고정이 된다는 점이다. 만약 n번째에 5라는 수가 들어갔다면 n-1에는 4 or 3이라는 수가 들어갈 수 있다. 따라서 행렬을 이용한다면 d[3][3] = d[2][2] + d[2][4]가 되는 것이다. d[길이가 n인 수][n번째 자리에 있는 수] = 해당 숫자의 계단 수의 개수이다. 따라서 0과 9를 제외하고는 n-1인 길이의 수의 접근가능한 행렬에서의 값을 더해주면 된다. 0과 9는 각각 1과 8에서 더한다. 또한 위의 계단 수는 많은 개수가 예상 되어서 오버플로우가 일어 날 수 있다. 따라서 문제에서와 같이 1,000,000,000으로 나눈 나머지를..
중점 1. 입력 받은 수의 개수를 파악해야한다. 2. 유무 및 개수를 출력해야한다. 없다면 0으로 출력한다. 3. 카드의 개수 범위가 많음에도 불구하고 시간제한이 짧다. 3번의 중점 때문에 binary_search를 사용하려했다. 그러나 binary_search 함수는 0과 1로 해당 숫자의 유무만을 반환한다. 따라서 이분 탐색을 활용한 다른 함수를 사용하였다. upper_bound라는 함수는 n이라는 숫자가 마지막으로 나오는 순서 다음 번의 번호를 return한다. 정확하게 이야기 한다면 n을 초과하는 숫자가 처음 나타나는 순서를 return한다. 하지만 sort한 후 진행하기에 위와 같이 이해하여도 된다. lower_bound는 n이라는 숫자가 처음 나오는 위치를 return 한다. 따라서 개수를 알..
중점 1. 제한 시간 1초로 적은 시간 2. f(n) = f(n-1) + f(n-2) + f(n-3)이다. 제한 시간이 1초로 적고 추가 시간이 없다고 명시되어 있다는 것을 보고 DP 힌트를 얻었다. 따라서 점화식을 구하려 노력하였다. 중점 2롸 같은 점화식을 파악할 수 있었고 f(n)에 대한 피보나치 수열임을 확인 하여서 코드를 작성했다. #include using namespace std; int d[11]; int t, n; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> t; d[1] = 1; d[2] = 2; d[3] = 4; for (int i = 4; i < 11; i++){ d[i] = d[i - 3] + d[i - 2] + d[i..
