백준

이번 문제는 임의의 진수와 해당 진수로 이루어져 있는 값을 입력받아 10진수로 변환하는 문제이다.예를 들어 8진수 77은 이진수로 1 1 1 1 1 1이고(8진수는 2진수를 3자리씩 자름, 2진수로 8은 111) 10진수로 변경하면 63이다. $8^1 * 7 + 8^0 * 7 = 63$  성공 소스public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); ..

이번 문제의 핵심은 이전에 점프한 거리보다 1이상 더 긴 거리를 뛴다는 것과 밟을 수 있는 징검다리의 최대 개수를 구하라는 것이다. 문제 내용에 2번째 규칙은 "두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다"이고 이 문장을 통해 등차수열인 것을 알 수 있으므로 등차수열의 합 공식을 사용하면 된다. 등차수열 합 공식$ \frac{n(n + 1)}{2} $밟을 수 있는 징검다리의 최대 개수를 구하는 문제이기 때문에 등차수열의 합이 입력 n보다 작거나 같은 수 중에 최댓값을 찾으면 된다. 예를 들어 징검다리가 10개인 경우 1, 2, 3, 4번 징검다리를 건너가면 해결된다. 입력의 범위가 $10^{16}$이기 때문에 자료형은 int가 아닌 long으로 선언하였고 반복문으로 수..

해당 문제를 읽자마자 우선순위 큐를 검색해 보았다. 우선순위 큐는 힙 구조이고 힙은 완전이진트리의 일종이며 완전이진트리는 마지막 레벨을 제외하고 모든 레벨이 채워져 있는 트리 형태라고 한다. 우선순위 큐와 힙 자료구조에 대해서는 나중에 공부를 해야겠다고 넘기고 우선순위 큐의 사용법만 숙지하고 문제를 풀기 시작했다. 우선순위 큐는 비교 기준이 필요하고 비교하기 위해 Comparator를 구현해야 했고 나는 문서의 중요도를 내림차순으로 정렬되도록 구현하였다.(우선순위 큐는 삽입, 제거 시 남은 원소들과 비교하여 반정렬 상태를 유지한다. 자세한 건 나중에 직접 구현해 보면서...) private static class Printer { int index; int priority; public ..

2024년 3월 11일 백준 알고리즘 골드를 달성하였다.   골드 달성 후기 작성 이유 나는 백준 알고리즘 사이트에서 브론즈 2 ~ 실버 4 난이도에 해당하는 문제들을 풀면서 알고리즘 문제 풀이에 있어 목표를 어떻게 설정해야 하는지 알기 위해 골드 달성 후기를 검색했던 적이 있었다. 지금 생각해 보면 당장 가까운 목표로 잡은 골드라는 티어에 대해 높게 생각하여 마음속에 있는 부담감을 해소하기 위해 여러 자료들을 찾아봤던 것 같다.이처럼 과거의 나와 비슷한 생각을 하고 있거나 이 게시글을 보고 있는 사람 중 알고리즘 학습에 대해 걱정이 되는 사람이 있다면 그럴 필요 없고 자신감을 가지라고 말하고 싶어 골드 달성 후기를 작성한다. 나는 머리가 좋은 편이 아니어서 의자에 앉아 있는 시간을 늘리려고 한다.실제로..

이 문제를 처음 봤을 때 어떤 방식으로 풀어야 하는지 25분 정도 고민을 한 것 같다. 왜냐하면 아래와 같은 방식이나 이와 유사한 방식만 생각이 들었기 때문이다.입력받은 K[i]들을 다 더한 후 N으로 나눈다.나눈 몫을 1씩 줄여가며 각 랜선의 길이에 나눈다(2중 반복문).나눈 몫을 누적하여 N과 동일할 때까지 반복한다.이러한 풀이는 시간복잡도가 $O(n*m)$ (사실상 $O(n^2)$)이라서 풀 수 없다.해당 문제는 시간제한이 2초이고 주어진 값의 범위가 $1    결론적으로 이 문제는 이분탐색 알고리즘을$O(\log_2 n)$ 사용하면 해결된다.그러나 주의할 점이 있다. 문제 해결 시 주의사항1. 오버 플로우를 조심해라.- 이분탐색 로직 중 left와 right 변수를 더할 때 $2^{31}-1$을 ..

이 문제는 M개의 수가 각각 A 배열에 들어있는 지 확인하는 문제이다. M개의 수가 최대 100,000개이고 시간제한은 1초이기 때문에 정렬 후 이진탐색 알고리즘을 사용하면 된다고 생각하였다.이진탐색의 시간복잡도는 $ \log_2 N $ 이다. $ 2^{16} = 65,536 $$ 2^{17} = 131,072 $$ 16   이진탐색 구현private static int[] arrSearch;private static int binarySearch(int num) { int left = 0; int right = arrSearch.length - 1; while(left num) { right = mid - 1; } else if (arrSearch[mi..

해당 문제에 대해 3가지 방법으로 풀어보았다.조합 공식 및 반복문 사용조합 공식 및 재귀(팩토리얼) 사용 dp 및 재귀 사용 처음 풀었을 때는 단순하게 조합 공식인 아래 공식을 사용하여 풀었다.  성공 소스 1 - 반복문public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer..