알고리즘/Java50

• 

  백준 알고리즘 1654번: 랜선 자르기 문제 정보 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 핵심 이분 탐색을 떠올려야 한다 내가 찾고자 하는 것은 N개의 랜선을 만들 수 있는 랜선의 최대 길이 이다 모든 길이를 탐색하여 랜선을 잘라보고, 최대 경우를 구하는 것은 불가능하므로 자연스럽게 이분 탐색을 시도해야 한다 우리가 흔히 사용했던 이분 탐색은 인덱스로 특정 수를 찾는 탐색을 많이 사용했다. 그래서인지 새로운 관점을 적용하기가 조금 어려웠던 문제라고 생각한다 풀이에서 min, max, mid 라는 변수가 등장한다.. 알고리즘/Java 2024. 4. 4.

• 

  백준 알고리즘 2529번: 부등호 문제 정보 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 핵심 백트래킹으로도 문제를 풀이할 수 있는데, 나는 조금은 다른 방식으로 문제를 풀이했다 일단 문제의 경우 부등호 관계를 만족시키는 최소/최대 정수를 구하는 문제이다 중복된 정수는 사용할 수 없으며, 첫 자리에 0이 가능한 것이 특징이다 당연하게도, 최소가 되려면 앞자리의 수가 작아야 하고 최대가 되려면 앞자리의 수가 커야 한다 다만 생각해야 할 것은 무작정 앞자리의 수를 최소/최대 수로 집어넣는 것이 아니라, 뒤에 부등호를 잘 보아야 한다는 점이다.. 알고리즘/Java 2024. 4. 3.

• 

  백준 알고리즘 2217번: 로프 문제 정보 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 핵심 어렵지 않은 단순 정렬 문제이다. 문제를 정리하자면 물체의 중량이 x일 때, 선택한 로프의 개수가 n개라면, 각 로프는 x/n의 중량을 부담 가능해야 한다 문제의 솔루션은 다음과 같다 들수 있는 최대 중량 = 선택한 로프들 중 최소 중량 * 사용된 로프의 수 어차피 로프를 많이 선택해 봤자, 각 로프들은 동일한 무게씩 배분한다 1 500 1000 -> 총 3개의 로프를 선택했다고 가정하자, 어떠한 큰 숫자가 나오더라도 첫번째 로프는 1의.. 알고리즘/Java 2024. 4. 2.

• 

  백준 알고리즘 1931번: 회의실 배정 문제 정보 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 핵심 최적의 해를 찾는 과정을 잘 생각해야 하는 문제인것 같다고 생각했고, 해당 문제를 풀이하는 과정은 다음과 같다 먼저 해당 회의시간(시작시간, 종료시간) 을 종료시간을 기준으로 정렬시킨다 왜냐하면, 현재 위치를 기준으로 가능한 회의 중 종료시간이 가장 빠른(작은) 회의를 선택해야 더 많은 회의를 진행할 수 있기 때문이다 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 위는 예제의 데이터인데, 이미 정렬되어 있지만 정렬한다면 위와 같은 순서로 정렬될 것이다 만약 종료 시간이 같다면? 시작 시간이 작은(빠른) 회의를 기준으로 .. 알고리즘/Java 2024. 3. 23.

• 

  백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열 문제 정보 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 핵심 DP 배열의 정의를 어떻게 내리느냐가 중요했다고 생각한다 매번 DP 관련 문제를 풀면서 느끼는 것이지만, 코드는 비슷한데 생각을 만들어 내느냐가 가장 중요한 것 같다 이 문제같은 경우에는 dp 배열을 다음과 같이 정의하였다 dp[i] : i번째 수를 선택했을 때, 가질 수 있는 최대의 길이 현재 위치를 무조건 택한다는 가정이 있기때문에, 1. 이전 dp 배열을 보면서 해.. 알고리즘/Java 2024. 3. 20.