kim_ghgh

본문 바로가기

최신 글

알고리즘

Algorithm Note Dynamic Programming(DP) 알고리즘 - 동적프로그래밍, Python으로 푸는 피보나치 Dynamic Programming 큰 문제를 나누어 작은 문제로 푸는 것 하나의 문제는 단 한 번의 풀이만 한다. Dynamic Programming 과 Recursion(재귀)의 차이점 DP와 재귀는 얼핏보면 '같은 문제가 반복적으로 일어나는 점' 에서 비슷하다고 생각할 수 있다. 하지만, 큰 차이점은 일반적인 재귀를 단순히 사용하면 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다. 가장 대표적인 예시는 피보나치 함수이다. DP 조건 두 가지 조건을 만족해야 한다. 1. 같은 문제가 반복적으로 발생 2. 최적 부분 구조 동일한 작은 문제들이 반복적으로 일어날 때, 같은 문제는 항상 정답도 같다. 즉, 중복 사용이 가능하다. DP 문제 풀이 방법 모든 작은 문제는 한 번..
Algorithm Note 알고리즘 - Greedy (탐욕 알고리즘, 욕심쟁이 알고리즘), 최적해 찾기 Greedy Alogrithm Greedy는 사전적인 의미로 '탐욕스러운', '욕심많은' 이라는 뜻을 가지고 있다. 탐욕 알고리즘 또는 욕심쟁이 알고리즘 라고도 불린다. 미래를 생각하지 않고 선택의 순간마다 당장 눈앞에 보이는 최적의 선택을 하는 기법 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘 그리디 알고리즘 해결 방법 선택 : 현재 상태에서 최적의 해답 선택 적절성 검사 : 선택된 답이 문제의 조건을 만족하는 지 확인 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다. 그리디 알고리즘 조건 그리디 알고리즘을 적용하기 위해서는 2가지 조건을 성립해야 한다. 1. 탐욕적 선택 속성 (Greedy Choice Prop..
Algorithm Note 알고리즘 - Stack, Queue (선형 큐, 원형 큐, 알고리즘 코드) 스택 '먼저 들어간 것이 나중에 나오는 자료구조' Last In First Out (LIFO) 구조이다. 스택은 배열과 연결 리스트로 나타낼 수 있다. 스택의 구성 - 상단 (top) : 스택에서 제일 나중에 입력된 데이터의 위치 - 하단 (bottom) : 스택에서 제일 먼저 입력된 데이터의 위치 - 요소 (element) : 스택에 저장되는 데이터 그 자체 - 공백 (empty stack) : 아무런 데이터도 갖고 있지 않은 스택 스택의 연산 push() : 스택에 데이터를 추가한다. pop() : 스택에서 데이터를 삭제한다. is_empty(s) : 스택이 공백상태인지 검사한다. is_full(s) : 스택이 포화상태인지 검사한다. create() : 스택을 생성한다. peek(s) : 요소를 스택..

조회수가 많은 글

728x90

티스토리툴바