Java

이번 문제의 핵심은 이전에 점프한 거리보다 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 ..

이 문제를 처음 봤을 때 어떤 방식으로 풀어야 하는지 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..

백준 알고리즘 사이트에서 자료구조 분류에 있는 1158번 요세푸스 순열 문제를 풀면서 원형큐를 만들어 봤다. 원형큐는 FIFO 구조인 큐를 원형으로 동작하게 소스를 작성한 자료구조이고 큐에 대한 정보는 이전 포스팅에 작성하였다. https://jiji-gilog.tistory.com/3 자바(JAVA) - Queue (큐) 구현큐는 BFS(너비우선탐색) 알고리즘에서 자주 사용된다고 하여 배열로 구현해 보았다. 큐는 입구 1개, 출구 1개로 FIFO(First In First Out) 구조이며 스택(LIFO)과는 조금 다르다. 큐 구현을 위한 클래스jiji-gilog.tistory.com  원형큐 구현 시 고려할 사항내가 작성한 원형큐의 front 변수는 첫 번째 인덱스이고 빈 공간으로 설정한다. 만약 f..

큐는 BFS(너비우선탐색) 알고리즘에서 자주 사용된다고 하여 배열로 구현해 보았다. 큐는 입구 1개, 출구 1개로 FIFO(First In First Out) 구조이며 스택(LIFO)과는 조금 다르다. 큐 구현을 위한 클래스 변수 3개front: 큐의 맨 앞 원소위치 (초기값 0)rear: 큐의 맨 뒤 원소위치 (초기값 -1)size: 큐의 원소 개수 (초기값 0)메소드offer(Enqueue): 맨 뒤에 원소 삽입poll(Dequeue): 맨 앞에 원소 추출peek: 해당 메소드는 원래 맨 앞 원소를 확인하는 메소드인데 나는 front, back 메소드로 맨 앞, 맨 뒤 원소를 확인하는 메소드로 구현하였다. poll 메소드를 사용하여 맨 앞 원소를 추출하기 전에 원소가 없는 경우를 판단해야 하는데 그때..

이번 포스팅은 백준 알고리즘 사이트에서 스택 큐 덱 알고리즘 분류가 있어 스택을 배열로 구현하는 방법을 작성한다. 먼저 스택은 위 이미지처럼 입구가 맨위에 1개라서 LIFO(Last In First Out) 구조이고 원소 삽입은 push 메소드, 추출은 pop 메소드이다. 스택은 간단한 자료구조여서 설명할 게 없다... 원소 삽입 및 추출 시 배열 사이즈를 동적으로 할당하는 기능은 원형큐에 추가해 놓았다. https://jiji-gilog.tistory.com/4 자바(JAVA) - Circular Queue (원형큐) 구현백준 알고리즘 사이트에서 자료구조 분류에 있는 1158번 요세푸스 순열 문제를 풀면서 원형큐를 만들어 봤다. - 원형큐 구현 시 고려할 사항 1. front 큐의 첫 번째 인덱스로 빈..