컴공과고씨

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제 간단 정리 이 문제는 말 그대로 nCm을 구해주면 되는 문제이다. nCm 이란 서로 다른 n개 중 m개를 뽑는 방법을 말한다. 구하는 법은 n!/m!(n-m)! 이다. 문제 해결 방법 이런 문제 같은 경우 공식을 구현하기 할 수는 있겠지만 답이 겁나게 크게 나오는 걸 볼 수 있다. 즉, c++에서는 저런 큰 수를 정수로 담을 변수가 없기도 하고 공식 구현 하더라도 일일이 다 곱하는 팩토리얼이 있기 때문에 시간초과가 걸릴 수 밖에 없다. 일단 써봐서 규칙을 찾아보는 것이다. 1C0 1C1 2C0 2C1 2C2..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 정리 7 3 8 8 1 0 2 7 4 4 처럼 삼각형이 주어짐 이때 삼각형의 크기가 주어지는데 높이를 나타냄 이 삼각형의 크기는 4임. 이렇게 해서 위에서 부터 숫자를 더해 밑으로 내려온다. 내려갈때는 왼쪽, 오른쪽 대각선으로 이동이 가능하다. 이때 숫자의 최대 합은? 문제 해결 방법 일단 다이나믹 프로그래밍을 이용해서 문제를 풀어야한다. 그리고 쉽게 문제를 풀기 위해 위 삼각형을 0 7 ------ 1번 줄 0 3 8 ------ 2번 줄 0 8 1 0 ----..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제같은 경우 다이나믹 프로그래밍에 대표적인 문제라고 할 수 있다. 각 경우에 대해서 최선의 선택을 하면서 가면 되는데 이 말을 이해하기 위해서는 직접해보는 것이 좋다. 표를 직접 그려봤다면 이게 무슨 원리인지 알 것이다. 자신이 채우고 있는 행의 최선의 선택은 1. dp[i][j] = dp[i][j-현재 물건 무게] + 현재 ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제를 보고 규칙이 있을 것 같아서 쭉 써보았다. 1 -> 1개 2 -> 2개 3 -> 4개 4 -> 7개 5 -> 13개 여기서 점화식을 알아낼 수 있는데 n = (n-1) + (n-2) + (n-3)번째 라는 점화식을 볼 수 있었다. 점화식은 다이나믹 프로그래밍으로 풀면 쉽게 풀 수 있어 다이나믹 프로그래밍을 이용하여서 문제를 풀었다. 단계별 문제 풀이 1. dp 배열 선언 2. 초기값 dp[1], dp[2], dp[3] 값 입력 3. 점화식을 이용해서 풀어줌 전체코드 1 2 3 4 5 6 ..

https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 이 문제를 보고 나는 수학적으로 풀어야겠다고 생각했다. 물론 dynamic programing (동적계획법)으로도 풀 수 있지만 딱 처음 떠오른것이 수학적으로 푸는것이였다. 어떤 생각을 했냐면 일단 최대한 5원짜리를 쓰고 남은 돈에서 만약 2로 나눴을 때 나머지가 0이 안되면 5원짜리를 한 개 덜 쓴 후 2로 나누어 주도록 반복하여 2로 나눈 나머지가 0이 되도록 하면 쉽게 풀릴거라고 생각했다. 그리고 예외처리로 처음 최대한 5원짜리를 쓰고 점점 5원짜리를 줄여갈건데 이것이 음수가 되면 거슬러 줄 수 없는 것이므로 ..

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수를 구하는 문제. 문제를 보면 처음 들어야할 생각은 동적 계획법(dynamic programing)를 떠올려주면 쉽게 풀린다. 재귀로 구현하면 아마 시간초과가 걸릴것이다. 그렇기 때문에 dp 배열을 이용하여 각 값을 저장해주고 다음 값을 구할때 계산하는 대신 앞에 계산한 값을 가져와주면 된다. 현재 값은 그 전의 값 + 그 전전 값 이 식을 구현해 주..