Algorithm61 [백준] 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. [백준] 1519번 부분 문자열 뽑기 게임 자바 문제 1519번: 부분 문자열 뽑기 게임 첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 dp배열을 이용하여 해당 게임 판에 써져 있는 N에서 진 부분 문자열을 빼서 만들 수 있는 모든 수의 승패여부를 확인한다. dp[x] = 숫자 x에 대해서 패배하는지 승리하는지의 여부 저장 (0:아직 모름/ 패배:-1/ 승리: 승리하기 위한 최소 부분문자열) dp[N+1]로 잡아서 숫자1부터 N까지 담을 수 있도록 한다. 그리고 N이 일의 자리인 경우 부분 문자열을 고를 수 없으므로 무조건 게임에서 지게된다. 따라서 우선 dp[1] ~ dp[9]까지는 -1을 담아 두고, N값에서 부분 문자열을 뺀 값부터 dp적용을 한다. 예를 들어 dp[10]은 .. 2022. 6. 13. [백준] 2075번 N번째 큰 수 자바 문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 처음에는 배열의 맨 아래 행만 정렬시킨 후 ArrayList에 담아, 두 개의 포인터를 이용해서 꺼내면서 이동시켜가면서 N번째 수를 구하려고 했는데 우선순위 큐를 이용하면 훨씬 빠르고 간단하게 풀이가 가능하다. ✔️ Priority Queue (우선순위 큐) 일반적인 FIFO인 큐의 구조를 그대로 가지는데, 데이터가 들어온 순서대로 나가는 것이 아니라 우선순위를 먼저 결정한 후 우선순위가 높은 데이터부터 나가는 자료구조이다. N번째 큰 수를 구해야 하므.. 2022. 6. 11. [백준] 4195번 친구 네트워크 자바 문제 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제 풀이 HashMap을 이용하여 친구의 이름을 숫자로 표현해야 배열 인덱스를 이용할 수 있다. 그리고 union-find함수를 이용하여 두 친구 관계의 집합 크기를 늘려간다. 이때 연결 노드를 저장할 부모 배열외에 몇개가 연결되어있는지 누적하기 위해 count 정수형 배열을 하나 더 사용해준다. count배열에는 처음에 모두 1로 초기화해주고 해당 원소가 다른 원소로 합쳐질 때(부모값이 변경될 때) count값을 해당 원소의 최상위 부모 co.. 2022. 6. 8. 이전 1 2 3 4 5 6 ··· 11 다음