본문 바로가기

백준23

[BFS] 2206 벽 부수고 이동하기 #include #include using namespace std; struct Pos { int x, y, b; }; queue q; char a[1001][1001]; int dist[1001][1001][2]; int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}; int main() { int n, m; scanf("%d %d", &n, &m); for (int i=0; i 2019. 9. 12.
[백준] 1694 숨바꼭질 BFS를 잘 활용하면 되는 문제. 그래프를 잘 생각 해보자. 각 숫자들을 그래프의 노드라고 했을 때, 1만큼 떨어진 이웃하는 숫자는 양방향 간선으로 다 이어져 있고, x노드에서 2x노드로 가는 간선들이 있다. BFS는 모든 정점과 간선을 살펴보는 알고리즘이므로 시간복잡도는 O(|V| + |E|)인데, V = 100,000, E < 300,000 이면 충분할 거라고 생각했다. 참고로 memset에 사이즈를 sizeof(d)/sizeof(int) 라고 했다가.... 수없이 실패를 했던 문제이다. 나머지는 최단거리를 구하는 BFS문제로 직관적으로 쉽게 풀 수 있다. #include #include #include using namespace std; int d[100001]; int main() { int n.. 2019. 9. 12.
[이진탐색] 1920 수 찾기, Binary search Binary search는 '정렬된 배열'에서 특정 원소를 찾을 때, O(logN)의 탐색시간을 보장합니다. 따라서, O(N)만큼 걸리는 Linear search 보다는 성능이 좋을 수 있습니다. 처음에는 재귀함수로 구현하였고, 이와 거의 비슷하게 반복문으로 구현할 수 있었습니다. #include #include int a[100001]; // array는 정렬되어 있어야 함. int binarySearch(int first, int last, int k){ int mid = (first + last) / 2; if (first > last) return -1; else { if (a[mid] == k) return mid; else { if (a[mid] < k){ binarySearch(mid + 1.. 2019. 8. 29.
[Deque] 5430 AC (백준) Deque의 성질을 잘 활용해야 하는 문제. 이것을 데크를 무시하고, 리버스를 처음에 그대로 구현했다가.. 시간초과가 났다. p의 길이의 합과 n의 합이 70만을 넘지 않다는 것이지... p x n 이 70만을 안 넘는 것은 당연히 아니었다. 리버스 있는 그대로 해서 하는 순간 reverse가 O(N)이라고 가정하면, 전체 수행시간이 O(PN)이 되어 10억, 즉 10초 정도로 시간초과가 난다. 그래서, 아이디어는 리버스했을 때 front인지 rear인지 설정을하고 각각 pop_front, pop_back을 해주면된다. 개념적으로는 참 쉬운데, 문자열 다루는데 익숙하지 않았던지 푸는데 너무 오래걸렸다. string 객체의 substr을 잘 이용해보았다. string s; s = "2019.08.28" i.. 2019. 8. 28.
[Deque] 1021 회전하는 큐 문제에 나온 그대로 하면 풀리는 문제이다. M 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.
[brute-force] 1436 영화감독 숌 N 2019. 7. 16.
728x90

티스토리툴바