본문 바로가기

BOJ75

[BOJ]2668번: 숫자고르기 문제: https://www.acmicpc.net/problem/2668 유형 태그가 다양한 걸 보니 푸는 방법은 다양한 것 같습니다만, 싸이클 찾기 문제로 해결했습니다. N = 100이니 직접 하나씩 뽑아보면서 탐색하면 터지는 건 자명합니다. 문제 예제를 보면 표에서 첫번째 줄에 5번 칸이 -> 5로 가는 걸 볼 수 있습니다. 이걸 보고 자기 자신의 숫자를 가지는 애들이 정답 갯수에 포함된다면, 정답으로 뽑히는 애들은 싸이클 성질을 가지고 있다는 걸 알았습니다. 즉, 이 문제는 가장 큰 싸이클을 구하는 문제입니다. 싸이클을 찾는 방법은 위상정렬을 통해 해결하였습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2668.cc 2020. 6. 26.
[BOJ]13549번: 숨바꼭질 3 문제: https://www.acmicpc.net/problem/13549 다익스트라로 해결하였습니다. 특정 좌표 X에서 수빈이가 움직일 수 있는 위치는 세 가지 입니다. 1. X-1 2. X+1 3. 2X 다익스트라로 해결한 이유는 두 배씩 뛰는 좌표의 경우 시간의 영향을 받지 않습니다. 그러므로 그냥 단순히 방문했다고 visited[] 배열을 true / false로만 표시한다면 더 빠른 시간에 특정 좌표 X에 도착해도 이미 visited[] 이 true라면 다시 탐색할 수 없습니다. 그러므로 큐에서 늦게 나온 값이라도 이미 저장되어있는 visited[] 시간보다 빠르면 갱신해줍니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ13549.. 2020. 6. 20.
[BOJ]12837번: 가계부 (Hard) 문제: https://www.acmicpc.net/problem/12837 쿼리랑 N 제한이 큽니다. O(NQ)에 처리하면 터집니다. 구간합, 갱신 쿼리를 O(logN)에 처리하기 위해 세그먼트 트리로 해결합니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ12837.cc 2020. 6. 17.
[BOJ]1654번: 랜선 자르기 문제: https://www.acmicpc.net/problem/1654 parametric search 문제입니다. 랜선의 하한: 1 랜선의 상한: 2^31 - 1 랜선의 상한 ~ 하한에 대한 임의의 길이 값을 기준으로 "N개의 랜선을만들 수 있다면 TRUE, 만들 수 없다면 FALSE" 입니다. 임의로 정한 랜선의 길이가 길어질 수록 만들 수 있는 랜선의 갯수는 작아지고, 랜선의 길이가 짧아질수록 만들 수 있는 랜선의 개수는 늘어납니다. 이런 구간의 연속성이 성립하기 때문에 랜선의 하한 ~ 상한의 범위를 선형 탐색이 아닌 이분 탐색으로 훑을 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1654.cc 2020. 6. 9.

티스토리툴바