본문 바로가기

PS/BOJ764

백준 14584 자바 - 암호 해독 (boj 14584 java) 문제 : boj14584 26번에 걸쳐 각 문자를 하나씩 증가시켜보면서, 입력으로 들어온 N개의 문자가 있는지 판단해보면 된다. 예를들어 처음에 'abcd' 였다면, 하나씩 증가시킨단 말은 'abcd' -> 'bcde' -> 'cdef' -> ... 와 같은걸 의미한다. 'arr[j] = (char)('a'+((arr[j]-'a'+1)%26));' 부분이 해당 역할을 한다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new Inpu.. 2022. 4. 10.
백준 9612 자바 - Maximum Word Frequency (boj 9612 java) 문제 : boj9612 String에 대해 카운팅을 해야 한다. 따라서 HashMap 등을 사용하면 쉽게 계산할 수 있다. 주의점은 동일한 횟수가 존재할 경우, 사전순으로 뒤에 있는걸 택해야 한다. 코드에서 이하의 부분이 해당 역할을 한다. maxStr.compareTo(cur) < 0 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in).. 2022. 4. 9.
백준 10090 자바 - Counting Inversions (boj 10090 java) 문제 : boj10090 n개를 입력받으면서 매번 입력받은 값이 k라 하면, 매번 이전까지 나온 수 중 k보다 큰 수가 몇 번 나왔는지만 알면 된다. 머지소트트리, 세그먼트트리, 제곱근 분할법이 이걸 알 수 있는 자료구조들이다(물론 더 있을 수 있다). 별다른 응용없이 해당 자료구조 중 아무꺼나 적용하면 풀리는 문제라 셋 중 맘에 드는걸로 검색해서 배워보자! 개인적으로 구현 난이도는 제곱근 분할법 < 머지소트트리 2022. 4. 8.
백준 4659 자바 - 비밀번호 발음하기 (boj 4659 java) 문제 : boj4659 풀이가 딱히 필요없다. 주어진 대로 구현할 수 있는 구현력(?)만 있으면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private int type(char c) { switch (c) { case'a': case'e': case'i': case'o': case'u' : return 1; default: return -1; } } private boolean checkIt(String s) { for (int i = 0; i < s.length(); i++) { if (type(s.charAt(i)) == 1) break; if (i == s.le.. 2022. 4. 8.
백준 2041 자바 - 숫자채우기 (boj 2041 java) 문제 : boj2041 배열이랑 반복문만 알면 풀 수 있는 순수 아이디어 문제인데도 다이아 티어를 받은 무서운 문제이다. 별다른 알고리즘적 지식이 필요하지 않으므로 풀기 전에 이 글을 보면 얻어갈 수 있는건 아이디어 뿐이다. 따라서 밑으로 내려 풀이를 보자마자 스포가 되므로, 최대한 스스로 풀어보고 풀이를 보는걸 추천한다(하지만 스스로 풀어봤다면 더이상 풀이가 필요없지) 백준1187번을 같이 풀었던 선배같은 후배와 같이 풀었다. 1187때는 결국 난 못풀었고 후배의 도움으로 풀 수 있었지만 이번엔 내가 먼저 풀이를 찾았다. 기분 좋다. ----- 풀이 스포주의 ----- 내 경우엔 여러 방식으로 해보다가, 결국 해답을 찾은 키 아이디어는 배열에 어떤 수가 들어갈지 고민하기 보다, 차이를 어떻게 배치할지 .. 2022. 4. 7.
백준 2163 파이썬 - 초콜릿 자르기 (boj 2163 python) 문제 : boj2163 쪼갠걸 겹쳐서 자를 수 없으므로, 결국 한땀한땀 자를 수 밖에 없다. 그럼 n x m 조각에 대해 n을 높이, m을 너비라고 생각해보자. 이걸 우선 가로방향으로 n개로 쪼개보자. 이 경우 n-1번 쪼개면 된다. 그리고 그 중 한 개만 세로방향으로 쪼개보자. m-1번 쪼개면 된다. 그런데, m-1번 쪼갠게 처음 n-1번 쪼갠 n개의 조각 하나이므로 총 n개의 조각을 m-1번 쪼개야 한다. 따라서 처음에 가로로 쪼갠 경우, 답은 n-1 + n(m-1) 이 된다. 그럼 처음에 세로로 쪼갠 경우는 어떻게 될까? m-1 + m(n-1)이 된다. 근데 둘다 식을 풀어보면 전자는 n-1+nm-n = nm-1 후자는 m-1+mn-m = nm-1 이다. 따라서 어느쪽을 먼저 자르더라도 nm-1이 .. 2022. 4. 6.
백준 9613 자바 - GCD 합 (boj 9613 java) 문제 : boj9613 우선 모든 쌍을 확인하는게 이 가능할지 확인해보자. n은 최대 100 이므로 모든 쌍을 확인할 경우 O(n^2)이 필요하고, 총 t개의 테스트케이스가 존재하므로 O(100*100^2) 이므로 충분히 가능하다. 그럼 뭐 어렵게 생각할 것 없이 무지성으로 모든 쌍을 확인해보면 된다. 모든 쌍 확인은 예를들어 배열의 길이가 5일 경우 인덱스는 0,1,2,3,4가 존재할 것이다. 그럼 0-1, 0-2, 0-3, 0-4, 1-2. 1-3. 1-4, 2-3, 2-4, 3-4 와 같이 확인하면 된다. 코드의 27~28line을 참고해보자. 그리고 모든 쌍에 대해 각각 GCD를 구해 그 결과를 더해주면 되는데, GCD의 경우 유클리드 호제법을 사용하면 빠르게 구할 수 이다. 유클리드 호제법은 검.. 2022. 4. 6.
백준 1486 자바 - 등산 (boj 1486 java) 문제 : boj1486 ※ 블로그 만들기 이전에 깃헙에 텍스트로만 작성해둔 풀이라 그림도 없고 다른 글들과 말투가 다릅니다. 날잡고 옮겨야지 생각은 했는데 블로그 만들기 이전에 푼게 900개정도 이기도 하고, 요즘 푸는거 풀이 작성하기도 빡쌔므로 아무래도 전부 새로 작성해서 옮길 시간을 없을 것 같아서 틈틈히 그냥 깃헙에 적어둔 텍스트로만 된 풀이라도 옮겨둘 생각입니다. 모든 위치에서 시작할 수 있는게 아니고, 딱 0,0 지점에서 출발이 가능하므로 결국 0,0에서 모든 지점으로의 거리와 모든 지점에서 0,0으로의 거리를 알면 solution 함수처럼 D 이내의 왔다가 다시 오는 거리 중 가장 높이가 높은걸 찾으면 됨. 그럼 결국 위에서 말한 2가지만 구할 수 있으면 되는데, 플로이드 와샬로 한방에 구해도.. 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.

티스토리툴바