[5주차] 이분 탐색 (이진 검색; Binary Search) 이분 탐색 (Binary Search)이란? 개념 정렬된 데이터에서 특정 데이터를 찾을 때 탐색 범위를 절반씩 줄여가며 탐색하는 방법 모든 데이터를 순회하며 확인하는 방식보다 빠름 시간복잡도 \(O(log_2N)\) 중앙값과 찾으려는 데이터를 비교하여 중앙값의 왼쪽 또는 오른쪽 절반 선택 중앙값 > 탐색 데이터 : 왼쪽 중앙값 < 탐색 데이터 : 오른쪽 구현 패턴 데이터 정렬 (필요 없는 경우도 존재) 탐색 범위 지정 low : 0 (또는 초기 탐색 범위의 최소값; 구현 시 편의를 위해 lo로 사용) high : 배열크기 - 1 (또는 초기 탐색 범위의 최대값; 구현시 편의를 위해 hi로 사용) 중앙값 설정 mid : (low + high) / 2 중앙값과 비교 arr[mid] == toSearch : .. [3주차] DP (Dynamic Programming; 동적 계획법) 다이나믹 프로그래밍(동적 계획법)이란? 개념 복잡한 문제를 작은 부분 문제(최적 부분 구조)로 나누어 해결 (≒ 분할정복) 점화식 활용 (점화식; 재귀적으로 정의되는 수학적 함수) cf) 다이나믹 프로그래밍(중복&메모이제이션 o) vs 분할정복(중복&메모이제이션 x) 중복되는 부분 문제(overlapping subproblems) 동일한 부분 문제가 중복 계산될 경우 한 번만 계산하여 결과 재활용 - 계산 중복 횟수는 분할 깊이가 깊어질수록 지수적으로 증가하기 때문 - 계산 결과 재활용 시 속도 향상 가능 계산 결과를 재활용하려면 메모리에 저장 필요 → 메모이제이션(memoization) → 1 & 2 모두 만족하는 경우 다이나믹 프로그래밍 적용 구현 패턴 값 저장 공간 초기화 (계산 결과가 될 수 없는.. Algorithm Study _ JAVA Baekjoon 단계별로 풀어보기 Week01 (26.JAN) 함수 - 4673, 1065 [2/28] 18 선형 자료 구조 18 선형 자료 구조 18.1 도입 배열?일렬로 늘어선 같은 종류의 자료 여러 개를 저장하기 위한 가장 기초적인 자료 구조 동적 배열과 연결 리스트배열에서 비효율적이거나 할 수 없는 작업들을 효율적으로 할 수 있게 도와줌 18.2 동적 배열 동적 배열(dynamic array)배열의 큰 문제 중 하나인 크기 지정 문제를 해결하기 위해 고안배열을 이용해 만들어 낸 별도의 자료 구조 (그래서 언어 문법이 아니라 언어의 표준 라이브러리에 포함) 동적 배열의 특성1. 원소들은 메모리의 연속된 위치에 저장2. 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1) 안에 할 수 있음3. resize() 연산 : 배열의 크기를 변경 (배열의 크기 N에 비례하는 시간)4. append() 연산 : 주어진 원소를 배열.. [2/27] 08 동적 계획법 (3) 08 동적 계획법 (8.11~8.17) 8.11 경우의 수와 확률 동적 계획법은 경우의 수를 세거나 확률을 계산하는 문제에도 많이 사용 오버플로에 유의하기답이 일반적으로 우리가 사용하는 32비트 정수형의 한계를 초과하기 십상대부분의 문제에서는 답을 어떤 수 M으로 나눈 나머지를 출력하기를 요구하는 식으로 이런 현상을 해결모듈라 연산(14.8 참고)(a+b)%M = ((a%M)+(b%M))%M(a-b)%M = ((a%M)-(b%M)+M)%M(a×b)%M = ((a%M)×(b%M))%M 예제 : 타일링 방법의 수 세기맨 왼쪽 세로줄이 어떻게 채워져 있는 지에 따라 두 경우로 나뉨한 개의 세로 타일 / 두 개의 가로 타일[조건]이 두 가지 분류는 타일링하는 방법을 모두 포함 (이 두 가지 외의 경우는 없다는 .. [2/25] 08 동적 계획법 (2) 08 동적 계획법 (8.5~8.10) 8.5 문제 : 합친 LIS [문제] 두 개의 정수 수열 A와 B에서 각각 길이 0 이상의 증가 부분 수열을 얻은 뒤,이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 합시다.이 중 가장 긴 수열을 합친 LIS (JLIS)라고 부릅시다.A와 B가 주어질 때, 합친 LIS의 길이를 계산하는 프로그램을 작성하세요. [시간 및 메모리 제한]프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다. [입력]입력의 첫 줄에는 테스트 케이스의 수 C(1≤C≤50)가 주어집니다.각 테스트 케이스의 첫 줄에는 A와 B의 길이 n과 m(1≤n,m≤100)이 주어집니다.다음 줄에는 n개의 정수로 A의 원소들이, 그 다음 줄에는 m개의 정수로 B.. [2/21] 08 동적 계획법 (1) 08 동적 계획법 (8.1~8.4) 8.1 도입 동적 계획법(dynamic programming)이란?최적화 문제를 연구하는 수학 이론에서 출발.큰 의미에서 분할 정복과 같음. (문제를 부분 문제로 나누어 해결)한 부분 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용하여 속도를 향상 시킨다는 것이 분할 정복과의 차이(중복 계산은 속도 저하를 야기하므로 중복을 없애는 것이 관건! 중복 횟수는 분할의 깊이가 깊어질수록 지수적으로 증가한다.)계산 결과 재활용을 위해 각 문제의 답을 메모리에 저장해 둠 메모이제이션(memoization)이란?함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법.메모이제이션을 사용하면 모든 부분 문제가 한 번.. [2/20] 07 분할정복 (2) 07 분할정복 (7.4~7.7) 7.4 문제 : 울타리 잘라내기 [문제] 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 울타리에서 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요.단, 판자의 너비는 모두 1이며 비스듬히 잘라낼 수 없다. [시간 및 메모리 제한]프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다. [입력]첫 줄에 테스트 케이스의 개수 C(C≤50)가 주어집니다.각 테스트 케이스의 첫 줄에는 판자의 수 N(1≤N≤20000)이 주어집니다.높이는 모두 10,000 이하의 자연수입니다. [출력]각 테스트 케이스당 정수 하나를 한 줄에 출력합니다.이 정수는 주어진 울타리에서 잘라낼 수 .. 이전 1 2 다음
