자바37

• 

  백준 알고리즘 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.

• 

  백준 알고리즘 2293번: 동전1 문제 정보 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 핵심 이전 글과 동일한 Dynamic Programming을 활용하여 풀이하는 문제이다 기존 문제 대비 점화식 세우는것이 개인적으로 조금 어렵다고 느꼈기 때문에 최대한 처음 문제를 접하는 입장에서 문제를 풀이해보도록 하겠다 문제 유형 잡기 일단 해당 문제는 서두에 설명했듯 DP 알고리즘을 사용하는 문제이다 이를 생각하게 된 몇가지 근거는, 먼저 일반적으로 많이 풀어봤을 법한 잔돈 문제 등은 Greedy 알고리즘이지만 이는 최적의 해를 구해나가는 방식으로.. 알고리즘/Java 2023. 12. 22.

• 

  백준 알고리즘 2583번: 영역 구하기 문제 정보 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 핵심 그래프 탐색 알고리즘을 사용하여 문제를 풀이하자! 다만, 처음에 고민되었던 부분은 각 영역의 오른쪽 위 꼭짓점의 좌표값을 어떻게 처리하느냐.. 였는데 꼭짓점을 좌표라고 생각하지 말고, 해당 영역을 좌표라고 생각해 보는 것이 도움이 되었던 것 같다 예를 들어 (0, 0)은 왼쪽 아래 꼭짓점이라고 생각하기보다는 첫번째 (왼쪽 아래) 영역이라고 생각하면 map[0][0]은 해당 영역을 나타내는 값이 되는 것이다 간단하게 그림으로 나.. 알고리즘/Java 2023. 12. 14.