전공
-
백준 1389(케빈 베이컨의 6단계 법칙 ) 플로이드 와샬전공/알고리즘 2020. 6. 15. 13:52
https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻�� www.acmicpc.net 가장 적은 거리로 연결되는 index를 찾는 전형적인 그래프 문제. dfs로 풀었지만 dfs를 이용해서 풀었을 때 정확한 시간복잡도 계산도 모르겠고, 해서 다른 알고리즘을 찾아보았다. 플로이드 와샬 모든 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘 a->b로 가는 최단 경로를 알아보려면, (a -> b) vs (a->c + c->b) 이..
-
백준 1012(유기농 배추) 그래프전공/알고리즘 2020. 6. 10. 14:33
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 엄청나게 쉽다고 생각한 문제 엄청나게 틀린 문제 대충 보자마자 방법을 알아챘다. 좌표를 입력받을 때마다 인접한 곳에 대해서 확인 후에 있으면 그 당사자 좌표를 갯수에서 빼주는 것이다. 그렇게 바로 코드를 짰고, for (int i = 0; i > a >> b; bug[a + 1][b + 1] = true; if (bug[a + 1][b + 2]) cnt++; else if..
-
백준 1461(도서관) 맞왜틀?전공/알고리즘 2020. 6. 9. 13:20
맞는데 왜 틀렸지? 라는 생각을 갖게된다. 나의 논리가 완벽하기에 나를 너무 믿기에 자꾸 틀린걸 알면서도 제출버튼을 클릭하고 제출한다. 알고리즘 문제를 풀다보면 논리의 허점을 찾기가 정말 힘들다. 단순 예제를 만들어서 확인해볼 생각도 안 하고, 확인했던 것만 확인하고 틀린다. 멍청 이 문제도 그랬다 그냥 결론은 딱히 없고 예제좀 제대로 넣고 풀어보자 처음부터 논리적으로 완벽하긴 더 힘들거 같으니깐 제발 https://www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치� ww..
-
백준 1080(행렬)전공/알고리즘 2020. 6. 8. 14:38
https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 문제를 정말 잘 읽어봐야 하는 문제. 이 문제에서 N*M의 행렬을 3*3의 부분행렬의 값을 1->0 0->1 로 변경하여 A와 B의 행렬이 같게 만드는 문제이다. 처음에 부분행렬이라고만 봐서 모든 부분행렬을 따져봐야 되나 이런 생각을 해보았다. 전체탐색으로 풀려고 했다. 왜냐하면 행렬의 변환이 무작위라고 느껴졌기 때문이다. 전체탐색 재귀로 풀게된다면 시간복잡도는 O(2^n)이므로 2^50, 약 10^17 엄청난..
-
백준 1541(잃어버린 괄호)전공/알고리즘 2020. 6. 8. 12:46
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 어떤 +, -와 숫자로 이루어진 수식을 입력받아서 괄호를 마음대로 넣어서 최솟값을 만드는 문제이다. 좀만 생각해보면 -연산자 뒤에는 모두 -로 만들 수 있다는 것을 알 수 있다. 처음에는 전체로 입력받아서 하나하나 조사할 생각을 안 하고 하나하나 따로 입력 받을 수 있는 방법이 있는가라는 착각을 해서 문제를 더 어렵게 생각하게 만들었지만 그게 아니었다. 이 문제는 string 으로 수식을 입..
-
백준 2042(구간 합 구하기)전공/알고리즘 2020. 6. 6. 17:40
이 문제는 전형적인 세그먼트 트리 문제이다. 세그먼트 트리는 어떤 연속된 구간의 합 차 등 어떤 계산의 반복을 미리 쪼개어 놔서 시간을 월등히 줄여주는 자료구조이다. 특징은 완전 이진 트리로 구성되어 배열 자료구조를 사용하며 맨 위 노드의 index를 1로 잡아서 좌측 노드는 2*index, 우측 노드는 2*index+1이다. 위 특징을 이용해서 구현을 진행한다. 단순 계산으로는 O(쿼리의 횟수 * 배열의 크기) O(mn)의 시간복잡도가 세그먼트 트리로는 O(mlogn)로 줄어든다. 코드의 구성은 세그먼트 트리 구현, 쿼리 함수 구현 이렇게 나뉜다고 볼 수 있다. 세그먼트 트리의 구현은 n의 값이 2의 거듭제곱꼴이 아닌 어떤 자연수이므로, top - down 형식의 재귀적 방법을 사용한다. 앞선 문제에서..
-
백준 1725(히스토그램)세그먼트 트리전공/알고리즘 2020. 6. 6. 15:09
세그먼트 트리란 잘게 나누어서 많은 요청에 대해서 일처리를 빠르게 해주는 자료구조이다. 만약에 2 3 4 6 8 1 수열에 대해서 i ~ j번째까지의 합을 구하고 싶다고 한다면 O(n)의 시간이 소요될 것이다. 하지만 여기서 m번 x번째 수열의 값을 바꾸고 다시 계산을 한다고 하면 O(nm)의 시간이 소요된다. 보다 빠르게 계산을 하기 위해서 자료들을 구간별로 나누어서 저장한 뒤에 필요한 수들의 호출 횟수를 줄여서 계산을 진행한다. 세그먼트 트리는 완벽 이진트리로 구성되어서 어떤 수의 변경, 합은 O(log n)의 시간만큼 소요된다. 만약에 n,m의 값들이 커진다면 시간차이는 기하급수적으로 늘어날 것이다. 그래서 쿼리가 많을 때에는 세그먼트 트리를 사용한다. 세그먼트 트리는 세 단계로 나뉜다. 주어진 처..
-
백준 12846(무서운 아르바이트)스택전공/알고리즘 2020. 6. 5. 14:36
https://www.acmicpc.net/problem/12846 무조건 연속해서 일을 하고, 일한 날 중에서 일급이 가장 낮은 날을 기준으로 급여를 받는다. 단순하게 완전탐색으로 n^2의 시간이 걸리게 풀 수 있다. 겨울 스터디 모의고사때 오기로 계속 틀렸던 기억이난다. 하지만 시간이 1초로 불가능했고, 1초안에 풀려면 세그먼트 트리랑 스택으로 풀어야한다고 한다. 이 문제는 가장 큰 히스토그램 문제와 일치하는 문제이다. (백준 6549) https://www.acmicpc.net/problem/6549 스택으로 구현하는 것은 단순 이것을 위한 알고리즘이라는 느낌이 마구 들어서 이걸 이용해서 다른 어떤 것으로 응용이 가능할지는 모르겠다. 스택에 pair로 위치와 높이를 저장한다. 조건을 걸어서 넣고 빼..