1. 비트 마스크 이진법 관련 연산들을 아주 빨리 할 수 있도록 정수의 이진수 표현을 자료 구조로 쓰는 기법 (엄밀하게 자료 구조라고 할 수 없음) 2. 비트 마스크의 장점 - 더 빠른 수행 시간 : 대부분 연산은 O(1)에 구현된다. - 더 간결한 코드: 다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있기 때문 - 더 작은 메모리 사용량: 같은 데이터를 더 적은 메모리를 사용해 표현할 수 있다. - 연관 배열을 배열로 대체: map같은 연관 배열 객체를 단순 배열을 사용해 같은 정보를 표현 3. 비트 연산자 - AND연산: 두 비트가 모두 1인 경우. 1반환 - OR연산: 두 비트중 하나라도 1인 경우. 1반환 - XOR연산: 두 비트중 하나만 1인 경우 (1의 개수가 홀수). 1반환 - NOT연산..

동적 계획법이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔다. 중복되는 부분 문제 없애 최적화하여 속도향상을 꾀하는 알고리즘 설계 기법이 바로 동적 계획법이다. 동적계획법은 분할 정복과 접근방식이 같다. 주어진문제 -> 더 작은문제들 -> 조각 계산 -> 조각의 답들로부터 원래 문제 답 계산 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에 여러번 계산하는 대신 한번만 계산하고 계산 결과를 재활용함으로써 속도 향상을 꾀함 각 문제의 답을 메모리에 저장해 둘 필요가 있음 이미 계산한 값을 저장해 두는 메모리의 장소를 캐시라고 부름 두번 이상 계산되는 부분문제를 부분 문제(overlapping subproblems)라고 부름 계산의 중복 횟수는 분할의 깊이가 깊어질 수록 지수적으로 ..

주어진 문제를 둘 이상의 부분 문제로 나누고 각 문제에 대한 답을 재귀 호출을 이용해 계산 각 부분 문제의 답으로부터 전체 문제의 답을 계산 문제를 거의 같은 크기의 부분문제로 나눈다. 세가지 구성요소 1. 문제를 더 작은 문제로 분할하는 과정(divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case) 자연스러운 방법으로 나누고 나눈 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 필요 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커짐 (부분 문제가 중복된다 overlapping subproblems) 같은 아이디어로 정렬을 수행하지만 시간이 많이 걸리는 작업을 분..

1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠. 만약 시간 안에 계산할 수 없다면 다른 설계 패러다임을 적용. 2. 가능한 모든 답의 후보를 만드는 과정을 여러개의 선택으로 나눔. 각 선택은 답의 후보를 만드는 과정의 한조각이됨. 문제 -> 부분문제 3. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성. 4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리. -알고리즘 문제해결전략 154p