백준 - [BOJ 2109] 순회강연
백준 온라인 져지(BOJ)에서 제공 되는 2019번 문제는 그리디(Greedy, 탐욕법) 유형이다. 해당 문제는 code.plus 중급 1/3, 그리디 알고리즘에 게시된 문제이다. 문제 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다. 예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 ..
2024. 2. 29.
[이분 탐색] 이분 탐색(Binary Search) 이란 ?
이분 탐색 두 이, 나눌 분을 써서 이분인가? 정답, 이분 탐색은 두개로 나누어서 탐색하는 것이다. 예를 들어, 1부터 10까지 있다고 생각해보자. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 우리가 8을 찾을 때, 눈으로 바로 보이니까 위치를 파악할 수 있다. 하지만 몇 번째에 있는가? 배열은 0번째부터 시작하니 7번째에 있다는 것을 알 수 있다. 컴퓨터 배열 인덱스 개념이 없는 사람들은 8번째라고 답할 것이다. 즉, O(1) 시간이다. 그럼, {1, 4, 7, 10, 12, 23, 30, 35, 100, 120} 이 있을 때, 35의 위치는? 우리는 앞에서 값을 세어가면서 몇 번째에 있는지 알 것이다. 즉, O(N) 시간이다. 100만개의 숫자가 있다면? 우리는 100만개를 일일이 세다가..
2024. 2. 1.
백준 - [BOJ 12015] 가장 긴 증가하는 부분 수열 2
백준 온라인 져지(BOJ)에서 제공 되는 12015번 문제는 선행 문제가 있다. 가장 긴 증가하는 부분 수열 나는 위 문제를 먼저 풀어보고 오는 것을 추천한다. 해당 문제는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)로 유명한 문제이다. 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤..
2024. 2. 1.
