Algorithm/BOJ42 [백준] 2357번 최솟값과 최댓값 자바 문제 (세그먼트 트리) https://www.acmicpc.net/problem/2357 문제 풀이 일일이 구간 내에서 for문을 돌려서 최대 최소를 구하면 시간초과가 난다.정수 배열의 특정 구간 내에서 연산을 해야 하는 세그먼트 트리의 응용 버전이다. 그래서 구간 별로 최소값과 최댓값을 미리 한번에 저장해두고 입력값을 바로 도출해 내야 한다.구간 별 최소값 및 최대값 을 저장해놓은 트리배열 2개를 각각 생성하여 따로 호출하여 출력했다. 소스 코드 public class b_2357 { static int[] arr; static int[] minTree, maxTree; public static void main(String[] args) { Scanner sc = new Scanner(Sys.. 2024. 10. 28. [백준] 1725번 히스토그램 자바 문제 (스택) 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 문제 풀이 문제 풀이에 대한 논리가 많이 어려웠다. 세그먼트 트리를 이용해서도 많이 푸는 방식인 것 같은데 나는 세그먼트 트리에 대해서 잘 몰라서 만만한(?) 스택으로 풀기로 했다. 다른 블로그 글들에 그림 포함해서 설명이 잘 나와있어서 알고리즘은 내가 보기 편한대로 다시 정리해보자면, 우선 히스토그램 순서대로 반복문을 실행하면서 높이가 증가하다가 감소하는 부분을 유의해야 한다. 왜냐하면 높이가 감소하는 순간 바로 그 .. 2022. 6. 29. [백준] 2110번 공유기 설치 자바 문제 (이분 탐색) 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 풀이 이분 탐색 알고리즘이다. 이분 탐색 문제를 몇 개 풀면서 느낀 건데 약간 정답의 범위가 정수의 형태로 적당히(?) 정해지는 경우 사용하는 것 같다. 그리고 이분 탐색을 사용할 때, 이분 탐색을 코드를 작성하는 것보다 해당 값에 대해 성립하는지 확인하는 코드짜기가 더 어렵다. 이번 공유기 설치 문제도 이분 탐색으로 정답을 추려가면서 이 정답에 성립하는지를 처리하는 로직이 까다로웠다... 2022. 6. 22. [백준] 2805번 나무 자르기 자바 문제 (이진 탐색) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 풀이 이진 탐색 알고리즘은 알고 있었지만 이 문제를 통해 이와 비슷한 새로운 알고리즘을 알게되었다. ✔️이진 탐색 : 데이터가 정렬되어 있는 배열에서 특정값을 찾아내는 알고리즘 1) 중간에 있는 임의의 값을 선택하여 찾고자 하는 수 X와 비교한다 1-1) X가 임의값보다 작으면, 임의값 기준 왼쪽 데이터들을 대상으로 다시 탐색 1-2) X가 임의값보다 크면, 임의값 기준 오른쪽 데이터들을 대상으로 .. 2022. 6. 19. [백준] 1202번 보석 도둑 자바 문제 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 처음에는 보석을 기준으로 ArrayList와 PriorityQueue를 이용해서 가장 비싼 것부터 제거해나갔는데 시간초과였다. 구글링을 해보니 보석을 기준으로 하는게 아니라 가방을 기준으로 해야 했고, 또 우선순위큐 하나로 구현이 가능했다. ✔️알고리즘 1. 보석을 무게가 가벼운 순으로 정렬을 한다 (오름차순) 2. 가방을 가벼운 순으로 정렬을 한다 (오름차순) 3. 모든 가방에 대하여.. 2022. 6. 17. [백준] 14247번 나무 자르기 자바 문제 14247번: 나무 자르기 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 www.acmicpc.net 문제 풀이 처음엔 그날 그날의 나무 중에서 가장 큰 걸 자르도록 구현했는데, 이렇게 하면 주어진 테스트 케이스도 맞추지 못한다. 나무1 나무2 나무3 나무4 나무5 1일째 1 3 2 4 6 2일째 3 10 5 8 1 3일째 5 7 8 12 2 4일째 7 14 11 4 3 5일째 9 7 14 8 4 => 6 + 10 + 12 + 14 + 14 = 56 이므로 최대치가 아니게 된다. 최대치를 구하기 위해서는 성장 속도가 제일 느린 것부터 더해주어야 한다. 왜냐하.. 2022. 6. 17. 이전 1 2 3 4 ··· 7 다음