기어가더라도 제대로

정의 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식 그리디나 백트래킹처럼 특정 알고리즘이 아닌 문제 해결 방식을 의미한다. Dynamic Programming(DP) 이라고도 부른다. 동적 계획법이 어렵게 느껴지는 원인 중 하나 Dynamic 하지 않고 Programming 과도 관련이 없다. 메모리를 많이 사용하는 대신 빠른 성능을 자랑한다. 두 가지 방법론이 있다. 메모이제이션(Memoization) 타뷸레이션(Tabulation) 메모이제이션 하향식 접근법 동적 계획법에서 작은 문제들의 결과는 항상 같다. 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 메모이제이션이다. 피보나치 수열이 주로 예시가 됨 위와 같이 있다고 할 때 중복되는 것들이 몇몇 있다. 이미 해결한 문제는 ..

정의 모든 경우의 수를 탐색하는 알고리즘 DFS나 BFS를 이용할 수 있다. 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기(Pruning)라고 한다. 자바스크립트는 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다. 코딩 테스트에선 이를 고려하여 재귀로 작성해도 풀 수 있도록 문제를 제출하는 경우도 있다. 탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다. DFS, BFS 정말 많이 나오는데 코테를 풀 때는 꼭알고 있어야하는 개념이다. 백트래킹의 핵심은 가지치기! 가지치기를 얼마나 잘하느냐가 효율성을 좌우한다. 어떻게 작성할 것인가? 우선, 모든 경우의 수를 찾을 수 있도록 코딩 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머..

투포인터 알고리즘 정의 일차원 배열에 두개의 포인터를 두고 조작하는 알고리즘 보통 연속적인 구간에 대한 계산을 할 때 많이 사용한다. 구간합 문제에서 많이 사용 count = 0 partialSum = 7 P1 = 0 P2 = 0 부터 출발해서 두 포인터가 마지막 요소까지 도착을 하며 두 포인터사이의 합이 10이 될때 마다 카운터에 1을 더한다. 목적값이 10인데 부분합이 7이므로 두번째 포인터를 이동시킨다. 부분합이 8이 되었다. count = 0 partialSum = 8 P1 = 0 P2 = 1 부분합이 8로 10을 넘지 않으므로, 두번째 포인터를 한칸 이동한다. 부분합이 11이 되었다. count = 0 partialSum = 11 P1 = 0 P2 = 2 부분합이 10을 넘었으므로, 첫번째 포인..