이런 말이 있다. 동적 계획법이라는 말은 전문가들이 전문가들처럼 보여줄 수 있도록 해주는 말이고 일반인들에게는 그냥 ‘기억해서 풀기’ 다. 이항계수에 관련한 성질은 기억해두면 이후 코딩이나 알고리즘 문제를 풀 때 유용하기 때문에 기록해 준다. 이항계수를 풀 때 중요한 성질은 다음과 같다. $$ {n \choose k} = {n \choose n-k} $$ $$ {n \choose k} = {n-1 \choose k} + {n-1 \choose k-1} $$ $$ \sum_{k=1}^n {n \choose k} = 2^n $$ 위의 공식은 이항계수의 정의식을 참고해서 유도하는 방법으로 이항 계수의 정의식을 알고 있어야 한다. $$ {n \choose k} = {n}\mathrm{C}{k} = \frac{n!}{(n-k)!k!} $$ 동적 계획법을 활용한 이항계수 풀이 이항계수에 관련한 알고리즘 문제를 풀기 위해서 이항계수의 2번째 성질을 이용하기로 한다. 그 이유는 2번째 성질이 …

분할정복 알고리즘을 배울 때 나오는 유명한 문제 중 하나이다. 하지만 난이도가 굉장히 높기 때문에 쉽게 접근하기 어려웠는데, 분할 정복에 남은 마지막 문제를 그냥 안풀고 넘어가기엔 마음에 걸려서 마음먹고 공부해보기로 했다. 백준 사이트에서도 검색을 추천하여 알고리즘을 공부하기를 권하기 때문에 검색을 통해 좋은 글을 발견했다. 그리고 해당 문제의 솔루션을 이해하는데만 집중했다. 분할정복 문제를 반복해서 풀어보니 분할정복은 DP 만큼이나 여러가지 형태의 문제가 있으니 최대한 많은 문제들을 풀어보는 것이 중요하다는 것을 알 수 있었다. 그리고 여러 문제를 풀어 본 결과 다음을 깨달을 수 있었다. 분할정복에서 분할을 하는 이유 중 하나는 굳이 필요 없는 연산/비교 등을 하지 않기 위해서이다. 다르게 이야기하면 쓸데없는 것을 쳐내기 위해서 특정 기준에 따라서 계속 분할을 하는 것이다. 백준 2261 문제를 보면 어떤 의미인지 알 수 있다. 이 사실이 나로 하여금 더 구현을 잘하게 해주…

Back-tracking 알고리즘을 공부할 때 제일 먼저 구현하는 것이 순열과 조합이다. Back-tracking 알고리즘에 대해서 입문하고 감을 잡기 위해서 시작하기 좋은 코드이다. 따라서 순열과 조합을 구하는 코드를 보고 외워서 머릿속에 저장해두는 것을 추천한다. 순열과 조합의 차이점: 순열: 순열은 순서가 있는 조합이다.(A Permutation is an ordered Combination) 조합: 조합은 순서를 생각하지 않고 선택만 한다. 순열 코드 조합 코드 순열 코드 조합 코드

Binary Search 이분탐색을 구현하면서, 계속 런타임 에러가 났다. 처음에 재귀로 구현을 시작했는데, 재귀에 너무 큰 값이 들어오면서 stack overflow 에러가 났나 싶어서 다시 while 문으로 구현했다. 하지만 while 문으로 구현한 이후에도 계속 런타임 에러가 떠서 확인해보니, n과 m을 헷갈려서 잘못 적었던 것이었다. 이왕 while 문으로 구현해서 맞은 거, 재귀와 비교해 보자 해서 재귀를 돌려 보았더니, 재귀가 훨씬 빠르고 메모리 효율도 좋은 것이었다. 일반적으로 생각했을 때, 재귀는 매번 메모리를 할당하면서 새로운 함수를 call 해주어야 하고, 또 그만큼의 시간과 공간이 더 필요해서 반복문에 비해 성능이 다소 떨어진다고 알고 있었지만, 훨씬 빠르고 메모리 효율도 좋아서 그 이유에 대해서 찾아보게 되었다. 정딥은 Tail-recursion. Tail-Recursion Tail-Recursion이란? Tail-Recursion이란 recursion 함수…

앞서 히스토그램 문제에 대한 접근 방법을 간단하게 설명하고 세그먼트 트리를 히스토그램에 맞추어서 설명했다. 이번 글에서는 구체적으로 어떻게 세그먼트 트리를 구현하여 히스토그램 문제를 푸는데까지 이어지는지 다루어 보도록 하겠다. 이 문제는 레벨이 높은 문제이긴 하지만 아이디어 자체가 굉장히 어렵거나 하진 않다. 다만 시간 복잡도 측면에서 효율적으로 접근하기 위해 세그먼트 트리를 활용하는게 좀 낯설어서 어려웠던 것 같다. Segment Tree 구현 Segment Tree를 구현할 때 배열을 사용해서 구현하도록 할텐데 segment tree는 다음과 같은 성질을 가지고 있다. 세그먼트 트리는 거의 Full Binary Tree(비슷한 형태를 지님)의 모습을 하고 있다. 왼쪽 자식: 부모노트 * 2 오른쪽 자식: 부모노드 * 2 + 1 높이: lgN 배열을 통해서 tree를 구현하려면 사전에 tree의 노드 갯수를 파악해서 배열의 크기를 지정해야한다. 위의 성질들을 이용하면 해당 tre…

히스토그램에서 가장 큰 직사각형의 크기를 찾는 알고리즘을 풀다가, 관련 문제의 풀이법을 간단히 찾아서 금방 해결할 줄 알았으니 구현에서 의도치 않은 오랜 시간이 걸렸다. 먼저 문제의 해결 방법을 요약하면 다음과 같다. 히스토그램 중, 높이가 가장 낮은 min 값과 해당 너비값을 곱하여 넓이를 구함. 해당 최소값을 기준으로 히스토램을 나누어서 1번을 반복함. 더 이상 나눌 수 없을 때까지 반복하며 매번 넓이의 max 값을 업데이트 함. 다음은 백준 블로그에 있는 문제 해설에서 가져온 그림이다. 위의 해결 방법을 이해하는데 도움이 된다. histogram{: width=“80%“} 처음에 단순히 이 풀이방법을 배열과 재귀를 사용해서 구현하는 방법으로 시도를 했었다. 사이트에 나와있는 테스트 케이스가 통과하길래 바로 채점을 했더니 결과는 시간초과 였다.. 개인적으로 알고리즘을 할 때 가장 어려운 부분이 답을 출력이 되지만 시간초과가 나올 때 인 것 같다. 문제설명 밑에 해당 문제를 세그…

알고리즘에 대해서 배울 때 가장 먼저 다루는 부분이 바로 Time Complexity 이다. 기술이 발전하면서 메모리에 대한 부분은 상당 부분 해결이 되고 걱정하지 않아도 되는 부분이 되었다. 하지만 시간 복잡도 측면에서는 아무리 발전해도 부족한 부분이다. 왜냐하면 짧으면 짧을수록 더 좋기 때문이다. 따라서 알고리즘 강의를 들을 때에는 항상 Time Complexity에 대한 강의를 시작으로 배운다. 어떠한 문제에 대해서 여러가지 알고리즘을 사용하여 해결할 수 있을 때 무엇이 최적의 알고리즘인지를 판단하는 잣대는 해당 알고리즘으로 문제를 해결하는데 걸리는 시간이기 때문이다. 거기서 핵심적인 역할을 하는 두 theory에 대해서 다음 글의 내용을 번역 및 정리하면서 알아보자. Lower Bound와 upper Bound Theory는 어떠한 문제에 대한 가장 적은 복잡도를 가진 알고리즘을 선택하는데 핵심적인 역할을 한다. 구체적으로 이 이론들을 다루기 이전에 각각 Lower Bou…

이진탐색의 응용 버전으로 상/하한선을 찾는 알고리즘이다. 이를 응용한 문제를 풀면서 배운 개념을 정리해둔다. 이진탐색을 사용하면 모든 요소들을 다 방문하면서 탐색하는 것보다 훨씬 더 효율적으로 원하는 요소를 탐색할 수 있다. 하지만 이진탐색의 경우, 중복되지 않은 값이 주어진 경우이거나, 해당 요소의 존재 여부만을 가리기 위해서 일 경우에만 사용이 가능하다. 위의 문제의 경우, 중복되는 값들이 존재하며 그 값들이 총 몇개가 있는지도 확인할 수 있어야 하기 때문에 일반적인 이진탐색을 통해서는 답을 도출할 수 없다. 그래서 찾은 알고리즘 Upper Bound 와 Lower Bound 알고리즘 이다. 이진탐색에서 살짝 변형되어서 중복된 자료가 있을 때 유용하게 탐색할 수 있는 알고리즘이다. 아래 그림을 보면 lower bound와 upper bound에 대해서 더 잘 이해할 수 있다. image Upper Bound Algorithm 구현은 이진 탐색과 매우 유사하지만 약간의 변형…

다음은 분할정복 Divide and Conquer Algorithm에 대한 지식 블로그 번역 및 요약+추가정리 내용이다. 원문: https://www.geeksforgeeks.org/divide-and-conquer-algorithm-introduction/ 이 글에서는 분할정복이 유용한 경우와 분할정복으로 해결할 수 있는 문제의 접근방식에 대해서 다룰 것이다. 다음이 이 글에서 다룰 내용들이다. DAC(분할정복) 소개 및 정리 DAC을 사용하는 알고리즘 DAC 알고리즘을 사용한 재귀 DAC를 사용한 문제 예시 Divide and Conquer: Divide: 문제를 분할이 가능한 경우까지 분할한다. Conquer: 분할된 sub problem을 재귀로 호출해 정복한다. Combine: 해결된 sub problem들을 합쳐 문제의 해결책을 찾는다. DAC가 응용된 알고리즘 기법들: Binary Search(이진탐색): 검색하고자 하는 value를 주어진 배열의 중간 인덱스((…