목록java (150)

땀두 블로그

[백준] 11279번 - 최대 힙

힙을 사용하는 문제이다. 이 문제는 힙을 직접 구현해도 되지만 간단히 우선순위 큐를 이용하여서 해결하면 된다. 입력값이 0일 때 마다 출력을 해주는데 값이 없는 경우 0을 출력하고, 있으면 그 값들 중 최대값을 출력해주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Collections; import java.util.PriorityQueue; public class p11279 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stu..
알고리즘/백준 2022. 3. 21. 09:06
탐욕법 - 거스름돈 알고리즘, 동전교환 알고리즘

탐욕법의 가장 대표적인 알고리즘으로 문제에 필요한 금액이 입력되면 가지고 있는 동전의 조합으로 해결하는 문제이다. 주어진 숫자 N을 충족하기 위해 동전의 배열에서 가장 큰 값부터 조건에 만족하면 추가하는 식으로 문제를 해결한다. public class coinChange { public static void main(String[] args) { // TODO Auto-generated method stub int N = 164; int ary[] = { 1, 5, 10, 50 }; int cnt = 0; for (int i = ary.length - 1; i >= 0; i--) { while (N > 0) { if (N >= ary[i]) { N -= ary[i]; cnt++; } else { brea..
알고리즘 2022. 3. 21. 09:05
[백준] 1931번 - 회의실 배정

그리디 알고리즘을 이용한 문제이다. 이러한 문제를 푸는 방식을 '활동 선택 문제'라고 한다. 활동 선택 문제에 대해 간략한 설명은 아래 링크를 참고하면 된다. https://ddamdoo.tistory.com/159 탐욕법 - 활동 선택 문제(Activity Selection Problem) 우리가 흔히 알고리즘에서 사용하는 탐욕법은 현재 위치에서 가장 최적의 해를 구해가는 과정을 연속해서 진행하는 문제이다. 이러한 문제 유형 중에는 활동 선택 문제가 있는데 이는 n개의 시 ddamdoo.tistory.com 이 문제를 활동 선택 문제로 풀게되면 먼저 종료시간 순으로 오름차순하고, 만약 종료시간이 같은 경우 시작시간을 기준으로 오름차순을 진행하여 해결하면 된다. import java.io.Buffered..
알고리즘/백준 2022. 3. 21. 09:04
[백준] 11726번 - 2*n 타일링

머리로만 풀다보니 제대로 안풀렸는데 그림으로 그리니 간단하게 해결이 되었다. 이렇게 1일 때는 1, 2일 때는 2, 3일 때 3, 4일 때 5, 5일 때 8.... 이 규칙성을 보면 n이 3보다 클 때 n으로 만들 수 있는 조합의 수는 f(n)=f(n-1) + f(n-2)라는 식을 세울 수 있다. 이 식을 이용하여 문제를 해결하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class p11726 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stu..
알고리즘/백준 2022. 3. 21. 08:57
[백준] 2630번 - 색종이 만들기

대표사진 삭제 사진 편집 작게작게문서 너비문서 너비옆트임옆트임 삭제삭제 사진 설명을 입력하세요. 대표사진 삭제 사진 설명을 입력하세요. 대표사진 삭제 사진 설명을 입력하세요. 처음으로 나온 분할정복(devide & conquer)문제이다. 문제가 해결되지 않으면 해결되는 수준까지 분해하는 문제로, 재귀함수를 이용하면 된다. 이 문제같은 경우 전체 배열의 크기를 반씩 줄여가면서 좌표를 옮겨가는 식으로 문제를 해결하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p2630 { public static ..
알고리즘/백준 2022. 3. 21. 08:55
Prev 1 ··· 8 9 10 11 12 13 14 ··· 30 Next