기어가더라도 제대로

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

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

정의 비트를 직접 조작하는 연산자 이진법 성질을 이용하여 문제를 해결하는 방법 특정 알고리즘은 아니고 비트 연산을 이용한 일종의 코딩 기법 이진수가 자료구조로 사용된다. 배열 대신 이진수를 이용할 수 있다. ex) [true, true, false,true] = 1101(2) 굉장히 빠르고 메모리 사용량이 적다. 그리디, 동적 계획법 등 다른 알고리즘과 함께 사용할 수 있다. 사용법 주의할 점 정수형 범위를 넘지 않도록 조심 연산자 우선 순위에 주의할 것 출처 케이시 강의