본문 바로가기

전체 글1042

백준 14428 자바 - 수열과 쿼리 16 (BOJ 14428 JAVA) 문제 : boj14428 가장 간단하게 생각할 수 있는 방법인 brute force부터 확인해보자. 10만개의 N개가 주어지고, 모든 쿼리가 '2 1 100000' 이런식이라면 O(NM)이 필요할 것이다. 따라서 시간내에 통과할 수 없다. 사실 이런식으로 중간중간 값이 변경되고, 범위에 대한 쿼리를 출력하는 유형은 대표적으로 세그먼트 트리(segment tree)를 사용하는 문제이다. 내 경우엔 조금 더 비효율적이지만, 훨씬 간단하고 구현을 이해하기 편하다고 생각되는 sqrt decompositon 방식을 사용해서 풀어봤다. 1. Sqrt decomposition 초기화 (코드의 init 함수) 이론적으론 세그먼트 트리에 비해 이해하기가 엄청 간단하다. 특정 수열이 N개의 수를 가진다면 N의 제곱근만큼 .. 2022. 2. 13.
백준 6219 자바 - 소수의 자격 (BOJ 6219 JAVA) 문제 : boj6219 1. 우선 A, B 사이의 소수를 어떻게 효율적으로 구할까? 에라토스테네스의 체 방식을 사용하여 미리 구해두면 된다. 이 때 내 경우엔 좀 더 효율적으로 하고자 sqrt(n)까지만 확인(왜 그래도 되는지는 여기를 확인해보면 된다.)하고, 짝수는 굳이 안봐도 되므로 아예 확인하지 않는 등의 약간의 추가 처리가 들어가있다. 코드에서 getPn()을 확인해보면 된다. 2. 다음으로 어떠한 정수가 있을 때 해당 수에 숫자 D가 포함되는지 어떻게 알 수 있을까? 가장 간단하게는 해당 정수를 String으로 변환하고 숫자 D도 character로 변경해서 확인해보는 방법이 있다. 당연히 좀 비효율적이다. 좀 더 빠르게 하려면 나머지 연산과 나누기 연산을 사용하면 된다. 어떠한 n에 대해 n%.. 2022. 2. 12.
에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 흔히 에라토스테네스의 체를 사용해 n 이하의 모든 소수를 구하려고 할 때, 효율적으로 구하기 위해 n의 제곱근( sqrt(n) ) 까지만 확인하곤 한다. 1년전쯤엔 n까지 다 확인하거나, 좀 머리 쓴다고 n/2까지 확인했었다. 그런데 당시에 sqrt(n)까지만 본다는 획기적인 말을 들었고, 증명을 찾아봤었다. 증명을 어디서 봤는진 정확히 모르겠다. 아무튼 자주 쓰이다보니 현재까지도 기억하고 있고, 중간중간 블로그에 해설을 적을 때 에라토스테네스가 나올때 마다 작성하기 귀찮아서 따로 글을 쓰게 되었다. 최대한 쉽게 작성해보겠다. n 이하의 모든 소수를 구한다고 해보자. 이 때 해당 수 n은 자연수 a, b에 대해 n = a * b 라고 표현할 수 있다. -> 예를들어 12는 2*6 혹은 3*4 등으로 나타.. 2022. 2. 12.
백준 2358 자바 - 평행선 (BOJ 2358 JAVA) 문제 : boj2358 이번년도에 푼 것중 가장 쓰레기 문제였다. 사실 블로그를 작년 말에 개설 후 '쓰레기'란 단어 자체를 처음 사용하고 있다. 혹시 풀 문제를 찾고 계시는 분이라면 이 문제는 미리 패스하시고, 맞왜틀 때문에 찾아오신 분이라면 잘 찾아오셨다. 다음의 2가지를 확인해보면 풀 수 있을 것이다. 1. '서로 다른 두 점을 선택하면 하나의 직선이 만들어진다. 이와 같이 직선을 만들었을 때, x축 또는 y축에 평행한 직선이 몇 개' -> 이렇게 해두면 당연히 combination으로 생각될 것이다. 즉 입력이 1 0 2 0 3 0 이라면 1 0 - 2 0 / 2 0 - 3 0 / 1 0 - 3 0 이렇게 해서 3개라 생각(3C2)하고 풀고있었을 것이다. 하지만 어이없게도 이 문제에서는 이게 아니.. 2022. 2. 11.
백준 11653 파이썬 - 소인수분해 (BOJ 11653 Python) 문제 : boj11653 소수들로 소인수 분해 후 그 결과를 오름차순으로 출력하면 되는 문제이다. 바로 생각날 부분은 우선 소인수 분해를 위한 소수를 구하기 위해 에라토스테네스의 체를 사용해 N이하의 소수를 구한 후, 작은 소수부터 차례대로 나눠보면서 나눠지면 출력하는 방식이다. 하지만 에라토스테네스의 체를 계산하는데도 사실 O(N)정도의 시간이 필요하며, 이 문제에서는 N이 하나만 주어지므로 굳이 사용하지 않아도 된다. 만약 TC가 여러개였다면 물론 미리 소수를 구해두는게 이득이었을 것이다. 이 문제의 경우 그냥 2부터 N까지의 수로 직접 N을 나눠보면서 나눠지는 수를 출력하기만 하면 된다. 코드 : github import sys input = sys.stdin.readline n = int(inpu.. 2022. 2. 10.
백준 13211 자바 - Passport Checking (BOJ 13211 JAVA) 문제 : boj13211 hashset의 개념을 안다면 바로 풀 수 있다. 혹시 모를 경우 brute force로는 O(NM) 이므로 풀 수 없다. 그러니 정렬 후 이분탐색 O(NlogN + MlogN)으로 풀면 된다. 하지만 정렬 후 이분탐색을 아는 사람이 hashset의 개념을 모를리 없으므로 사실상 해시로 풀면 되는 문제이다. 이 경우 O(N+M) 이 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; public class Main { private void solution() throws Exception { BufferedReader br = new Buf.. 2022. 2. 10.
백준 1544 자바 - 사이클 단어 (BOJ 1544 JAVA) 문제 : boj1544 최대 50길이의 String이 최대 50개 주어진다. 그럼 매번 단어가 주어질 때 마다 해당 단어의 사이클 단어를 전부 미리 만들어둔다고 해도, 최대 50x50 = 2500개의 단어밖에 나오지 않는다! 따라서 그냥 복잡하게 생각할 것 없이 2500개를 전부 만들면서 모든 단어끼리 비교해보면 된다. 로직은 다음과 같다. 1. n개의 ArrayList를 생성한다. 2. i번째 단어를 입력받을 시 i번 단어로 만들 수 있는 모든 사이클 단어를 만들어서 i번째 ArrayList에 집어넣는다. 3. 1번째부터 i-1번째 ArrayList들을 각각 전부 순회하며 동일한 단어가 있었는지 확인한다. 4. '3'에서 없었다면 cnt를 1 증가시킨다. i를 1 증가시키며 i가 n이 될때까지 2~4를.. 2022. 2. 9.
백준 18126 자바 - 너구리 구구 (BOJ 18126 JAVA) 문제 : boj18126 N이 최대 5000이고, 간선도 각 노드마다 최대 5000개 이므로 O(N^2)으로만 해도 충분하다. 따라서 그냥 dfs로 모든 경우를 확인하고, 그 사이에 나온 거리들 중 가장 큰 값을 출력하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; class Edge { int to, c; public Edge(int to, int c) { this.to = to; this.c = c; } } public class Main { long answer = 0; int n; Arra.. 2022. 2. 8.
rsync를 사용해서 Synology NAS로 데이터 자동 백업하기 (리눅스용) rsync를 사용해서 시놀로지NAS(이하 NAS)에 로컬 혹은 서버의 데이터를 백업하는 방법에 대해 작성한다. 목차 [ Synology NAS 설정 ] 1. 주의점 Synology NAS에서는 quickconnect로 로컬망에 있는 NAS도 외부에서 쓸 수 있도록 해준다. 하지만 rsync를 통한 백업의 경우 quickconnect로 불가하므로, 외부망에서 사용하려면 별도로 작업이 필요하다. 2. NAS에서 rsync 서비스 활성화 NAS 관리자 권한 계정으로 접속 후 '제어판 -> 파일 서비스 -> rsync -> rsync 서비스 활성화 및 포트 작성' 외부망에 열려있는 NAS라면 특히 포트는 기본 포트보다는 변경하는것이 좋다. 3. 백업용 유저 생성 기존 유저로 해도 되겠지만, 아무래도 백업용으로 .. 2022. 2. 8.
백준 16208 자바 - 귀찮음 (BOJ 16208 JAVA) 문제 : boj16208 1. 우선 그냥 풀어보자. 결국 현재 막대 크기를 x+y로 나눌 수 있을 때, 비용인 xy들의 합을 최소로 하고 싶은 것이다. 그렇다면 수학적으로 최대한 '작은수 x 큰수'가 되도록 하는것이 최소이다. '중간수 x 중간수'일수록 손해이다. 예를들어 현재 길이가 10일 경우 5x5는 25지만 1x9는 9다. 또한 맨 마지막 막대는 비용이 0이므로 (x+0 이므로 xy = 0) 결국 주어진 n개의 쇠막대를 길이가 짧은 순서대로 나누면 된다(그리디 알고리즘). 내 경우엔 어차피 a_i 0) { int cur = Integer.parseInt(st.nextToken()); cnt[cur]++; sum += cur; } long answer = 0; for (int i = 1; i 0) .. 2022. 2. 7.

티스토리툴바