본문 바로가기

전체 글1047

백준 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.
백준 1590 자바 - 캠프가는 영식 (BOJ 1590 JAVA) 문제 : boj1590 n개의 경우 각각에 대해 만족하는 가장 작은 시각을 찾아보면 된다. n개의 경우 각각에 대해 a가 0부터 C-1까지의 자연수라고 할 때, 다음 식을 통해 나온 값 중 최초로 T 이상의 값이 나오는 경우가 해당 경우의 최소수치이다. n개에 대해 각각 위의 최소수치를 구하고, 그 중 가장 작은 값이 답이다. 이 때 C는 최대 100 이므로 0부터 99까지 전부 다 해봐도 최대 O(NC) 정도의 시간복잡도이므로 전부 다 해보면 된다. 따라서 브루트 포스이며, 최초로 T 이상의 값이 나올 경우 바로 중지하면 되고 추가로 f(a)가 이미 이전에 나온 값보다 큰 경우엔 더이상 볼 필요도 없으므로 백트래킹도 가미하면 좀 더 효율적으로 할 수 있다. 코드에서 while문 내의 's < t'부분이.. 2022. 2. 6.
백준 1287 자바, 파이썬 - 할 수 있다 (BOJ 1287 JAVA, Python) 문제 : boj1287 사실 계산기 구현이니 난이도 때문에 플래라고 보긴 힘든 문제이다. 다만 파이썬으로 날먹하지 않는 이상은 빡구현이 필요하므로 티어가 높아진듯하다(총 1000자리가 입력으로 주어지므로, 500자리 곱하기 500자리와 같은 큰 수 연산이 필요하다). C로는 더 심한 빡구현이 필요해서 도전한 사람이 아직 없는듯하다 ㅋㅋㅋ 1. 우선은 날먹부터 일단 대충 봐도 한방에 계산해주는 무언가가 있다면 날먹이 가능할것처럼 생겼다. 우선은 자바에서 시도를 해봤었다. 아래와 같은 코드인데, 자바스크립트 엔진을 가져와서 자바에서 쓸 수 있다. 그럼 자바스크립트의 eval 함수를 사용해서 바로 계산이 가능하다. ScriptEngineManager scriptEngineManager = new ScriptE.. 2022. 2. 5.
백준 23258 자바 - 밤편지 (BOJ 23258 JAVA) 문제 : boj23258 개인적으로 오늘 푼 플3 문제보다 몇배는 어려웠다. 심지어 플로이드 와샬 알고리즘을 정확히 이해해야 풀 수 있는 문제라고 추천을 받고 풀게되어서 일단 플로이드 와샬을 써야 한다는 점은 알고 풀게 되었는데 그런데도 엄청 해맸다 ㅠ 아무튼 플로이드 와샬을 써보려면 이 문제는 꼭 풀어봐야 할 것 같다. 플로이드 와샬을 이해하는데 도움이 되는 매우 좋은 문제라 생각한다. 1. '2^C 방울 이상 마시면 안된다'의 의미 우선 이 부분부터가 문제였다. 처음엔 뭔가 장난스럽게, 좀 더 복잡하게 보일려고 이렇게 작성했다고 생각했다. 그래서 2^X, 2^C에서 '2^' 부분은 때고 X, C로만 생각했는데 당연히 제대로 답이 안나왔다. 결론적으로 키 아이디어에 해당하는 부분으로 사실 Ce로 가는 .. 2022. 2. 4.
백준 15352 자바 - 욱제와 그의 팬들 (BOJ 15352 JAVA) 문제 : boj15352 1. 우선 '행동 2'만 존재할 경우 어떻게 풀 수 있을지 확인해보자. 입력으로 주어진 N개의 A값들에 대해 좌우로 인접한 항목이 같은 팬클럽 번호라면 그룹을 지어보자. 이 때, union-find를 사용하고 부모가 되는 노드에 차수를 입력해둔다고 한다면 '행동 2'에 대해 O(1)로 부모의 차수를 출력하는 것 만으로 결과를 낼 수 있다. 예를들어 parents[a]에 대해 parents[a] >= 0일 경우 부모의 번호, parents[a] < 0일 경우 부모 중 하나이며, 그 부모에 그룹지어져 있는 노드의 개수라고 하면 예제 입력 1은 다음과 같이 나타낼 수 있다. union-find의 사용방법은 다양한 편이므로, 어쨌든 해당 그룹에 포함된 개수를 한방에 알 수만 있도록 짜면.. 2022. 2. 4.
백준 2688 자바 - 줄어들지 않아 (BOJ 2688 JAVA) 문제 : boj2688 방법 1. dp로 풀기 dp[a][b]를 a개의 수를 가지고 표현할 때 마지막 수가 b일 경우의 수 라고 정의하자. 그럼 이 문제에 대한 dp 점화식은 다음과 같다. 즉, 개수가 하나 더 작은 경우에서(dp[a-1]), 자신보다 작은 경우들에다가 자기 자신을 붙여주면 된다. 예를들어서 현재 b가 3일 경우 001과 113뒤에 3을 붙여 0013, 1133을 만들면 조건을 만족한다. 이 점화실을 a는 1부터 입력받은 n까지, b는 0부터 9까지 진행하면 된다. 그리고 여기에 prefix sum 까지 살짝 넣어주면 시그마를 없애서 시간 복잡도를 좀 더 간소화 시킬 수 있다. 거기에 미리 최대치인 a=64까지 계산해두고, 각 T개의 n개마다 dp[n][0]+dp[n][1]+...+dp[.. 2022. 2. 3.

티스토리툴바