728x90 알고리즘5 [백준_11049] 다이나믹 프로그래밍(DP), 행렬 곱셈 순서 [백준_11049] 다이나믹 프로그래밍(DP), 행렬 곱셈 순서 행렬 곱셈 순서에 따라 곱셈의 횟수가 달라진다. 행렬이 주어졌을 때 다이나믹 프로그래밍(DP)를 이용하여 곱셈 횟수의 최솟값을 구하는 문제이다. 뭔가 어려운 포인트들이 많아 한 번 정리해두면 좋은 문제이다. https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 풀이 생각 포인트 이 문제에서 중요한 포인트는 3가지 정도 있다. i 번 째 행렬의 행은 i-1 번 째 행렬의.. 2021. 9. 1. [WEEK04] 알고리즘_그리디(Greedy) 알고리즘 [WEEK04] 알고리즘_그리디(Greedy) 알고리즘 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 난이도가 매우 낮은 알고리즘 중 하나이다. 항상 최적의 결과를 도출하는 것은 아니지만 어느정도 빠르게 구할 수 있으며 특정한 상황에서는 그리디 알고리즘이 최적의 해를 구할 수 있게 해준다. 예를 들면 거스름 돈 문제이다. 무조건 더 큰 화폐 단위부터 거슬러 주는 것이 최적의 해를 제공한다. 즉, 무조건 큰 경우, 작은 경우, 긴 경우, 짧은 경우 등 극단적으로 문제에 접근한다는 점에서 정렬(Sort) 기법이 함께 사용되는 경우가 많다. 사실 뭔가 특별한 테크닉이 아니라 그냥 특정 경우에 평소 풀던대로 풀면 되는 듯 하다.. 유튜브 - 동빈나 그리디(Greedy) 알고리즘 [ 실전 알고리즘 강좌(Al.. 2021. 8. 30. [백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열 [백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열 다이나믹 프로그래밍 대표 문제인 LCS 문제를 풀어봤다. LCS(Longest Common Subsequence)는 최장 공통 부분 문자열로 다이나믹 프로그래밍의 대표적인 문제이다. 문자열 출력까지 포함하는 9252번 문제를 풀어보았다. https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 풀이 생각 포인트 다이나믹 프로.. 2021. 8. 27. [WEEK04] 알고리즘_다이나믹 프로그래밍(DP) [WEEK04] 알고리즘_다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 특징 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 메모이제이션(Memoization, 이미 계산한 결과는 배열에 저장함. Memorization이 아님)을 통해 동일 계산시 저장된 값을 단순히 반환하여 시간을 줄임 -> 메모리를 적절히 사용하여 수행 시간을 굉장히 단축시킨다. 일반적으로 탑다운(하향식, 재귀함수 이용), 바텀업(상향식) 두가지 방식으로 구현한다. 보통 바텀업이 전형적인 형태이다. 다이나믹 프로그래밍 사용 조건 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 통해 큰 문제를 해결 가능한 구조 중복 부분 문제(Overlapping Subproblem.. 2021. 8. 27. [WEEK03] 알고리즘_그래프, DFS, BFS [WEEK03] 알고리즘_그래프, DFS, BFS 이번 주는 DFS(Depth First Search) 깊이 우선 탐색, BFS(Breadth First Search) 너비 우선 탐색에 대한 내용을 학습한다. 이 두가지 방법은 그래프의 탐색 기법으로 그래프에 대해 먼저 알아보자. 그래프 그래프는 정점(노드)과 간선(엣지)으로 이루어진 자료구조를 의미한다. 또한 간선의 방향의 유무에 따라 단방향 그래프, 무항향(양방향) 그래프로 나뉜다. 그래프를 표현하는 방식은 인접 리스트, 인접 행렬 두가지로 나뉜다. 일반적으로 인접 행렬이 많이 사용된다. 두가지 모두 익숙해져서 문제에 맞는 방법을 이용할 수 있도록 해야겠다. 1) 인접 행렬 그래프 - 모든 정보를 저장 - 장점 : 직관적, 쉽게 구현 가능 - 단점 :.. 2021. 8. 20. 이전 1 다음 728x90
