다이나믹 프로그래밍

#1 동적 프로그래밍이란?① 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고 ② 이를 재귀호출로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법이다.#2 문제의 조건최적하부구조부분문제들 간의 중복 존재최적하부구조큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있다.큰 문제와 작은 문제 간의 관계를 점화식으로 표현 가능하다.예: 펙토리얼 함수부분문제들 간의 중복 존재재귀호출로 문제를 해결할 때 중복되는 연산이 존재중복 연산에 의한 엄청난 비효율 발생#3 구현전략다이나믹 프로그래밍을 적용하는 방식으로 탑다운 방식과 버텀업 방식이 있다.탑다운 방식은 재귀호출을 사용하고 버텀업 방식은 재귀호출 대신에 반복문을 사용한다.양 방법 모두 중복되는 연산의 결과를 따로 저장한다.계산결과를..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 10. 21.

추적값(pivot)을 활용한 분할 알고리즘

문제특정 값을 기준으로 배열을 두개의 영역으로 분할하려고 한다. 특정값을 pivot이라고 하자. pivot을 기준으로 pivot보다 작은 값들과 pivot보다 큰값들이 모인 영역으로 배열을 분할한다. 아이디어구현의 편의상 배열의 맨 끝 원소를 pivot으로 삼는다. pivot보다 작지만 가장 마지막에 배치 된 원소의 인덱스를 i, 배열을 순회하는 인덱스를 j, 배열의 첫번째 인덱스를 lo, 마지막 index를 hi라고 하자.포인터 j가 배열 전체를 순회한다.j가 가리키는 값이 pivot보다 작다면 i를 값을 1만큼 증가한 후에 j의 값과 교체한다. 교체 후에 j를 전진시킨다.j가 가리키는 값이 pivot보다 크다면 j를 전진시킨다.j가 pivot에 도달할 때까지 반복한다.j가 pivot에 도달하면 i +..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 10. 15.

선형시간으로 최대값과 최소값 찾기

문제배열을 정렬을 하지 않고도 선형시간으로 최대값과 최소값을 찾을 수 있다.접근법배열의 크기가 짝수인지 또는 홀수인지에 따라 나뉜다. 홀수인 경우에는 추가작업이 필요하다. 공통 접근법은 다음과 같다.배열의 인덱스 0번과 1번 자리를 각각 최소자리와 최대자리로 지정한다.배열을 2만큼씩 간격으로 i번째와 i+1번째의 값의 크기를 비교한다. i번째가 더 크다면 두 값의 위치를 교체한다.0번째 값은 i번째와 비교하여 0번째가 값이 더 큰 경우에 위치를 교체한다.1번째 값은 i+1번째와 비교하여 1번째가 값이 더 큰 경우에 위치를 교체한다.배열의 크기가 짝수인 경우에 배열 전부에 위의 과정을 반복하고 홀수인 경우에는 마지막 원소를 제외하고 실행한다.짝수 크기의 배열은 0번째가 최소값, 1번째가 최대값이 된다.홀수..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 10. 15.

[ 자료구조 ] 힙(heap)

개념특징힙은 영어로 ‘더미’다. 컴퓨터공학에서 힙은 데이터 더미를 완전이진트리 구조로 표현하여 최대값 또는 최소값을 빠르게 찾을 수 있는 자료구조다. 우선순위큐를 구현하는 데 자주 사용된다. 힙은 최대힙과 최소힙이 있다.최대힙최대힙은 루트노드가 최대값이다. 부모노드의 값이 자식노드의 값보다 커야한다.최소힙최소힙은 루트노드가 최소값이다. 부모노드의 값이 자식노드의 값보다 작아야한다.연산힙 연산이 끝난 후에도 완전이진트리 구조를 유지해야한다. 최대힙 기준으로 삽입연산과 삭제연산을 설명하면 다음과 같다.삽입연산데이터 삽입은 힙의 맨 끝에서 이뤄진다. 부모노드와 우선순위를 비교해 부모보다 자식이 높으면 부모와 자식의 위치를 바꾸면서 루트노드까지 비교한다.1. 이진트리의 맨 마지막 자리에 노드를 추가한다.2. 부..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 10. 7.

[ 알고리즘 ] 기준값에 의한 분할

알고리즘 목적기준값(pivot, 피벗)을 기준으로 배열을 분할하는 알고리즘이다. 배열을 피벗보다 낮은 영역과 피벗보다 큰 영역으로 나눈다. 영역을 나눈 후에 피벗을 자기 자리에 배치한다.기준값을 기준으로 배열을 분할한다고 해서 반드시 정렬되어야 하는 것은 아니다.시간복잡도는 Θ(N)이다.알고리즘 구현동작과정pivot을 정한다pivot보다 작은 값을 발견할 경우, 왼쪽 영역을 확장하고 자리를 교체한다.모든 데이터를 순회했으면 pivot을 배치한다.구현#include #include using namespace std;void Print(vector &arr) { for (int i = 0; i arr = {5, 2, 7, 3, 8, 5, 6, 4}; // vector arr = { 2, 8, ..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 9. 28.

[ 자료구조 ] Stack

#1 스택스택은 데이터를 쌓는 형태로 가장 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last in First Out) 자료구조다.#2 연산push스택에 데이터를 삽입하는 연산으로 스택의 가장 위에 데이터를 저장한다.pop스택에 데이터를 삭제하는 연산으로 가장 마지막에 저장한 데이터를 제거한다.peek스택의 가장 위 데이터를 확인한다.#3 스택의 사용파이썬# 빈 스택 초기화stack = []print("stack:", stack)# 스택에 원소 추가stack = [1, 2, 3]stack.append(4)print("stack:", stack)# 스택 원소 제거stack = [1, 2, 3]stack.pop()print("stack:", stack)# 스택 원소 찾기stack = [1, 2, 3..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 9. 26.