본문 바로가기

Algorithms135

알고리즘 문제 해결 전략2 18장 선형 자료 구조(2) 18.5 문제: 조세푸스 문제 마지막 두 명 중 하나가 되기 위해서는 조세푸스는 첫 번째 병사로부터 몇 자리 떨어진 곳에 있어야 할까요? 모든 문제는 기본 자료구조로 풀림. 배열, 연결링크드 리스트. 이 자료 구조는 메모리와 데이터로 만들어짐. 문제 풀이를 위해서 필요한 자료 구조를 선태갛기 위해서는 문제를 이해하고 제대로 정의해야 함. 각 테스트 케이스에 두 개의 정수로, 마지막 살아남는 두 사람의 번호를 오름차순으로 출력함. 18.6 풀이: 조세푸스 문제 조세푸스 문제는 연결 리스트로 풀 수 있는 전형적인 문제임. 한 사람이 죽을 때마다 포인터를 (K-1)번 옮기기 때문에, 전체 시간 복잡도는 O(NK)가 됨. 이 문제에서는 N, K가 모두 1000 이하의 값이기 때문에 충분히 시간 안에 수행할 수 .. 2021. 6. 22.
알고리즘 문제 해결 전략2 18장 선형 자료 구조(1) 18.1 도입 일렬로 늘어선 같은 종류의 자료 여러 개를 저장하기 위한 가장 기초적인 자료구조는 배열. 동적 배열과 연결 리스트에 대해 다룸. 18.2 동적 배열 배열의 큰 문제 중 하나는 처음에 배열을 선언할 때 배열의 크기를 지정해야 함. 그 이상의 자료를 집어넣을 수 없다는 점임. 동적 배열은 배열이 갖는 다음과 같은 특성을 그대로 이어 받음. 원소들은 메모리의 연속된 위치에 저장됨. 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있음. 동적으로 할당받은 배열과 동적 배열은 서로 별개의 개념임. 동적 배열 클래스는 현재 배열의 크기와 동적으로 할당받은 배열을 가리키는 포인터를 다음과 같이 저장하고 있음. 메모리를 할당받을 때 배열의 크기가 커질 때를 대비해서 여유분의 메모리를 미.. 2021. 6. 22.
알고리즘 문제 해결 전략2 17장 부분 합(2) 17.2문제: 크리스마스 인형 산타 할아버지는 한 번 주문할 때마다, 주문한 상자에 있는 인형들을 모두 꺼내서 각각을 K명에게 정확히 같은 수만큼 나누어 주고, 남는 인형이 없도록 함. 17.3 풀이: 크리스마스 인형 두 가지의 서로 다른 부분 문제로 구성됨. 두 문제는 모두 부분 합을 이용해서 풀 수 있음. 어린이들에게 인형을 모두 나눠주려면 인형의 총수가 K의 배수여야 함. (psum[T] - psum[H-1]) mod K = 0 이것을 전개하면 psum[T] mod K = psum[H-1] mod K psum[]에서 중요한 것은 K로 나눈 나머지일 뿐이라는 사실을 알 수 있음. 따라서 이 문제는 psum[]을 아래와 같이 정의함. 이 아이디어는 이 문제를 해결하는 데 중심 역할을 함. 구입할 수 있.. 2021. 6. 21.
알고리즘 문제 해결 전략2 17장 부분 합(1) 17.1 도입 부분 합이란 별 것이 아니고, 배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열임. scores[]의 부분 합 psum[]의 각 원소를 다음처럼 정의할 수 있음. 별 것 아닌 단순한 아이디어이지만 부분 합은 종종 아주 유용하게 이용됨. 부분 합 계산하기 vector partialSum(const vector& a) { vector ret(a.size()); ret[0] = a[0] for (int i = 1; i < a.size(); ++i) ret[i] = ret[i - 1] + a[i]; return ret; } int rangeSum(const vector& psum, int a, int b) { if (a == 0) return psum[b]; ret.. 2021. 6. 21.
알고리즘 문제 해결 전략2 16장 비트마스크(4) 16.4문제:졸업 학기 졸업 필수 학점을 채우려면 전공 과목 N개 중 K개 이상을 수강해야 함. 각 과목의 정보와 앞으로 M학기 동안 개설될 과목의 목록이 주어질 때, 태우가 최소 몇 학기를 다녀야 졸업할 수 있느지 계산하는 프로그램을 작성하시오. 한 과목도 수강하지 않는 학기는 휴학한 것으로 하며, 다닌 학기 수에 포함되지 않음. 예제 입출력 설명 : 첫 학기에 0번 과목, 번 과목을 듣고, 두 번째 학기에 1번 과목을 들은 뒤, 네 번째 학기에 2번 과목을 들으면 됩니다. 세 번째 학기에는 2번 과목이 개설되지 않으므로 다니지 않아도 됨. 두 번째 테스트 케이스에서는 2번과 3번 과목이 서로 선수과목으로 지정되어 있기 때문에 두 과목은 들을 수 없습니다. 0번 과목을 듣기 위해 1번 과목을 미리 들어.. 2021. 6. 21.
알고리즘 문제 해결 전략2 16장 비트마스크(3) 16.3 비트마스크의 응용 예제 지수 시간 동적 계획법 배열 대신 정수로 집합을 표현하면 이것을 곧장 배열의 인덱스로 쓸 수 있따는 점을 이용함. 따라서 메모이제이션의 구현 또한 훨씬 간단해짐 에라토스테네스의 체 k번 원소가 참인지 알기 위해서는 k/8번째 원소의 k%8번째 비트가 켜져 있는지를 확인하면 됨. 실제로 비트마스크를 사용하는 부분은 isPrime(), setComposite() 임. inline bool isPrime(int k) { return sieve[k >> 3] & (1 > 3] &= ~(1 2021. 6. 21.
알고리즘 문제 해결 전략2 16장 비트마스크(2) 16.2 비트마스크를 이용한 집합의 구현 여섯 개의 원소를 갖는 집합 {1,4,5,6,7,9}을 표현하는 정수는 754임을 다음과 같이 알 수 있음. 피자집 예제 한 피자의 정보는 스무 종류의 원소만을 가지는 집합이 되고, 비트마스크를 이용해 표현할 수 있음. 공집합과 꽉 찬 집합 구하기 : 1 2021. 6. 21.
알고리즘 문제 해결 전략2 16장 비트마스크(1) 16.1 도입 현대의 모든 CPU는 이진수를 이용해 모든 자료를 표현함. 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 할 수 있음. 이와 같은 특성을 화용해 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크라고 부름. 비트마스크의 장점은 - 더 빠른 수행 시간 - 더 간결한 코드 - 더 작은 메모리 사용량 - 연관 배열을 배열로 대체 컴퓨터는 모든 정수형 변수를 이진수로 표현함. 컴퓨터가 표현하는 모든 자료의 근간이 됨. 2^(N-1)에 해당하는 비트를 최상위 비트(most significant bit)라고 부르고, 2^0을 나타내는 비트를 최하위 비트(least significant bit)라고 부름. 비트별 NOT연산은 정수 하나를 입력받아 켜져 있는 비트는 끄고, .. 2021. 6. 21.
Bipartite Match 알고리즘 - 그래프의 최대 이분 매칭은 두 간선이 같은 정점을 공유하지 않는 간선의 최대 집합으 ㄹ말함. #include #define MAX 1000 int countA, countB; int matchA[MAX]; int matchB[MAX]; int adj[MAX][MAX]; int visited[MAX]; int dfs(int a) { int b; if (visited[a]) { return 0; } visited[a] = 1; for (b = 0; b < countB; ++b) { if (adj[a][b] && (matchB[b] == -1 || dfs(matchB[b]))) { matchA[a] = b; matchB[b] = a; return 1; } } return 0; } int bipartiteM.. 2021. 6. 21.

티스토리툴바