알고리즘/개념 (2) 썸네일형 리스트형 [C++] 다이나믹 프로그래밍(Dynamic Programming) 안녕하세요! 테크지니어22입니다.오늘은 다이나믹 프로그래밍에 대해서 알아보도록 하겠습니다. 다이나믹 프로그래밍(DP)이란?- 여러 하위 문제들로 풀고 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘- 일반적으로 시간복잡도는 O(n^2) or O(n x m)형태로 나타남. 언제 자주 사용되는가? - 최적화문제(최대,최소) -> n이 커서 백트래킹이나, 완전탐색 등으로 구할 수 없는 경우 유용- 중복되는 부분 문제 어떻게 사용하는가?전체 문제를 하위 문제로 쪼개고 이를 이용하여 전체 문제로 해결가능한 지 파악하기테이블 정의하기1차원으로 최대한 정의를 해보기(관점을 달리하기 혹은 비틀어보기)어렵거나 추가 정보가 요구되면 2차원 정의 해보기점화식 찾기초기값 설정하기DP 배열 채우기탑다운 방식->재귀 사용바텀.. [C++] 이분 탐색 안녕하세요! 테크지니어22입니다.오늘은 이분 탐색에 대해서 알아보도록 하겠습니다. 1. 이분탐색이란?정렬되어 있는 배열에서 특정 데이터를 찾기 위해 탐색 범위를 절반으로 줄여가며 찾는 탐색법입니다.일반적으로 선형탐색 시간초과가 발생하면 이분탐색을 떠올리게 됩니다.하지만 이분 탐색이 가장 많이 사용하는 상황은 최적화문제를 결정 문제로 변환이 필요할 때입니다.'한쪽 구간은 뭔가가 되고, 한쪽 구간은 안 된다. 따라서 어떤 한 값의 가능 여부를 알면 그 값을 기준으로 어떤 구간을 탐색할지 결정할 수 있다' 가 핵심입니다. 2. 탐색구간- 어떤 탐색구간을 사용하건 구현상의 선택의 문제이기 때문에 자신에게 편한 것을 선택하면 됩니다. [lo,hi] 구간조건: while (lo ≤ hi)경계 업데이트 : if(co.. 이전 1 다음