본문 바로가기

algorithm8

[BOJ] 2805번: 나무 자르기 (매개 변수 탐색) 1. 문제 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net (1) 정답의 최대치 정답의 범위: 0 ~ 10억 (Integer type) 잘린 나무의 길이 합 long 타입 사용해야 한다.) 2. 접근 (1) 키워드 체크하기 적어도 M미터의 나무를 집에 가져가기 위해서 절다기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오 (2) 매개 변수 만들어 보기 정답을 "매개 변수(Parameter)"로 만들고 Yes/No 문제(결정 문제)로 바꿔 보기 모든 값에 대.. 2022. 1. 26.
[Algorithm] 매개 변수 탐색 (Parametric Search) 1. 매개 변수 탐색 (Parametric Search) 최적화 문제를 결정 문제로 바꾸어 푸는 것이다. 정답을 파라미터로 만들고 결정문제로 바꾸어 푼다 => 이분 탐색의 아이디어 배열이 0과 1만 존재하며 오름차순 인건 보장되지만, 전체 배열은 모른다. 특정 인덱스의 값을 O(T)에 계산 가능할 때, 여기서 0과 1의 경계를 찾아야 한다면? Up-Down 게임 A가 1~1000 사이의 어떤 자연수를 선택 B는 A 한테 "생각한 숫자가 X 이상이야? 라는 질문 A는 맞으면 1, 아니면 0 이라고 대답 최소 횟수로 질문하려면? 하나씩 탐색 : 1000번 탐색, T(탐색시간) => O(T * 1000) 이분 탐색 : log1000 탐색, T(탐색시간) => O(T * log1000) = O(T * 10) *.. 2022. 1. 26.
[BOJ] 7795번: 먹을 것인가 먹힐 것인가 1. 문제 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net (1 ≤ N, M ≤ 20,000) 정답의 최대치 모든 쌍이 정단인 경우 => N * M = 20,000 * 20,000 = 4*10^8 = 4억 => Integer 사용 가능 2. 시간복잡도 (1) 완전탐색 A 배열 (N) 에서 하나씩 선택해서 B 배열 (M) 전부 탐색 O(NM) = 20,000 * 20,000 = 4억 => (4초) 시간초과 (2) 이분탐색 1. B 배열 정렬 한번 => O(Ml.. 2022. 1. 24.
[Algorithm] 이분 탐색 (Binary Search) 1. 탐색(Search)이란? 수열과 탐색 대상 X가 주어졌을 때, X가 존재하는 지? X[이하, 미만, 이상, 초과]의 원소는 몇 개가 있는지? X랑 가장 가까운 원소는 무엇인지? 모두 시간복잡도 O(N)을 가진다. 2. 이분 탐색 (Binary Search) 정렬이 보장되는 배열에서 기준 X를 가지고 범위를 "이분"하면서 탐색하는 방법 1) 임의의 M번 인덱스에 있는 A[M]이 X보다 크다면, A[M...N]은 전부 X보다 크다. 2) 임의의 M번 인덱스에 있는 A[M]이 X보다 작다면, A[1...M]은 전부 X보다 작다. * 오름차순 정렬이기 때문에 생기는 성질! 정렬이 아니라면 불가능하다. (1) 이분탐색 과정 L := X를 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스 R := X를 탐색할 가치가.. 2022. 1. 24.
[Algorithm] 이분 탐색 (Binary Search) 1. 탐색(Search)이란? 수열과 탐색 대상 X가 주어졌을 때, X가 존재하는 지? X[이하, 미만, 이상, 초과]의 원소는 몇 개가 있는지? X랑 가장 가까운 원소는 무엇인지? 모두 시간복잡도 O(N)을 가진다. 2. 이분 탐색 (Binary Search) 정렬이 보장되는 배열에서 기준 X를 가지고 범위를 "이분"하면서 탐색하는 방법 1) 임의의 M번 인덱스에 있는 A[M]이 X보다 크다면, A[M...N]은 전부 X보다 크다. 2) 임의의 M번 인덱스에 있는 A[M]이 X보다 작다면, A[1...M]은 전부 X보다 작다. * 오름차순 정렬이기 때문에 생기는 성질! 정렬이 아니라면 불가능하다. (1) 이분탐색 과정 L := X를 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스 R := X를 탐색할 가치가.. 2022. 1. 24.
[BOJ] 11652번: 카드 (JAVA) 1. 문제 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net N (1 ≤ N ≤ 100,000) 카드 숫자 : -2^62보다 크거나 같고, 2^62보다 작거나 같다. => long 타입을 써야 한다. int 타입 사용 시 런타임 에러 발생 정렬을 이용해서 답을 구할 수 있다. 2. 시간복잡도 배열 정렬 O(NlogN) 순서대로 읽기 O(N) 시간복잡도 : O(NlogN) = 100,000 * log100,000 100%.. 2022. 1. 22.
반응형

티스토리툴바