본문 바로가기

알고리즘, 자료구조/알고리즘29

[Deque] 1021 회전하는 큐 문제에 나온 그대로 하면 풀리는 문제이다. M 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.
[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.
[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.
1018 체스판 다시 칠하기 일일이 다 해보면 된다. 단순반복 노동은 한 번만 그 원리를 알면, 나머지는 정말 쉽다. 특히 반복할 때 컴퓨터는 절대 실수하지 않는다. 8x8의 크기의 filter로 체스판을 자르고 올바른 체스판으로 만들기 위해 뒤집어야할 횟수 중 최소가 되는 것을 고른다. 추가 테스트 케이스 9 9 WBWBWBWBB BWBWBWBWB WBWBWBWBW BWBWBWBWB WBWBWBWBW BWBWBWBWB WBWBWBWBW BWBWBWBWB WBWBWBWBW #include char a[52][52]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i=0; i 2019. 7. 18.
[brute-force] 1436 영화감독 숌 N 2019. 7. 16.
[brute-force] 2798 블랙잭 블랙잭 100가지 중에 3가지를 고르는 경우의 수는, 10C3 = 161,700 경우의 수 별로 없으면 컴퓨터의 무식하고 빠른 연산을 살려서 모든 경우를 체크하여 보자. 가능한 조합을 모두 고르는 함수를 마침 공부하였다! sum = 0 인 상황에서 m - sum = 0 && d.. 2019. 7. 15.
728x90

티스토리툴바