본문 바로가기

PS831

백준 14413 자바 - Poklon (BOJ 14413 JAVA) 문제 : boj14413 1. update가 없는 쿼리 문제로, 오프라인 쿼리로 처리해도 된다. 또한 각 쿼리마다 범위가 계속 변경되는 와중에 원하는 답을 구하는 쿼리 문제이다. 따라서 mo's algorithm을 사용할 경우 효율적으로 풀 수 있다. 모스 알고리즘은 쿼리의 수가 n이고 각 쿼리 qi = (a, b)라 할 때(문제에선 l, r이었음. l이 헷갈려서 a, b로 변경하여 설명함), 모든 쿼리를 (a/sqrt(n), b) 순서로 정렬하게 된다(a/sqrt(n)은 소수점 버리고 정수로). 이 경우 각 쿼리를 정렬 후 수행 시 모든 경우에 대해 a와 b의 변화량이 최대 N*sqrt(N) 정도로 고정되고, 효율적으로 직전에 구해둔 쿼리의 데이터 중 중복되는 부분을 재사용할 수 있다. 예를들어 q1=.. 2021. 12. 11.
백준 7585 자바 - Brackets (BOJ 7585 JAVA) 문제 : boj7585 괄호를 제외한 나머지 문자는 모두 쓸모없다. 예를들어 '예제 입력1'은 다음과 동일한 데이터이다. 이제 올바른 괄호쌍인지만 판단하면 되는데, 스택을 사용하면 간단하다. 1. 여는 괄호 (, {, [ 를 만날 시 스택에 해당 괄호를 넣는다. 2. 닫는 괄호 ), }, ] 를 만날 시 스택에서 하나를 pop한다. pop한 결과가 동일한 형태의 여는 괄호가 아닐 경우 (예를들어 ']'에서 pop을 하니 '('가 나온 경우) Illegal이다. 3. 최종적으로 1, 2의 과정을 문자열 끝까지 진행하고 스택에 남은게 아무것도 없다면 Legal, 뭐라도 남아있다면 쌍이 안맞는 것이니 Illegal이다. 코드 : github import java.io.BufferedReader; import .. 2021. 12. 11.
백준 14382 자바 - 숫자세는 양 (Large) (BOJ 14382 JAVA) 문제 : boj14382 INSOMNIA인 경우부터 생각해보자. 일단 각 자리 중 1~9중 어느 수라도 들어가면 배수에서 모든 수가 나타날 수 있다. 따라서 INSOMNIA인 경우는 n이 0인 경우 하나 뿐이다. 그 외의 경우는 실제로 n, 2n, 3n, ...을 해보면서 각 자리수에 포함된 숫자들을 찾아내어 모든 수를 찾았는지 확인하면 된다. 모든 수를 찾는 것은 미리 0~9까지를 넣은 해시를 준비해두고 찾을 때 마다 remove 후 size를 확인해봐도 될테고, 내 경우엔 remain=10 과 boolean 배열을 두고 새로운 수를 찾으면 remain을 감소시켜서 remain이 0이 되면 모두 찾은것으로 판단했다. 코드 : github import java.io.DataInputStream; impo.. 2021. 12. 10.
백준 1011 자바 - Fly me to the Alpha Centauri (BOJ 1011 JAVA) 문제 : boj1011 다른 사람 코드들을 보니 규칙을 찾아 수식으로 해결한 경우가 많은 것 같다. 내 경우엔 그리디로 해결했다. x에서 y로 가면서 '최소값'을 구해야 한다. 이 경우, 최선의 선택은 x에서 1로 시작해 무조건 +1로만 진행하는 것이다. 점점 가속해야 가장 최선의 선택임이 자명하다. 하지만 문제는 y에서 도착할 때도 1이어야 한다. 그렇다면 최선의 선택은 다음과 같다. x에서 계속 +1씩 증가하면서 진행하고, y까지도 계속 -1씩 감소시키면서 감속시키는 것이다. 그럼 반대로 바꿔서 저 '?' 부분을 향해 x와 y에서 동일한 속도로 진행해서 만난다고 생각해보자. 그럼 x쪽에서1, y쪽에서1 -> x쪽에서2, y쪽에서2 -> x쪽에서3, y쪽에서3 이동.. 이런식으로 보면 되겠다. 이 때 .. 2021. 12. 8.
백준 14003 JAVA - 가장 긴 증가하는 부분 수열 5 (BOJ 14003 JAVA) 문제 : boj14003 8달전에 못풀고 키핑해뒀던 문제인데, 이번에도 못풀 뻔 했다가 겨우 풀었다. 확실히 플래는 아직 많이 까다롭다. 일단 가장 긴 증가하는 부분 수열의 길이 자체는 이분탐색을 활용한 LIS 알고리즘을 쓰면 얻을 수 있다. 하지만 LIS 알고리즘은 가장 긴 증가하는 부분 수열의 '길이'를 파악할 뿐이고, 이 문제에서는 가능한 수열 중 하나를 출력하는 방법도 찾아야 한다. LIS 알고리즘은 나름대로 잘 알려진 알고리즘이므로 제외하고, 수열 자체를 찾는 방법에 대해 써보겠다. 1. LIS 알고리즘에서 입력이 10 20 30 5 15 가 들어오면 어떻게 될까? 최종적으로 LIS의 길이인 '3'은 구해낼 수 있으나, 배열에는 다음과 같이 '5 15 30' 이라는 값이 들어가 있게 된다. 실제.. 2021. 12. 8.
백준 22865 자바 - 가장 먼 곳 (BOJ 22865 JAVA) 문제 : boj22865 설명이 좀 부족한 부분이 있는 문제이다. 일단 문제 이해부터 해보자. 예제 입력 1을 그래프로 그려보면다음과 같다. 위 그래프를 기반으로 어떠한 X 지점에서 시작해서 모든 정점으로 가는 최단거리를 구해보겠다. 이 때, 시작하는 정점인 X는 각각 A,B,C 이다. 예를들어 C인 5번 정점에서 시작할 경우 3번정점까지의 최단거리는 '7'이다. A,B,C로의 거리를 알아야 하는데 왜 A,B,C에서 시작하는 거리를 잰 것인지 궁금할 수 있다. 이 문제의 경우 무방향 그래프에서 진행되므로, A에서 모든 정점으로 가는 최단거리는 모든 정점에서 A로 가는 최단거리와 동일하다. 문제에서 미흡한 부분이, X가 A,B,C가 될 수 있는지 없는지 명확히 제시하지 않았다는 점이다(어차피 시작점들은 거.. 2021. 12. 7.
백준 2839 자바 - 설탕 배달 (BOJ 2839 JAVA) 문제 : boj2839 가장 작은 수의 봉지를 사용해야하므로 '5'를 최대한 많이 쓸수록 이득이다. 그리고 '정확히' n킬로그램을 선택해야한다. 따라서 최상의 선택인 '5'짜리 봉지를 'n/5'개 사용하는 것부터 시작해서 '5'짜리 봉지를 0개 까지 확인해보면서, 남은 설탕이 '3'짜리 봉지로 정확히 나눌 수 있다면 해당 지점이 최선의 선택이다. (그리디) 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamRea.. 2021. 12. 6.
백준 23801 자바 - 두 단계 최단 경로 2 (BOJ 23801 JAVA) 문제 : boj23801 한 점에서 모든 점으로의 최단거리를 알 수 있는 알고리즘 중에 다익스트라 알고리즘이 있다. 이 문제의 경우, x에서 p개의 점 중 적어도 하나를 방문한 후 z까지 가야 한다. 그럼 다익스트라로 x부터 다른 모든 점으로의 거리를 찾아도 답을 구할 수 없다. 이 문제의 경우 z점으로 들어가는 모든 지점의 거리도 알 수 있어야 한다. 이것도 다익스트라를 응용해서 할 수 있는데, 무방향 그래프라면 z에서 시작하는 다익스트라를 돌려도 그 결과가 모든 점에서부터 z로 향하는 최단거리와 동일하다. (참고로 방향이 있는 그래프일 경우에도 다익스트라로 모든 점에서부터 한 점으로의 최단거리를 구할 수 있는데, 모든 간선의 방향을 역방향으로 바꾼 후 다익스트라를 돌리면 된다.) 1. X에서 모든 점.. 2021. 12. 6.
백준 9081 자바 - 단어 맞추기 (BOJ 9081 JAVA) 문제 : boj9081 이하 설명은 이해의 편의를 위해 숫자로 설명해보겠다. 실제로 이 문제를 풀때도 문자를 아스키코드를 기준으로 변경해서('A'~'Z'까지 나오므로 각각을 숫자 0~25로 대입) 풀어야 한다. 내 풀이는 그리디 이다. 1. 문자를 뒤에서부터 보면서, 같거나 증가하는 경우는 계속 진행하고 처음으로 더 작아진 경우를 찾는다. (문자로 따지면 ADCB라면 D->A일 때 작아진다.) 이하 그림에서는 9->3이 처음으로 작아진 부분이다. 처음으로 숫자가 감소하는 부분에 나왔던 '3'에 해당하는 위치를 T라고 적겠다. 2. T위치와, 그 이후에 나온 숫자를 몇 번씩 나왔는지 카운팅한다. 이하 그림에서 idx 부분이 실제 숫자에 대입된다(문자라면 'A'~'Z'까지 카운팅하면 된다.) 예를들어 idx.. 2021. 12. 5.
백준 4882 자바 - 정규형 (BOJ 4882 JAVA) 문제 : boj4882 지문에 제대로 낚였다.. 문제를 잘못이해해서 꽤 오래동안 맞왜틀 외치고 있었다. ㅠ 가장 깊은 레벨부터 AND로 지정하고, 이후 올라갈수록(레벨 숫자가 낮아질수록) AND - OR - AND - OR - ... 이렇게 지정해야 하는 문제였다. 문제 예시에서 '가장 위'가 AND라고 멋대로 생각해버린데다가 한글 번역본에서 '가장 낮은 레벨에 있는 트리는 AND 트리'라고 해버려서 당연히 '낮은' 레벨이니깐 레벨1부터 AND라고 계속 생각하고 맞왜틀 외치고 있었음 ㅡㅡ; 심지어 예제도 그렇게 풀면 다 맞다;; 결론적으로 도저히 내 코드에 문제점을 못찾겠어서 혹시나하고 영어 원본으로 보고 알아채고 맞출 수 있었다('The trees at the deepest level are AND-t.. 2021. 12. 2.

티스토리툴바