원

소수 구하기 알고리즘으로 유명한 에라토스테네스의 체는 굉장히 빠르게 동작한다. 그렇기 떄문에 수행 범위를 늘릴 때 부담이 되는 것은 수행 시간이 아닌 메모리이다. 체를 구현할 때는 범위 내의 각 정수가 지워졌는지 여부를 저장해야하는데, 이 부분을 원래는 불린 값 배열을 이용해 표현하는 것이 대부분이다. 32비트 정수가 표현할 수 있는 범위 내의 모든 수에 대해 체를 수행한다고 가정하면 불린 값 배열을 사용하기 위해 4기가바이트의 메모리가 필요하다. 짝수를 제외해 2기가바이트로 줄일 수도 있지만, 여전히 적지 않은 메모리 양이다. 이 때 비트마스크를 사용하면 메모리 사용량을 8분의 1로 다시 줄일 수 있다. MAX_N개의 원소를 갖는 불린 값 배열을 다음과 같은 배열로 대체한다. unsigned char ..

비트마스크의 가장 중요한 사용 사례는 집합을 구현하는 것이다. 이 표현에서 N비트 정수 변수는 0부터 N-1까지의 정수 원소를 가질 수 있는 집합이 된다. 이때 원소 i가 집합에 속해 있는지 여부는 2^i을 나타내는 비트가 켜져 있는지 여부로 나타낸다. 예를 들어 여섯 개의 원소를 갖는 집합 {1, 4, 5, 6, 7, 9}을 표현하는 정수는 754임을 다음과 같이 알 수 있다. 2^1 + 2^4 + 2^5 + 2^6 + 2^7 + 2^9 = 10 1111 0010(2) = 754 비트마스크 연산을 이용해 이 집합을 어떻게 조작할 수 있는지 알아보자. 피자집 예제 토핑을 골라 주문할 수 있는 피자집의 주문 시스템이 있다. 이 피자집에는 0부터 19까지의 번호를 갖는 스무 가지의 토핑이 있으며, 주문시 토..

다양한 문자열 문제를 해결하기 위해서는 접미사 배열(suffix array) 자료구조를 이해해야한다. 접미사 배열은 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해 둔 것이다. 이 말 그래도 모든 접미사들을 문자열 배열에 저장하면 문자열 길이의 제곱에 비례하는 메모리가 필요하기 때문에, 대개 접미사 배열은 각 접미사의 시작 위치를 담는 정수 배열로 구현된다. 예를 들면 아래 표는 문자열 "alohomora"의 접미사 배열 A[]와 각 위치에서 시작하는 접미사들을 보여준다. i A[i] S[A[i] ..] 0 8 a 1 0 a l o h o m o r a 2 3 h o m o r a 3 1 l o h o m o r a 4 5 m o r a 5 2 o h o m o r a 6 4 o m o r a 7 6 ..

https://algospot.com/judge/problem/read/PI algospot.com :: PI 원주율 외우기 문제 정보 문제 (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용 algospot.com #include #include #include #include #include #include #include #include #include #include #include #define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define ENDL cout > N; memset(cache, -1, ..

https://www.acmicpc.net/blog/view/28 피보나치 수를 구하는 여러가지 방법 피보나치 수는 다음과 같이 정의되는 수열입니다. $F_0 = 0$ $F_1 = 1$ $F_n = F_{n-1} + F_{n-2}$ 피보나치 수를 조금 써보면, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 와 같습니다. 피보나치 수를 구하는 함수 www.acmicpc.net https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 주기의 길이가 P 이면, N번째 피보나치 수를 M으로 나눈..

#include #include #include #include #include #include #include #include #include #include #include #define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define ENDL cout > N >> M; for (int i = 0; i > A[i]; for (int i = 0; i > B[i]; } int jlis(int indexA, int indexB) { int& ret = cache[indexA+1][indexB+1]; if (ret != -1) return ret; ret = 2; ll a = (in..

분할 정복(Divede & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라느 말로 간단히 설명할 수 있다. 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해낸다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. 분할 정복을 적용해 문제를 해결하기 위해서는 문제에 몇가지 특성이 성립해야한다. ① 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다. ② 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야한다. 분할 정복..

메모이제이션의 적용 완전 탐색으로 이 문제를 해결하기는 불가능하다. 하지만 적절한 완전 탐색 알고리즘을 만들고 메모이제이션으로 시간을 줄여주면 해결할 수 있다. 이 문제를 푸는 완전 탐색 알고리즘은 주어진 수열을 쪼개는 모든 방법을 하나씩 만들어보며 그 중 난이도의 합이 가장 작은 조합을 찾아낸다. 각 재귀 함수는 한 번 불릴 때마다 첫 조각의 길이를 하나하나 시도해보며 남은 수열을 재귀적으로 쪼갠다. 나머지 수열의 최적해를 구할 때 앞의 부분을 어떤 시그로 쪼갰는지는 중요하지 않다 (최적 부분 구조가 성립) #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #inclu..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 책을 공부하기 전 잠깐 동적 계획법에 대해 공부한 적이 있었다. 이 때, 위 문제를 푼 적이 있었고 그때도 물론 이 문제를 오랜시간 고민하다 결국 다른 분들 설명을 보고 풀었던 기억이 있다. (https://wonsjung.tistory.com/65?category=949214) 이 코드를 보면 2중 for문으로 (완전..

https://www.algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 www.algospot.com 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여..