본문 바로가기

백준744

백준 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.
백준 자바로 1000 문제 자축용 글 예아! 그리고 처참한 기하학.. 다야까지 ㄱㄱ 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.

티스토리툴바