본문 바로가기

Algorithm16

[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.
[Algorithm] 정렬 (Sort) 1. 조건 (1) 정렬 조건이 필요하다. Comparable 인터페이스를 구현해야 한다. compareTo 메소드 오버라이딩을 통해 정렬 조건을 구현한다. (2) 시간 복잡도는 약 O(N logN) 이다. N개의 원소를 정렬하는 것은 O(NlogN) 만큼의 시간 복잡도를 갖는다. (3) In-place / Stable 여부를 알아야 한다. 정렬 알고리즘이 In-place(제자리)한가? 정렬하는 과정에서 N에 비해 충분히 무시할 만한 개수의 메모리만큼만 추가적으로 사용하는가? 정렬 알고리즘이 Stable(안정)한가? 동등한 위상의 원소들의 순서 관계가 보전되는가? ex) 5 3 4 5 수열의 경우 3 4 5 5 => 동등한 위상의 원소들의 순서가 보전되었다. 2. 특성 코딩테스트에서 정렬은 문제에 직접 언.. 2022. 1. 22.
[BOJ] 15663번: N과 M (9) (JAVA) 1. 문제 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개의 자연수 중에서 M개를 고른 수열 중복X, 순서O => 순열(Permutation) 단, 조건) 중복되는 수열을 여러 번 출력하면 안 된다. 중복되는 답을 제거해주어야 한다. 2. 시간복잡도 입력 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 순열(Permutation) 알고리즘에서는 O(N! / (N-M)!) 시간복잡도를 가진다. 시간 : O(N! / (N-M)!) = 8! / 0! = 40,320 3. 구현 (1) String.co.. 2022. 1. 22.
반응형

티스토리툴바