본문 바로가기

분류 전체보기1105

백준 4386 자바 - 별자리 만들기 (BOJ 4386 JAVA) 문제 : boj4386 1. 모든 별을 이어야하고, 최소 비용을 구해야 한다. 따라서 N개의 정점(별)에 대해 이은 간선이 N-1개(모든 정점을 포함하려면 최소 N-1개의 간선이 필요하고, 최소비용을 위해서는 거기서 하나라도 간선이 추가되선 안되므로) 이어야만 모든 별을 이으면서 최소 비용이 가능하다. 따라서 Spanning Tree를 구성해야 하고, 최소 비용이어야 하므로 MST (Minimum Spanning Tree)를 구하는 문제임을 알 수 있다. 후보군이 될 간선은 N개에 대해 다른 N-1개 모두로의 간선이므로 간선은 총 N*(N-1)개 존재할 수 있다. 이 중 N-1개를 골라 MST를 만들었을 때의 최소 비용이 답이다. 2. 대표적인 MST 알고리즘에는 Prim과 Kruscal이 있다. 이 문.. 2022. 1. 12.
백준 14248 자바 - 점프 점프 (BOJ 14248 JAVA) 문제 : boj14248 문제 자체의 정의에 따라 i번째 정점에서 i-Ai, i+Ai 로의 간선이 생긴다. 이에 대해 단순히 방문 가능한 위치만 찾으면 되므로 dfs 혹은 bfs로 더이상 진행 불가할때까지 진행해보면서 방문한 곳의 개수를 세면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { boolean[] v; int cnt = 0, n; int[] arr; private void dfs(int s) { if (sn||v[s]) return; v[s] = true; cnt++; dfs(s+arr[s]); dfs(.. 2022. 1. 11.
백준 11060 자바 - 점프 점프 (BOJ 11060 JAVA) 문제 : boj11060 N이 1000까지이고, Ai가 최대 100이라 대충 돌려도 O(NA = 100000) 이라 널널한 문제이다. 가장 좌측지점부터 시작해서 dp 개념을 살짝 섞은 브루트포스로 풀면 된다. 각 입력값에서 갈 수 있는 모든 곳을 가보면서 최소로 갈 수 있는 수치로 갱신해가면 된다. dp[x]는 x위치까지 갈 수 있는 최소 점프 횟수가 된다. 점화식은 Ai에서 i=x에서 시작해 우측으로 이동한 경우이고 현재 y (x+1 2022. 1. 10.
백준 2331 자바 - 반복수열 (BOJ 2331 JAVA) 문제 : boj2331 무작정(brute force) 계속 D[n]을 구해나가면서 이전에 이미 나왔던 결과가 다시 나오는지 확인만 하면 된다. 이 때, 중복된 값은 해싱을 통해 찾으면 빠르게 찾을 수 있다. 추가로 중복값이 나왔을 때 해당값의 위치가 몇번째였는지를 알아야 남게되는 수들의 개수를 출력할 수 있다. 따라서 HashMap을 사용해서 이미 나왔던 수와 해당 수가 몇번째에 나왔는지를 기록해두면 이후 중복된 값이 계산되었을 때 바로 남은 수의 개수를 알 수 있다. (중복값이 나온 위치 이전의 모든 값들이 남은 수들이 된다.) 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Hash.. 2022. 1. 9.
백준 9847 자바 - 4SUM (BOJ 9847 JAVA) 문제 : boj9847 1. Brute Force로 가능한가? 4개의 수의 합이 0이 되는 경우를 찾아야 한다. 제일 간단하게 생각해보면 모든 쌍을 보면 된다. 이 경우 O(500^4) 이므로 유효한 시간 내에 찾을 수 없다. 2. 문제를 단순화 해보자 그럼 우선 문제를 단순화해서 생각해보자. 세트가 2개만 존재한다고 생각해보자(각 세트에 들어간 수는 N개). 그럼 각 세트에서 하나씩 골라서 2개의 수의 합은 어떻게 찾을 수 있을까? 모든 경우를 보는 O(N^2)보다 더 빠른 방법이 있을까? 두 세트가 X와 Y라고 한다면, X의 수를 정렬한 후 Y의 모든 수를 순회하면서 X에 대해 이분탐색으로 합이 0이 되는 경우를 찾을 수 있을 것이다. 그럼 O(NlogN[정렬] + N[순회]*logN[이분탐색]) 정.. 2022. 1. 8.
백준 20949 자바 - 효정과 새 모니터 (BOJ 20949 JAVA) 문제 : boj20949 원하는 방식으로 정렬하는 방법만 알면 쉽게 풀 수 있는 문제이다. 이 문제의 경우 쿼리로 따지면 ORDER BY [W^2+H^2 값] DESC, IDX ASC 인 셈이다. 이 때 W^2+H^2은 W와 H가 모두 최대 3만이므로 두 합은 최대 18억으로, int형으로 표현 가능한 수치이다. 당연하게도 문제에서 square root가 있다고 루트 씌우고 계산하면 소수점 오차때문에 틀릴 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Monitor implements Co.. 2022. 1. 6.
자바로 백준 풀 때의 팁 및 주의점 (boj java) 백준에서 자바로 1000문제정도 풀었다. 자바로 백준을 풀면서 어느정도 코드를 최적화 시킨 부분도 있고, 모르면 통과 못하는 경우들도 있어서 생각나는대로 작성해본다. 1. 클래스명은 'Main', 패키지는 없어야 한다. 이런식으로 package없이 클래스명을 Main으로 두고 작성해야 한다. IDE에서 작성할때 Version Control을 위해 따로 둘 수는 있겠으나, 어쨌든 제출할 때는 저렇게 해야 한다. 또한 제출 시 당연히 import 부분도 같이 넣어줘야 한다. 2. Main 이외의 클래스를 추가로 쓰고싶다면 public이 아닌 클래스 혹은 Inner 클래스를 쓰면 된다. 아무튼 public class는 무조건 Main 이어야하고, public class는 하나여야 한다. 3. main 함수에서.. 2022. 1. 6.
백준 1298 자바 - 노트북의 주인을 찾아서 (BOJ 1298 JAVA) 문제 : boj1298 기본 형태의 이분매칭 문제이다. 그러니 푸는법을 모르겠다면 이분매칭에 대해 구글링해보면 풀 수 있다. 얼핏 이분 그래프가 아닌 것 같아 이분매칭을 적용하지 못한다고 생각할 수 있으나, 제시된 N이 결국 N명의 사람과 N개의 노트북 두개 모두를 뜻하므로 N개의 사람 정점과 N개의 노트북 정점이 이분 그래프를 이루게 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Main { StringTokenizer st; B.. 2022. 1. 6.
우분투 20.04(WSL) 마리아 DB 서버 설치 방법 (wsl ubuntu mariadb server) 1. 설치 버전 확인 여기를 클릭해서 mariadb의 설치가이드로 이동한다. 2. 우분투 버전 확인 방법 위 이미지의 'A' 항목을 원하는 항목으로 변경한다. 'Choose a MariaDB Server version'은 원하는 마리아DB 버전을 선택하면 된다. 'Choose a distribution' 부분은 마리아 db를 설치할 우분투의 버전이다. 다음의 명령어를 통해 확인 가능하다. cat /etc/os-release 3. 마리아 DB 설치 진행 '1'의 이미지에서 B 부분을 복사하여 우분투에서 실행한다(우측 상단의 버튼을 누르면 복사가 되고, 그냥 우분투에서 붙여넣기 한다음 엔터 누르면 된다.) 그리고 C 부분도 마찬가지로 실행한다. 4. 마리아 DB 실행 및 기본 설정 이제 마리아 DB를 실행하.. 2022. 1. 6.
백준 2188 자바 - 축사 배정 (BOJ 2188 JAVA) 문제 : boj2188 완전 기본형태의 이분 매칭 문제이다. 이분 그래프임이 직관적으로 드러나므로 이분매칭 개념을 알고있다면 기본형 문제로 풀어볼만 하다. '예제 입력 1'을 그려보면 다음과 같다. 이분 매칭된 결과 중 최대로 매칭 시킬 수 있는 경우의 예시는 다음과 같다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Main { ArrayList[] edges; private int[] matched; private boolean[] .. 2022. 1. 5.

티스토리툴바