공부/알고리즘 (15) 썸네일형 리스트형 [알고리즘] 동적 계획법(dynamic programming) - fin. 드디어! 마지막입니다!! 오늘 알려드릴 동적 계획법 테크틱은 반복적 동적 계획법 입니다!지금까지는 재귀 함수를 이용해서 메모이제이션을 하기 위한 저장 공간을 만드는 것을 많이 보여드렸었죠! 반복적 동적 계획법을 이용하면 좋은점이 몇 가지 있습니다! 첫번째로는, 공간 복잡도를 줄일 수 있다는 것입니다! 재귀 함수를 통해서 메모리를 만들어 놓으면 함수 간에 순서가 명확하지 않기 때문에 처음부터 끝까지 사용할 공간을 미리 만들어 놓고,지우지 않습니다! 하지만, 반복적 동적 계획법을 이용하면 다릅니다. 대표적으로 유용하게 이를 활용하는 것이 슬라이딩 윈도 테크닉입니다! 예전에 삼각형 위의 최대 경로 알고리즘을 푼 적이 있었죠!재귀 함수를 이용한 메모이제이션을 이용할 때에는, 삼각형의 높이에 따라서 공간 복잡도가.. [알고리즘] 동적 계획법(dynamic programming) - 6 이번에는 조합 게임을 하는 경우에서 사용하는 동적계획법입니다! 바로, 체스나 바둑, 오목처럼 두 사람의 참가자가 하는 게임이죠!이 게임의 문제를 해결한다는 것은, 게임의 상태가 주어졌을때 완벽한 수를 찾아내는 알고리즘, 다시 말하면 자신이 최대한으로 이길 수 있는 수를 찾아내는 것이죠! 이런 수는 어떻게 찾아내면 될까요? 어떠한 경우에도 결국 게임이 끝나는 부분은 존재할 것입니다! 거기서 게임의 승/패는 갈리게 되겠죠. 여기서 A는 당연히 A가 이기는 결과로 갈 것입니다! 즉, 해당 차례인 사람의 차례에서 이기는 루트가 있다면 바로 이기는 수를 두게 되고, 해당 차례 사람은 이기게 되는 것이죠! 만약, B 차례인데 B가 이기는 경우가 없다면 어떻게 될까요? 위와 같은 경우는 어떻게 하더라도 A가 이기는 .. [알고리즘] 동적 계획법(dynamic programming) - 5 오랜만에 쓰는 알고리즘 글입니다!요즘 뭔가 하고싶은 일이 많다보니 알고리즘을 조금 줄이게 됐네요!종만북 1권도 도대체 언제 끝낼지 모르겠습니다 후덜덜;; 각설하고 이제 동적 계획법에 대해서 설명하겠습니다! 오늘은 정수 이외의 입력에 대해서 어떻게 메모이제이션을 할 것인가? 에 대해 알아보겠습니다! 지금까지는 메모이제이션에 사용되는 값이 정수였습니다!하지만, 가끔씩 메모이제이션에 사용해야 하는 값이 문자열이거나 배열인 경우가 있습니다. 이런 경우에는 어떻게 메모이제이션을 해야할까요!? 첫번째로는 STL의 힘을 빌리는 방법이 있습니다.C++ STL에는 map과 vector라는 아주 훌륭한 stl이 있기 때문에 다음과 같이 메모이제이션을 사용할 수 있습니다. map memoi STL의 컨테이너는 자체적인 대소.. [알고리즘] 동적 계획법(dynamic programming) - 4 오늘은 알고리즘 동적 계획법 4번째를 설명하도록 하겠습니다!진짜 동적 계획법 엄~~~청 길어서 거의 10까지 할 것 같아요. 이번 동적 계획법에서는 k번째 답을 계산할때 쓰는 방법입니다! 예를 들면, 한 배열에서 LIS들은 한 가지 방법만 있는 것이 아닙니다.가능한 LIS들을 사전순으로 나열한다고 할 때, k번째 LIS를 구하려면 어떻게 해야할까요? 우선, 사전순으로 개수를 세는 알고리즘을 만드는 경우를 생각해 봅시다. 1번째 답으로 올 수 있는 경우가 3개 있다고 합시다. 그럼, 경우 1에서 만들어 질 수 있는 수가 n1개 있을것이고,경우 2에서 만들어질 수 있는 경우의 수가 n2개 있을 것 입니다. 하지만, 만약 경우 1에서 만들어질 수 있는 수가 k개 보다 작으면 어떨까요?그럼, 경우 1의 경로를 .. [알고리즘] 동적 계획법(dynamic programming) - 3 이번에는 경우의 수, 확률과 동적 계획법에 대해서 알아보겠습니다!경우의 수나 확률의 경우에도 재귀적인 특징을 많이 가지고 있기 때문에 동적 계획법을 많이 이용합니다. 대표적으로, 이항 계수를 구하는 가 있습니다! 경우의 수를 세는 것도 이전의 최적 부분 구조를 이용합니다.이전까지 어떤 경로로 왔던 상관없이, 현재 진행중인 부분부터 끝까지의 경우의 수를 센 뒤에 이 값을 반환하면,이 반환된 값을 통해 더하든 곱하든 해서 처리하는 방식이 일반적인 경우의 수를 동적 계획법으로 풀어가는 방식입니다. 이 때, 다음 경로를 선택해야할 때 고려해야할 것이 2개 있습니다. 첫 번째는 모든 경로가 내가 선택하려고 하는 범위 내에 있어야 한다는 것이고,두 번째는 어떤 경우더라도 내가 선택하려고하는 선택지에 두 번 포함되면.. [알고리즘] 동적 계획법(dynamic programming) - 2 오늘은 동적 계획법 제 2 단계를 시작하겠습니다!지난번에는 메모이제이션을 통해서 입력 값이 계산되었다면, 바로 그 값을 반환하는 것을 배웠습니다.이번에는 입력값을 어떻게하면 걸러낼 수 있을지에 대해서 한번 살펴보겠습니다. 만약, 앞에 해결한 부분의 조각들의 결과들이 뒤에 미해결된 부분 조각들에 영향을 주지 않는 문제가 있다고 합시다.(대표적으로, 수열에서 점차적으로 증가하는 부분집합의 가장 긴 개수를 찾는 LIS(longest increasing subsequence가 있습니다.) 그렇다면, 이 문제의 답은 (0~0번 까지의 답) or (0~1번 까지의 답) or (1~2번 까지의 답) 등등... + (3~5번 까지의 답) 으로 나눠서 구할 수 있습니다.(현재의 답 + solve(3,5) 의 형식으로 나.. [알고리즘] 동적 계획법(dynamic programming) - 1 오늘은 동적 계획법에 대해서 설명하겠습니다.동적 계획법은 분할 정복과 유사합니다.동적 계획법 또한, 문제를 더 작게 나눈 다음에 각 조각의 답을 구한 뒤에 이 답들로부터 원래 문제에 대한 답을 계산하기 때문입니다.다만, 동적 게획법의 부분 문제는 두 개 이상의 부분 문제를 푸는데 사용될 수 있습니다!따라서, 해당 부분 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 다시 사용해서 속도의 향상을 가져올 수 있습니다.이를 위해서, 각 부분 문제의 답을 메모리에 저장하는 방식을 취합니다!!이를 메모이제이션 (memoization) 이라고 합니다. 여담이지만, 메모이제이션을 메모리제이션과 햇갈리는 경우가 굉장히 많습니다! 실은 저도 최근에서야 메모리제이션이 아니라 메모이제이션인걸 알았습니다.... [분할정복/카라츠바 알고리즘] 곱셈 최적화! 카라츠바 알고리즘에 대해 알아보자 기본 단계 카라추바 알고리즘의 기본 단계는 큰 두 수 x와 y의 곱을 자릿수가 x, y의 절반인 수들의 곱 3번과 덧셈과 시프트 연산을 이용해 계산하는 것이다. x와 y를 B진법의 n자리수라고 하자. n보다 작은 양수 m에 대해 다음과 같이 x, y를 쪼갤 수 있다. x = x1Bm + x0 y = y1Bm + y0 (단, x0과 y0는 Bm보다 작다.) z2 = x1y1 z1 = x1y0 + x0y1 z0 = x0y0 라고 할 때, x와 y의 곱은 xy = (x1Bm + x0)(y1Bm + y0) = z2 B2m + z1 Bm + z0 이 식은 4번의 곱셈을 해야한다. 카라추바는 덧셈을 몇 번 함으로써, xy를 3번의 곱셈을 통해 구할 수 있다는 걸 알았다. z2 = x1y1 라 하자. z0 = x0y.. 이전 1 2 다음
