본문 바로가기

코딩테스트22

[그리디 알고리즘] 백준 1715번 문제정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) =.. 2024. 12. 2.
[그리디알고리즘] 백준 11047번 문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 문제분석동전개수의 최솟값을 묻는 질문이므로, 가격이 큰 동전 부터 거슬러서 개수를 구하면 최소 조건이 된다.그리디 탐색 방법으로 , 각각의 시행 시점의 최솟값이 전체 최솟값이 되기에 그리디 탐색방법으로 사용해도 무방하다- 거스름 돈의 입력은 오름차순.. 2024. 11. 27.
[이진탐색] 백준 1300번 문제세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.배열 A와 B의 인덱스는 1부터 시작한다. 문제분석첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다.10^5 이므로, O(N^2)으로 풀이를 할 경우 메모리 초과가 나온다.이진탐색을 이용하여 풀이를 할 생각을 해야한다. (O(logN))3*3 예시)3 * 3 배열 형성 (N = 3)K 값 : 7[i]/[j] (인덱스)123결과1123-> 1의 배수2246-> 2의 배수3369->.. 2024. 11. 24.
[이진탐색] 백준 2343번 문제강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.강토의 각 강의의 길이가 분 단.. 2024. 11. 22.
[이진탐색] 백준 1920번 문제N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.[입력]첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. [출력]M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 문제 분석주어진 수들의 존재여부를 찾아야하므로, 탐색 알고리즘을 선택해야한다.자연수의 범위가 100,000이므로 N^2 의 시간복잡도를 가지는 탐색알고리즘을 사용하면 안된다.고로, 이진탐색을 사용하여 (O.. 2024. 11. 21.
이진탐색 이진탐색이란?원하는 데이터를 빠르게 찾기 위한 알고리즘이진 탐색은 데이터가 정렬되어있는 상태에서 중앙값을 이용해서 찾고자 하는 값과 비교해가며 찾는 알고리즘(코딩테스트에서 부분 문제로 많이 출제 됨)기능특징시간복잡도Target 데이터 탐색중앙값 비교를 통한 대상 축소 방식O(logN) 이진탐색 핵심이론pre) 오름차순으로 정렬현재 데이터 셋에서 중앙값을 설정한다중앙값 > Target 값 일때, 중앙값 기준으로 왼쪽 데이터 셋 설정중앙값 1~3을 반복하다가, 중앙값 == Target 일때 탐색 종료 EX) 48을 찾아라20303340 454850xxxx454850xxxxx48 (탐색 종료)50 이진탐색 구현import java.util.Arrays;public class App { public sta.. 2024. 11. 21.

티스토리툴바