본문 바로가기

알고리즘, 자료구조55

Circular Queue Circular Queue Queue의 front에서 추가, 삭제시 O(N)이 걸린다는 것을 보완합니다. 1) List(연결 리스트) 이용해서 구현 #include #include using namespace std; list::iterator circularNext(list &l, list::iterator &it) { return next(it) == l.end() ? l.begin() : next(it); } list::iterator circularPrev(list &l, list::iterator &it) { return it == l.begin() ? --l.end() : prev(it); } list circle; int main() { for (int i = 1; i < 6; ++i) { .. 2019. 8. 27.
[Queue] 19.5 외계 신호 분석 이 문제는 종만북, '알고리즘 문제해결 전략 2' 에 나와있는 예제 입니다. RNG를 만드는 방법, 입력이 너무커서 한번에 넣지 못하니, 온라인 알고리즘을 만드는 법을 배웠습니다. 또한 구간합을 탐색하는 데 이미 계산한 것들을 queue에 push하여 담고, 필요없는 것들을 즉각적으로 pop하여 필요한 구간합만 계산하는 아이디어도 얻었습니다. #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; // 선형 합동 난수 생성기(Linear congruential random number generator) struct RNG { unsigned seed; RNG() : seed(1983) {} unsigned next() { unsig.. 2019. 8. 27.
19. [스택, 큐, 데크] 간단 정리 구현 1. 연결리스트 O(1) : 리스트 양쪽 끝에 추가와 삭제 O(N) : 임의의 노드의 할당, 삭제, 포인터 따라가기(traveling) 2. 동적 배열 스택 : 추가, 삭제 O(1) 큐 : rear(뒤) 부분 추가, 삭제 O(1) / front(앞) 부분 추가, 삭제 O(N) 따라서 circular queue(혹은 circular buffer)를 만들기도 함. (추가, 삭제 발생시 head와 tail을 변경) : O(1) 데크 : 둘다 O(1) 온라인 알고리즘 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘. 입력의 크기가 너무 커서 프로그램상에 올려놓을 수 없을 때 사용한다. 2019. 8. 27.
선형자료구조 1. 동적배열 - 원소를 순서대로 저장 --> 인덱싱(원소찾기)이 O(1) - 삽입, 삭제 O(N) - 원소들이 메모리에 연속해 배치되어 있어 CPU 캐시의 효율을 높여줍니다. capacity: 미리 여유있게 할당받은 메모리의 크기 = 배열의 용량 size: 배열의 원소 수 용량(capacity)이 꽉찼을 때, 배열에 새로운 원소를 추가하려면 아래 방식으로 재할당을 하여야 합니다. 더 큰 새 배열을 동적으로 할당받고, 기존 배열의 내용을 모두 복사한 다음, 배열에 대한 포인터를 바꿔치기(swap)해야 합니다. - append() 연산과, 성능 append() 연산을 여러번 할 때 배열의 최종크기가 얼마일지 미리 짐작할 수 있다면, 동적배열의 용량을 미리 늘려둠으로써 재할당 비용을 없앨 수 있습니다. --.. 2019. 8. 26.
[Disjoint Set] 1717 집합의 표현 예제입력 및 출력) 7 8 0 1 3 0 3 2 3 4 5 6 7 1 1 7 NO 0 7 6 0 3 2 3 4 5 6 6 1 7 1 NO 0 3 7 0 3 2 6 4 5 6 6 0 4 2 0 3 2 6 2 5 6 6 0 1 1 0 6 2 6 2 5 6 6 1 1 1 YES 이 문제를 풀기 위해서는 Disjoint Set을 공부하면 좋습니다. 집합을 표현하고 다루는 3가지 함수를 배워봅시다. Disjoint Set은 만드는 방법이 연결리스트와 트리가 있지만, Union(합집합), Find 의 성능이 트리가 더 우월합니다. 자료구조는 트리로 가정해봅시다. 1. makeset() {0}, {1}, {2}, ... , {n} 의 집합을 만들어봅시다. p[n+1] 배열을 만들고, p[x] = x 라고 하면, 예를.. 2019. 8. 26.
16. 비트마스크 (bitmask) 장점 - 더 빠른 수행 시간을 보장합니다. - 더 간결한 코드를 제공합니다. - 메모리 사용량을 줄일 수 있습니다. 즉, 더 많은 데이터를 미리 계산해서 저장해 둘 수 있습니다. 비트마스크를 자료 구조로 이용하는 방법 및 각종 트랙을 소개합니다. 용어정리 8bit를 예로들자면, 최솟값은 0이고, 최댓값은 1111 1111(2) = 255입니다. 20을 나타내는 비트를 최하위 비트(LSB, Least Significant Bit), 2N-1을 나타내는 비트를 최상위 비트(MSB, Most Significant, Bit) 라고 합니다. 어떤 비트의 위치가 1이면 해당 비트가 "켜져 있다"고 하고, 0이면 "꺼져 있다"라고 합니다. 연산 코드 두 정수 a, b를 비트 별로 AND 연산 a & b OR a XO.. 2019. 8. 12.
[1931] 회의실배정 11 1 4 / 3 5 / 0 6 / 5 7 / 3 8 / 5 9 / 6 10 / 8 11 / 8 12 / 2 13 / 12 14 회의실을 사용할 수 있는 회의의 최대 수를 구하라. 위 예시의 답은 (1,4), (5,7), (8,11), (12,14) 입니다. '그리디'하게 생각한 방법 중 하나는, 시작 가능한 회의 중에서 '종료시간'이 가장 빠른 것을 그 다음 회의로 배정하는 것입니다. (1, 4) (5, 7) (8, 11) (12, 14) 기준을 '회의시간'이 가장 짧은 것으로 잡으면 오답이 나옵니다. (1, 4) (5, 7) (12, 14) 이렇게 끝나기 때문입니다. 1. 종료시간이 가장 빠른 것을 고릅니다. 2. 이전 회의의 종료시간보다 시작시간이 늦은 것들 중 종료시간이 가장 빠른 것을 고릅니다.. 2019. 7. 29.
2217 로프 greedy 로 풀어봅시다. 예를 들어 로프의 정보가 다음과 같이 주어졌다고 합시다. 20 8 15 9 2 먼저 내림차순으로 정렬한 뒤, (그렇지 않으면 그리디하게 풀 수 없습니다.) 20 15 9 8 2 생각해봅시다. 1) 20 ans = 20 2) 20 15 현재 만들 수 있는 최대 중량 = 20 바뀐 최소 값(15)으로 만들 수 있는 최대 중량 = 30 ans = 30 3) 20 15 9 현재 만들 수 있는 최대 중량 = 30 바뀐 최소 값(9)으로 만들 수 있는 최대 중량 = 9 * 3 = 27 ans = 30 4) 20 15 9 8 현재 만들 수 있는 최대 중량 = 27 바뀐 최소 값(8)으로 만들 수 있는 최대 중량 = 8 * 4 = 32 ans = 32 5) 20 15 9 8 2 현재 최소인.. 2019. 7. 25.
1541 잃어버린 괄호 그리디 알고리즘으로 푸는 문제이다. 괄호를 무한히 맘대로 사용할 수 있다. -가 나온 뒤에 +가 나온다면 다 괄호로 묶고, -가 나온다면 새로 괄호를 시작하여 뒤에 +를 다 묶으면 된다. 즉 -가 나오면 그냥 다 빼주면 된다. 그 순간의 최적해가 전체의 최적해가 되는 구조인 문제. 논리적으로 이게 정답이 나올지 잘 생각해보아야 한다. 그게 보장이 된다면, greedy algorithm으로 해를 구할 수 있다. +는 상관없이 계속 더하면 되지만, -가 나오면 그 다음으로 나오는 수는 다 빼주면 된다. #include using namespace std; int main() { string s; getline(cin, s); bool minus_check = false; int start = 0; int a.. 2019. 7. 25.
1107 리모컨 현재 채널이 100이고, 이동할 채널이 5457 일때, #include #include #include #include int check(int); using namespace std; int X[10]; int ans, N, M; int main() { scanf("%d%d", &N, &M); for (int i = 0; i < M; ++i) { int n; scanf("%d", &n); X[n] = 1; //고장난애들 } ans = abs(100 - N); for (int i = 0; i 2019. 7. 21.
728x90

티스토리툴바