알고리즘/문제풀이 - 백준

백준 11066 파일 합치기

문제 : https://www.acmicpc.net/problem/11066 서론 계산할 수 있는 모든 경우의 수를 재귀+메모이제이션으로 풀려고 했으나 메모이제이션을 어떻게 해야할지 전혀 떠오르지 않았다. 그래서 아래 블로그의 2번 풀이를 참고했다. 참고한 풀이와 90% 유사한데 유사하지 않은 부분은 for문의 추가로 시간복잡도가 좋지않다. https://js1jj2sk3.tistory.com/3 풀이 예 : 40 30 30 50 구간 1~4는 40 / 30 30 50 40 30 / 30 50 등의 여러가지 방법으로 2분할이 가능함 구간 1~4에서 분할된 방법 중 하나인 40 / 30 30 50의 오른쪽 30 30 50은 30 / 30 50 30 30 / 50 으로 다시 분할이 가능함 분할된 30 / 3..

2020. 3. 29. 15:03
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 타일 장식물

문제 : https://programmers.co.kr/learn/courses/30/lessons/43104 서론 피보나치수열과 DP문제. 프로그래머스의 레벨3 문제들만 풀고있는데, 같은 레벨인 문제들도 난이도 격차가 꽤 큰거같다. 이 문제는 DP의 전형적인 문제다. 풀이 그림이 그려져있다. 1, 1, 2, 3, 5, 8.... 피보나치수열이다. 그럼 DP를 이용한다. 문제를 보니 둘레를 구해야하는데 answer = (dp[N-1] + dp[N-2] + dp[N-2] + dp[N-3])*2; 위와 같이 점화식을 만들 수 있다. 그리고 N이 1, 2일때는 dp배열의 음수인덱스를 가지기 때문에 예외처리해줘야하는데, 예외처리를 해주지 않아도 통과한다. 테스트케이스가 없나보다. 구현 // c++ #includ..

2019. 10. 10. 22:38
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 2 x n 타일링

문제 : https://programmers.co.kr/learn/courses/30/lessons/12900 서론 DP문제. 풀이 문제에 1000000007로 나눈 나머지를 출력하라는 조건이 있다. DP문제일 가능성이 매우 높으므로 규칙성을 찾는다. 직접 그려보니 result[n] = result[n-1] + result[n-2]인것 같다. 간단한 코드니 DP로 구현해본다. 통과. 구현 // c++ #include using namespace std; int dp[60001]; int solution(int n) { int answer = 0; dp[0] = 1; dp[1] = 2; for(int i=2; i

2019. 10. 9. 16:02
알고리즘/문제풀이 - 백준

백준 12865 평범한 배낭

문제 : https://www.acmicpc.net/problem/12865 서론 어디서 본것같은 문제였는데 풀어보니 처음본다. 공부해놓고 잊은건 실망스러우니 어디서 본것같은건 반드시 착각이다. 풀이 유명한 문제라고 해서 크게 고민 안하고 배낭문제를 검색했다. 참고한 사이트는 https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C 배낭문제를 모르고, 위의 참고한 사이트를 읽어보지 않으면 아래의 내용은 이해할 수 없다. dp의 행은 아이템, 열은 무게다. 무게 3짜리를 기준으로 dp[0][0]..

2019. 8. 19. 15:52
알고리즘/문제풀이 - 백준

백준 11049 행렬 곱셈 순서

문제 : https://www.acmicpc.net/problem/11049 서론 DP와 분할정복 아이디어를 이미 갖고 있었음에도 구현을 못한 문제 행렬을 어떻게 곱해서 재귀함수의 리턴으로 넘겨줘야할지를 해결하지 못했다. 다른분의 풀이를 참고하여 구현한 지금에서도 왠지모를 석연찮음이 남아있다. 아이디어 11066번 문제와 유사하다. 전체적인 풀이 아이디어는 이 문제와 같다. https://hydroponicglass.tistory.com/4 위 문제와 다른점은 행렬을 계산하는 것. (AB)(CD)에서 ABCD는 AB와 CD의 곱이다. 따라서 왼쪽분할인 AB의 결과값과 오른쪽분할인 CD의 결과값에 AB와 CD를 곱한 결과값을 더해줘야한다. 즉 재귀함수의 리턴값은 왼쪽+오른쪽+(왼쪽*오른쪽) 리턴값의 왼쪽*..

2019. 8. 18. 18:56
알고리즘/문제풀이 - 백준

백준 9461 파도반 수열

문제 : https://www.acmicpc.net/problem/9461 풀이 점화식을 세우는것이 중요하다. n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 1 1 1 2 2 3 4 5 7 9 n6부터 n[i] = n[i-5] + n[i-1]의 규칙을 발견할 수 있다. 즉 n6 = n1 + n5 구현 배열에 integer 범위를 초과하는 값이 들어가므로 더 큰 자료형을 선언해야한다. // C++ #include using namespace std; int t, n; long long dp[101]; void cal() { dp[1] = 1; dp[2] = 1; dp[3] = 1; dp[4] = 2; dp[5] = 2; for (int i = 6; i > t; for (int i = 0; i < ..

2019. 5. 23. 19:19