전체 글127

• 

  백준 알고리즘 1826번: 연료 채우기 문제 정보 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 핵심 선뜻 Greedy를 사용하기 애매했다. 바로 직전 문제인 주유소(13305번) 보다 더 어려웠던 것 같다. 내가 그리디에 아직은 익숙하지 않다고 생각했다. 문제의 내용 문제는 단순하다. 시작 지점에서 끝 지점까지 이동할 때, 주유소를 최소 횟수만큼 들리도록 하는 것이다. 각 가중치는 해당 주유소에서 넣을 수 있는 기름 양이다. 실수했던 내용 난 처음에 이 문제의 유형을 인지하지 못하고, 목적지까지 가는 중간 .. 알고리즘/Java 2024. 4. 17.

• 

  백준 알고리즘 13305번: 주유소 문제 정보 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 핵심 너무 복잡하게 생각하면 안된다 이 문제의 핵심은 당연하게도 가장 싼 주유소에서 주유를 하는 것이다 나는 처음에 이 문제를 어렵게 접근해서 풀었다 (결국 풀었지만) 첫번째 풀이 int[][] station = new int[N][2]; int remain = 0; for(int i=N-1; i>=0; i--) { remain += distance[i]; station[i][0] = remain; station[i][1] = price[.. 알고리즘/Java 2024. 4. 16.

• 

  백준 알고리즘 9576번: 책 나눠주기 문제 정보 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 핵심 전공 서적을 최대한 많은 학생들에게 나누어 줘야 하는 문제! 여기서 일단 정렬의 필요성은 느꼈는데, 어떤 식으로 정렬해야 할 지 고민하다가 위와 같은 케이스를 고려하여 기준을 선정해야 겠다고 생각하였다 끝나는 수를 기준으로 정렬해야 한다. 왜냐하면 시작점을 기준으로 정렬해 버리면 위 사진과 같은 결과가 나와서 최대 경우가 나오지 않는다 그 이후에는, 각 정렬된 학생들의 신청서(시작점~끝점)를 순회하면서 남아있는 책이 있다면 Pick(visited=t.. 알고리즘/Java 2024. 4. 15.

• 

  백준 알고리즘 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 핵심 요약 각 보석들(N개)의 무게 및 가격이 존재한다 가방들(K개)에는 담을 수 있는 최대 무게가 존재한다 각 가방에는 보석을 하나씩만 담을 수 있음 -> 가방들로 담을 수 있는 보석 가격 합의 최대를 구하기 생각한 방법 단순히 무게만 가지고, 가방이 담을 수 있는 최소 무게의 보석을 택하는 것이 아닌 최대의 가격을 함께 생각해서 담아야 함 또한, 가방의 무게를 정렬해서 구해야 왼쪽의 케이.. 알고리즘/Java 2024. 4. 11.

• 

  백준 1655번: 가운데를 말해요 문제 정보 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 핵심 현재까지의 수의 개수가 홀수 개인 경우 가운데에 있는 수를 택하면 됨 짝수 개인 경우에는 두개의 수 중 작은 수를 택하면 됨 처음에는 이런 생각으로 정렬된 배열에서의 중앙 인덱스를 구해서 중앙값을 구하면 되겠다고 생각했지만, 생각해 보니 Heap은 내부가 정렬된 상태는 아니기 때문에 이렇게 풀이하지 못했다 정렬된 상태를 유지하는 자료구조를 써야하나? -> AVL 트리나 레드블랙 트리를 써야 할까도 생각했지만, 중앙 값을 구하는 것.. 알고리즘/Java 2024. 4. 11.