본문 바로가기

백준756

백준 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.
백준 12001 자바 - Load Balancing (Bronze) (BOJ 12001 JAVA) 문제 : boj12001 일단 B를 기준으로 모두 살펴보게 되면 O(1,000,000^2)이 되므로 시간초과가 나게 된다. N이 100개밖에 안되므로, N을 기준으로 살펴보면 된다. 처음엔 N개를 입력받고 fence가 교차하는 지점을 모든 N개 지점의 (x+1, y+1)에 있다고 보고 그로 인해 나눠지는 4사분면을 카운팅하면 될꺼라고 생각했다. 예를들어 cow가 주황색 지점에 있는 다음과 같은 상태를 생각해보자. 그럼 다음과 같이 모든 지점의 (x+1, y+1) 지점을 기준으로 나눠보면 답을 찾을 수 있을꺼라 생각했다. 하지만 제출해보니 틀렸고, 반례를 찾아보니 다음과 같은 경우 불가하다. 위의 경우 다음과 같이 나누어야 한다. 어찌되었든 기존 아이디어인 각 지점의 (x+1, y+1)은 분명 맞는 아이디.. 2021. 12. 2.
백준 1365 자바 - 꼬인 전깃줄 (BOJ 1365 JAVA) 문제 : boj1365 이 단어를 제가 쓰게될줄은 몰랐는데.. 'Well-Known'한 문제이다. DP쪽엔 냅색류가 유명하듯, 이분탐색쪽도 뭔가 선 꼬인거에서 안꼬이게 최대치 이런 종류의 문제가 유명하다. 사실 이런 류의 문제를 접해보지 못했다면 아이디어를 떠올리기 힘들 수 있다. 아이디어는 어떨 때 꼬이는지를 확인해보면 된다. -> 간단히 순서대로 선을 이어줄 때, 직전에 들어왔던 입력값보다 작은 값이 입력되면 꼬이게 된다. 예를들어 아래와 같은 경우 좌측의 순서대로 우측에 매칭된 숫자는 1, 3, 4, 2가 된다. 이 때 꼬인 부분은 이전보다 작은 값이 들어온 [4, 2] 부분이 된다. 그럼여러 경우를 테스트 해보면, 위와 같이 서로 겹치지 않게(안꼬이게) 하려면 단순히 subsequence(1,3,.. 2021. 12. 1.
백준 15970 자바 - 화살표 그리기 (BOJ 15970 JAVA) 문제 : boj15970 제시된 x와 y를 색상을 기준으로 나눠서 생각해보자. 즉, 문제에서 제시된 예시는 다음과 같이 나눠서 볼 수 있다. 두 경우는 연관되는 경우가 없으므로 색상이 다르다면 따로 생각해도 상관없다. 이렇게 보면, 각 색상별로 각 지점에서 좌, 우로 가장 가까운 점을 선택하기만 하면 된다. 정렬을 한 후 이분탐색으로 쉽게 찾을 수 있다. 그럼 이럴 때 쓰기 딱 좋은 자료구조가 있는데 Binary Search Tree로 구현되어 있는 TreeSet이다. 일반적으로 set은 해당 값이 들어있는지 파악하는 용도로 많이 쓰지만(hashSet 처럼), TreeSet은 이분탐색트리로 구성되어 있고 알아서 정렬되어 들어가므로 ceilling과 floor도 쉽게 구할 수 있다. 즉, 그보다 높거나 낮.. 2021. 11. 30.
백준 12966 자바 - 턴 게임 2 (BOJ 12966 JAVA) 문제 : boj 12966 수학적인 문제는 좀 피했었는데 오랜만에 도전한건데 잘 풀어낸 것 같아 기쁨. 사실 문제만 보고는 감이 잘 안왔었는데, 일단 주어진 부분에 대해 생각나는 것 부터 차례대로 쳐내다보니 답을 구할 방법이 보였다. 1. 일단 n번째(문제에서 'i'로 설명한걸 글에서는 'n'으로 표현한다. 'i'로 글쓰면 1이랑 헷갈린다.) 턴에 승리한 사람이 얻는 점수는 2n-1이다. 만약 n = 5라고 한다면 아래와 같이 된다. 즉, 점수는 모든 홀수인 셈이다. 2. 우선 불가능한 경우부터 예외처리를 해보자. 문제에서 제시된 게임은 1번째부터 순서대로 계속 진행을 해야 하고, 중간에 둘 다 점수를 못얻는 경우가 없다. 따라서 x와 y를 더한 값이 홀수의 등차수열 합과 일치해야 가능한 경우이다. 뭔소.. 2021. 11. 29.
백준 20856 자바 - Tunnelbaneplatser (BOJ 20856 JAVA) 문제 : boj 20856 입력받은 a1, a2, a3, a4에 대해 확실한것부터 제거해나가면서 선택해가면 된다(그리디). 이하 설명에서 cnt는 결과값으로 출력할 변수이다. 1. a4값만큼 cnt에 더한다. (4명이니 그냥 바로 앉으면 된다. 다른 그룹과 같이 앉을 수 없다.) 2. 다음으로 a2값을 보자. a2는 a2혼자 혹은 a2+a2, a2+2*a1의 형태로 가능하다. a3와 앉을 방법이 아예 없다. 따라서 a2를 2로 나눈 몫만큼 cnt를 더하고, a2를 2로 나눈 나머지가 있다면 cnt를 하나 더 올려주면 된다. 이 때 a1이 2 이상이라면 a1 두 그룹과 같이 앉고, 아니면 a2 혼자 앉으면 된다. 근데 사실 어차피 a2랑 같이 앉을 수 있는건 a1 뿐이므로 a1이 음수가 되던말던 상관없이 .. 2021. 11. 28.
백준 1515 자바 - 수 이어 쓰기 (BOJ 1515 JAVA) 문제 : boj 1515 입력으로 주어지는 수는 최대 3000자리이고, 0~9까지는 10개이다. 그러므로 대충 생각해봐도 아무리 최악의 케이스라 할지라도 3000 * 10 = 30000 이내에서 모두 찾아질 것임을 알 수 있다. 그러므로 brute force로 입력받은 값을 첫 자리부터 확인하며 1부터 30000까지 입력으로 받은 값에 대입해보며 하나씩 찾아나가면 된다. 예를들어 290119을 보자. 첫 자리수부터 확인한다. 여기서 base라는걸 1로 두고, base를 1씩 증가시키며 쭉 매칭시키자. 우선 'base=1'은 현재 pointer가 보고있는 2와 겹치는게 없으니 다음으로 넘어간다. 'base=2'는 pointer와 동일하므로 찾은거다. pointer를 전진한다. 그리고 base가 현재 1자리.. 2021. 11. 28.
백준 2697 자바 - 다음수 구하기 (BOJ 2697 JAVA) 문제 : https://www.acmicpc.net/problem/2697 A와 같은 구성에 A보다 큰 수 중 가장 작은 수는 그리디로 해결할 수 있다. 사실 이건 그리디야! 하고 푼건 아니고, 규칙을 찾고보니 그리디 스러운 규칙이었다.ㅋㅋ 1. 수를 뒤에서부터 한 자리씩 보면서, 처음으로 수가 이전보다 작아진 지점을 찾는다. 해당 지점을 T라고 하겠다. 2. T위치 이전은 그대로 출력한다. 그리고 T 위치를 포함해, 그 이후 위치에 대해 나왔던 숫자들을 몇번씩 나왔는지 카운팅한다. 3. T 이후의 위치에 있는 수 중, T에 해당하는 수보다 크면서 가장 작은 수를 찾아 T의 위치에 넣는다. 4. 카운팅해둔 값을 가지고, 작은 숫자부터 차례대로 카운팅값 횟수만큼 출력한다. 설명하기가 애매하니 예시를 들어 .. 2021. 11. 26.

티스토리툴바