알고리즘

개요위 문제는 최대 연산의 수(M)가 3,000,000이기 때문에 반복문을 사용하면 안될 것 같아 HashMap 자료구조를 사용하여 문제를 해결하였다. 해당 문제를 해결한 후 다른 사람들이 어떤 방식으로 풀었는지 확인할 결과 비트마스크 알고리즘을 사용하여 푼 방식이 존재하여 필자는 아래 2가지 방법으로 문제를 풀어보았다. 성공소스1. HashMap 사용add: map의 containsKey와 put 메서드를 사용하여 x값을 추가한다.remove: map의 remove 메서드를 사용하여 x값을 제거한다.toggle: map의 containsKey 메서드와 put, remove 메서드를 활용한다.all: 반복문을 사용하여 1 ~ 20을 map에 put한다.empty: map의 clear 메서드를 사용한다.참..

이번 문제는 문제를 이해하는 데에만 시간이 좀 걸렸다. 처음에는 예제 입력 3번째 줄의 각 수를 8진수로 변환한 후 출력하는 것으로 알고 풀어 예제 출력 중 6이 아닌 4 2가 나와서 이상함을 느꼈다. 예제 입력을 정리하면 입력의 2번째 줄은 A진법 수의 자릿수의 개수를 나타내고 3번째 줄은 각 자릿수이다. 예를 들어 3번째 줄 첫 번째 입력인 2는 $2 * 17^1$, 16은 $16 * 17^0$이고 10진수로는 $34 + 16 = 50$이다. 그러므로 10진수로 변환한 50을 B진법으로 변환하면 해결된다.      성공 소스public class _11576 { public static void main(String[] args) throws IOException{ BufferedR..

이번 문제는 이전에 포스팅하였던 2745번 문제 풀이를 반대로 진행하면 된다. https://jiji-gilog.tistory.com/13 [백준] 2745번 : 진법 변환 - JAVA임의의 진수와 해당 진수로 이루어져 있는 값을 10진수로 변환하는 문제이다. 예를 들어 8진수 77은 이진수로 1 1 1 1 1 1이고(8진수는 2진수를 3자리씩 자름, 2진수로 8은 111) 10진수로 변경하면 63이jiji-gilog.tistory.com  10진수를 임의의(B) 진수로 변환하는 방법은 10진수 값(N)을 B로 나누고 나머지를 출력하면 된다.예를 들어 8을 2진수로 변환한다고 하면 8을 2로 몫이 0이 될 때까지 나누는 작업을 반복하며 나머지를 저장하고 역순으로 출력하면 된다. 해당 문제는 10진수를 임..

이번 문제는 임의의 진수와 해당 진수로 이루어져 있는 값을 입력받아 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 난이도에 해당하는 문제들을 풀면서 알고리즘 문제 풀이에 있어 목표를 어떻게 설정해야 하는지 알기 위해 골드 달성 후기를 검색했던 적이 있었다. 지금 생각해 보면 당장 가까운 목표로 잡은 골드라는 티어에 대해 높게 생각하여 마음속에 있는 부담감을 해소하기 위해 여러 자료들을 찾아봤던 것 같다.이처럼 과거의 나와 비슷한 생각을 하고 있거나 이 게시글을 보고 있는 사람 중 알고리즘 학습에 대해 걱정이 되는 사람이 있다면 그럴 필요 없고 자신감을 가지라고 말하고 싶어 골드 달성 후기를 작성한다. 나는 머리가 좋은 편이 아니어서 의자에 앉아 있는 시간을 늘리려고 한다.실제로..

해당 문제에 대해 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..