본문 바로가기

전체 글1068

[종만북] FESTIVAL - 록 페스티벌 (자바 java) 문제 : FESTIVAL N이 최대 1000 이므로 O(N^2)의 알고리즘이라도 충분히 통과할 수 있다. 따라서 단순히 차이가 L 이상인 모든 구간에 대해 O(N^2)으로 확인해주면 된다. (코드의 24~25 line 참고) 주의점은 10^(-7) 이하의 절대/상대 오차가 있어야 하므로, 그냥 바로 출력하면 안되고 소수점 8자리 이상을 출력하도록 해야 한다. 자바의 경우 String.format("%.8f", answer)과 같은 코드로(c언어와 비슷한 출력 방식) 소수점 8자리까지 출력할 수 있다. 그리고 모든 구간에 대해 직접 더해봐도 시간 제한에 충분히 맞출 수 있긴 하지만(O(N)), prefix sum을 미리 구해둘 경우 [a, b] 구간의 합은 arr[b]-arr[a-1] 과 같이 O(1)로 .. 2022. 4. 5.
백준 1486 자바 - 등산 (boj 1486 java) 문제 : boj1486 ※ 블로그 만들기 이전에 깃헙에 텍스트로만 작성해둔 풀이라 그림도 없고 다른 글들과 말투가 다릅니다. 날잡고 옮겨야지 생각은 했는데 블로그 만들기 이전에 푼게 900개정도 이기도 하고, 요즘 푸는거 풀이 작성하기도 빡쌔므로 아무래도 전부 새로 작성해서 옮길 시간을 없을 것 같아서 틈틈히 그냥 깃헙에 적어둔 텍스트로만 된 풀이라도 옮겨둘 생각입니다. 모든 위치에서 시작할 수 있는게 아니고, 딱 0,0 지점에서 출발이 가능하므로 결국 0,0에서 모든 지점으로의 거리와 모든 지점에서 0,0으로의 거리를 알면 solution 함수처럼 D 이내의 왔다가 다시 오는 거리 중 가장 높이가 높은걸 찾으면 됨. 그럼 결국 위에서 말한 2가지만 구할 수 있으면 되는데, 플로이드 와샬로 한방에 구해도.. 2022. 4. 5.
분할 정복을 이용한 거듭제곱 최적화 아마 다음은 이미 알고 있을 것이다. 예를들어 거듭제곱되는 수치가 짝수일 때와 홀수일 때를 예로들면 다음과 같다. A^4 = (A^2)^2 (짝수일때) A^5 = A * A^4 = A * (A^2)^2 (홀수일때) 만약 A^8이 있다면 원래는 A*A*A*A*A*A*A*A 으로 곱셈 연산을 7번 해야 하지만, A^8을 ((A^2)^2)^2 으로 변경하면 A*A=A', A'^2=A'' 이라 할 시 최종적으로 A'을 구하는데에 A*A로 곱셉 한번, A''=A'*A'을 구하는데도 마찬가지로 곱셈 한번, 최종적으로 A''*A''을 구하는데 곱셈 한 번이 들어간다. 즉 7번의 연산이 3번의 연산으로 줄어든다! 즉, 거듭제곱을 위와 같이 계산한다면 원래 N번의 연산이 O(logN)으로 줄어든다. 여기서 분할정복을 활.. 2022. 4. 5.
백준 2749 자바 - 피보나치 수 3 (boj 2749 java) 문제 : boj2749 일단 10^18 이므로 그냥 구하기는 절대로 불가능한 수치임을 알 수 있다 ㅋㅋㅋ. 내 경우엔 피보나치의 경우 행렬의 거듭 제곱으로 풀 수 있다는걸 이미 알고 있었으므로 공식만 찾아서 풀었다. 공식은 f(n)이 n번째 피보나치라 할 때, 아래와 같다. 이 때 거듭 제곱의 계산은, 분할 정복을 활용해서 O(logN)에 빠르게 구할 수 있다. 예를들어 A^8 = ((A^2)^2)^2 임을 활용하는 것이다. 혹시 모른다면 예전에 백준 게시판에 답글달았던 이 글을 참고하면 된다. 그보다, 다른분의 풀이도 보다보니 '피사노 주기'라는 것도 알게 되었다. 피보나치 수를 어떠한 수로 나눈 나머지는 항상 주기성을 가진다고 한다. 수의 세계는 신비로운 것 같다. 코드 : github import .. 2022. 4. 5.
백준 1072 자바 - 게임 (boj 1072 java) 문제 : boj1072 결국 n판 진행 후의 확률 차이가 1이면 n이 답이므로, 다음의 식을 구하면 풀 수 있는 문제이다. 이 때 x와 y는 이미 주어진 수치이므로 n에 대한 1차식이긴한데.. 난 수학적 지식이 딸려서 저걸 'n=~~' 형태로 변경할 수가 없었다 ㅠㅠㅠ 그러므로 좀 더 무식한 방법으로 진행했다. 직접 해보는거다 ㅋㅋ 우선 '만약 Z가 절대 변하지 않는다면 -1을 출력' 부분부터 예외처리하고 넘어가야 한다. 간단히 말해 맨 처음 확률이 99%거나 100%면 변경될 수 없다. 이 경우 -1을 출력해주면 된다. 다음으로는 간단히 100y/x를 구한 후, 해당 수치가 변경될 때 까지 n을 한땀한땀 증가시키면서 100(y+n)/(x+n)을 구해나가면 된다... 는 사실 이러면 시간초과가 난다. 생.. 2022. 4. 5.
백준 1644 자바 - 소수의 연속합 (boj 1644 java) 문제 : boj1644 소수의 연속합인걸 일단 생각 안하고 그냥 어떠한 자연수로 이루어진 배열이 있고, 연속한 배열의 부분합이 N인걸 찾는다고 생각해보자. 일단 단순히 모든 범위를 보려면 O(N^2) 이므로 통과할 수 없다. 그렇다고 DP로 풀자니 식이 잘 떠오르지 않았다. 보통 이런류의 연속합은 투포인터를 활용하면 쉽게 찾을 수 있다(원래는 통과할 방법 찾기 전에 대충 어떠한 수가 소수의 연속합으로 몇 번 정도 나오는지 궁금해서 대충 짜보고 돌린건데 통과했다 ㅋㅋ). 투포인터 전략만 잘 세우면 된다. st와 ed라는 두 포인터를 두고 [st, ed] 구간에 포함된 합을 계속 계산하고 있다고 해보자. 시작은 st와 ed 둘 다 배열의 첫번째에 둔다. 이 경우 ed가 증가(다음 칸으로 전진)되면 합이 늘어.. 2022. 4. 5.
백준 15927 자바 - 회문은 회문아니야!! (boj 15927 java) 문제 : boj15927 혹시 고민을 많이 했다면, 풀이를 볼 시 상당히 짜증날 수 있다. 스포성이 다분한 풀이 이므로 최대한 직접 풀어보는걸 추천한다. ------ 입력으로 들어온 문자열은 이하의 3가지 경우가 존재한다. A. 애초에 팰린드롬이 아님 (e.g. 'abcd') B. 팰린드롬이긴한데, 모든 문자열이 동일함 (e.g. 'aaa') C. 모든 문자열이 동일한게 아닌 팰린드롬 (e.g. 'aabaa') 각각 어떻게 처리할지 살펴보면 된다. A -> 처음부터 팰린드롬이 아니므로 가장 긴 팰린드롬이 아닌 부분문자열은 자기 자신이다. 따라서 입력 문자열의 길이를 출력하면 된다. B -> 이 경우 부분문자열 중 팰린드롬이 아닌게 존재할 수 없다. 따라서 -1을 출력하면 된다. 참고로 'a' 와 같이 문.. 2022. 4. 4.
백준 1337 자바 - 올바른 배열 (boj 1337 java) 문제 : boj1337 문제 분류는 정렬과 투 포인터 있긴한데, 내 경우엔 그냥 정렬 없이 그리디로 풀었다. 어떠한 수를 추가할 생각을 하는 것 보다는 그냥 추가해야될게 있던 없던 있다고 치고 해봤을 때, 원래 존재하던게 몇 개 있었는지 확인해 보는 것이 더 간단한 방식일 것이다. 그러니깐 그냥 해당 배열에 있는 값을 HashSet에 모두 넣어서 O(1)로 원하는 수를 찾을 수 있도록 해두고, N개의 수에서 현재 보고 있는 원소의 값을 a라고 하자. 그럼 모든 N개의 a값에 대해 a, a+1, a+2, a+3, a+4를 해시셋에서 확인한다. 그럼 존재하지 않는게 몇갠지 알 수 있다. 그 값 중 가장 작은게 답이다. 예를들어 '예제 입력 4'를 보자. 7 6 1 9 5 7 15 8 이걸 다음과 같이 구해볼.. 2022. 4. 3.
백준 18868 자바 - 멀티버스 Ⅰ(boj 18868 java) 문제 : boj18868 주어진 대로 구현하면 되긴 한다. 내 경우엔 입력받은 값을 전처리해서 좀 더 쉽게 만들었다. 각 우주에 있는 모든 행성의 모든 쌍에 대해 순서대로 규칙을 만들어 하나의 String으로 만들었다. 예를들어 어떤 우주에 4개의 행성이 있었다면 1-2, 1-3, 1-4, 2-3, 2-4, 3- 4 순서대로 모든 쌍을 비교한다. 그래서 "+-+=++"와 같은 형태의 해당 우주의 모든 행성의 크기 규칙에 대한 String을 만드는 것이다. 그럼 최종적으로 M개의 String에 대해 모든 쌍을 확인 했을 때 동일한 String을 가진 행성이 몇 쌍 존재하는지만 확인하면 되는 문제로 변경된다. 즉 모든 쌍에 대한 단순 비교 로직 2개만 있으면 풀 수 있으므로 구현의 복잡도가 많이 줄어든다. .. 2022. 4. 2.
백준 3029 자바 - 경고 (boj 3029 java) 문제 : boj3029 H시간은 H*60*60초 이다. M분은 M*60초이다. S초는 S초이다. 따라서 입력으로 주어진 hh:mm:ss 두 개는 간단히 둘 다 00:00:00부터 몇 초 후인지로 변경할 수 있다. 예를들어 다음의 예시를 보자. (예제 입력 2에서 위아래를 바꾼 예시이다.) 14:36:22 12:34:56 이 때 현재 시간인 14:36:22는 52582초, 나트륨을 던질 시간인 12:34:56은 45296초가 된다. 전자를 st, 후자를 ed라고 해보겠다. 이 때 ed-st를 한다면 기다리는 시간을 알 수 있을 것이다. ed-st = -7286이 된다. 그 말인 즉, 나트륨을 던질 시간은 하루 뒤였다는 얘기이니 (현재 시간의 다음날 12:34:56) 24시간을 더해주면 된다. 즉, ed가 .. 2022. 4. 2.

티스토리툴바