화분

문제 출처 : https://www.acmicpc.net/problem/12865 배낭 문제는 다이나믹 프로그래밍의 대표적인 문제 중 하나이다. 대학교 알고리즘 수업을 들을 때 풀어봤던 문제라서 풀이 전략을 떠올리는 것은 어렵지 않았으나 세부적인 코드를 짜는데 시간이 조금 걸렸다. 나 같은 경우 2차원 배열의 테이블을 만들어서 풀었는데 이같은 풀이 방법으로 더 간단히 짤 수도 있을거라 본다. 한편 백준에서 다른 사람들이 푼 걸 보면 가끔 말도 안되게 간단하게 풀어서 제출하는 걸 심심찮게 보는데 이 문제도 그렇다. 동적 프로그래밍의 '프로그래밍'의 뜻은 우리가 익히 알고 있는 뜻이 아닌 표(테이블)을 의미한다. 몇차원이든 표에 기록하고 그 기록들을 참조해서 문제를 해결해나간다. 문제를 푸는 방식에는 보텀업..

처음에는 다익스트라 알고리즘의 변형으로 문제를 풀려고 하였다. 알고리즘을 짜는데 상당히 오랜 시간이 걸렸지만(stl 등의 c++ 사용법을 익히는 등의 이유로) 정답은 얼추 잘 맞추는거 같았다. 하지만 메모리 초과 문제가 발생하였다. 초안: #include #include #include using namespace std; int main() { short times = 0; cin >> times; for (int t = 0; t > nob >> nor; for (int i = 1..

이 문제는 조합(combination)에 관한 문제이다. 이 문제를 풀려고 했을땐 동적 프로그래밍 문제인 줄 알았으나 많은 사람들이 조합으로 해결하였고 나 또한 조합 문제라고 생각했다. 동적프로그래밍으로 풀수도 있는진 모르겠다. 처음엔 간단하게 풀 수 있을거라 생각했지만 실제론 어려웠다. 어려웠던 점을 꼽자면 1.변수가 담을 수 있는 숫자의 크기 제한 2.팩토리얼 연산의 한계 3.조합 함수 내에서의 예외 처리 1번의 경우 long long으로 팩토리얼 계산 결과 값을 담는 변수의 크기를 늘렸다. 2번의 경우 팩토리얼 연산의 크기를 줄이는 우회 방법을 사용하였다. 우연히도 오늘 책(종만북)에서 이 부분에 대한 해결법을 봤었고 이 문제에 대해 고민할때 책에 나온 부분을 다시 짚어보았다. 3번의 경우 크게 두..

문제 : https://www.acmicpc.net/problem/1904 풀이과정: N = int(input()) fibo_value = [-1]*(N + 1) def fibonacci(n): if fibo_value[n] != -1: return fibo_value[n] if n == 1: fibo_value[1] = 1 return 1 if n == 2: fibo_value[2] = 2 return 2 else: fibo_value[n] = fibonacci(n-2) + fibonacci(n-1) return fibo_value[n] print(fibonacci(N) % 15746) 고민하다가 피보나치 수열 문제라는 것을 알고 코드를 위처럼 짰으나.. 런타임 에러가 났다. 찾아보니 재귀함수가 너무 ..