이분탐색이란? 이분탐색은 정렬되어 있는 배열에서 사용 가능한 탐색 방법으로, 탐색 범위를 매번 반으로 쪼개 나가며 탐색하는 방법을 얘기합니다. 일반적인 탐색 방법과 비교하기 위해 다음과 같은 문제를 예시로 들어봅시다. 1~N 사이의 자연수로 이루어진 길이가 N인 수열이 있습니다. 이 수열에서 1 이상 N 이하의 정수 K는 몇 번째에 위치해 있는지 구하고자 합니다. 이를 완전탐색으로 해결하면 1번째 값부터 N번째 값까지 일일이 확인해보는 O(N)의 방법이 있습니다. 하지만 N이 100,000 이상 혹은 더욱 커지면 비효율적으로 동작하므로 더욱 빠르게 동작하는 알고리즘이 필요합니다. 만약 수열이 오름차순으로 정렬되어 있다면 이분탐색이라는 알고리즘을 적용할 수 있고, 이의 시간복잡도는 O(logN)입니다. 이..

1. 완전탐색이란? 완전탐색은 가능한 모든 경우에 대해서 일일이 수행해보는 알고리즘을 말합니다. 이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법입니다. 예를 들어, 4자리의 암호로 구성된 자물쇠를 풀려고 시도한다고 생각해봅시다. 이 자물쇠가 고장난 것이 아니라면, 반드시 해결할 수 있는 가장 확실한 방법은 0000 ~ 9999까지 모두 시도해보는 것입니다. (최대 10,000번의 시도로 해결 가능) 하지만, Computer Science에서 문제 해결 알고리즘을 사용할 때는, 기본적으로 2가지 규칙을 적용합니다. 1. 사용된 알고리즘이 적절한가? ( 문제를 해결할 수 있는가 ) 2. 효..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net def dfs(): if len(s) == m: print(' '.join(map(str, s))) return for i in range(1, n+1): s.append(i) dfs() s.pop() n, m = map(int, input().split()) s = [] dfs()

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net def dfs(start): if len(s) == m: print(' '.join(map(str, s))) return for i in range(start, n+1): if visited[i]: continue visited[i] = True s.append(i) dfs(i+1) s.pop() visited[i] = False n, m = map(int, input().split()) s =..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net def dfs(): if len(s) == m: print(' '.join(map(str, s))) return for i in range(1, n+1): if visited[i]: continue visited[i] = True s.append(i) dfs() s.pop() visited[i] = False n, m = map(int, input().split()) s = [] visited ..

https://www.acmicpc.net/problem/2343 import sys input = sys.stdin.readline n, m = map(int, input().split()) lecture = list(map(int, input().split())) ans = 0 s = max(lecture) e = sum(lecture) while s mid: temp = 0 cnt+=1 temp += i if temp != 0: cnt+=1 if cnt > m: s = mid + 1 else: e = mid - 1 print(s) 최소값을 구하려면 s를 값으로 반환하거나 e에서 mid를 값으로 넣으면 된다. 일단 시작 값을 나는 1로 설정을 했는데 생각해보면 모든 영상을 블루레이로 담으려고 하는게 ..