woonadz :)

동적 프로그래밍(Dynamic Programming)이란? 동적 프로그래밍(Dynamic Programming)은 작은 하위 문제로 나누어 그 결과를 저장해가며, 전체 문제를 해결하는 알고리즘 설계 기법입니다. 이를 통해 중복 계산을 줄여 계산 속도를 높이고 효율적으로 계산할 수 있습니다. DP 기법을 적용시킬 수 있는 조건 1. 중복되는 부분 문제(Overlapping Subproblems) 동일한 작은 문제들이 반복하여 나타나는 경우, 반복적으로 같은 문제를 해결하는 성질입니다. 2. 최적 부분 구조(Optimal Substructure) 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 성질로, 작은 문제의 최적해를 통해 큰 문제의 최적해를 구할 수 있습니다. DP 문제 풀이..

정렬이란? Key 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업. - 오름차순정렬 : 키 값이 작은 데이터를 앞쪽에 놓은 경우 - 내림차순정렬 : 키 값이 큰 데이터를 앞쪽에 놓은 경우 안정된 정렬 : 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것. 아래의 예시로 설명하자면 키란 5를 의미하고 요소는 하트와 스페이드를 의미한다. 오름차순으로 정렬하였음에도 (5,하트) 는 여전히 (5, 스페이드) 앞에 위치해있다. 내부 정렬 : 하나의 배열에서 작업할 수 있는 경우 사용하는 알고리즘 (버블, 선택, 삽입, 셸, 퀵, 병합, 힙, 도수 정렬 등등은 모두 내부정렬이다.) 외부 정렬 : 하나의 배열에서 작업할 수 없는 경우 사용하는 알고리즘 (외부 정렬은 내부..

재귀란? 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 '재귀적' 이라고 함. 직접 재귀와 간접 재귀 직접 재귀란 자신과 같은 함수를 호출하는 것. 간접 재귀란 함수 a가 함수 b를 호출하고, 다시 함수 b가 함수 a를 호출하는 구조이다. 재귀 알고리즘에 알맞은 경우 - 풀어야 할 문제가 재귀로 정의되는 경우 - 계산 할 함수가 재귀로 정의되는 경우 - 처리할 데이터 구조가 재귀로 정의되는 경우 유클리드 호제법 최대공약수는 y가 0이면 x이고, y가 0이 아닐 경우 gcd(y, x%y) 이다. 하향식 분석과 상향식 분석 하향식 분석이란 가장 위쪽의 함수 호출부터 시작해 계단적으로 자세히 조사해 가는 분석 기법으로 같은 함수의 호출이 여러번 나올 수 있기 때문에 경우에 따라 효율적..

1. 스택 스택이란? 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로 후입선출 구조이다. 2. 큐 큐란? 데이터를 일시적으로 쌓아 두기 위한 자료구조로 선입선출 구조이다. - 인큐(enqueue) : 데이터를 넣는 작업 - 디큐(dequeue) : 데이터를 꺼내는 작업 - 프런트(front) : 데이터를 꺼내는 쪽 - 리어(rear) : 데이터를 넣는 쪽 링 버퍼란? 베열의 처음과 끝이 연결되어있는 자료구조로 기존 큐에서 발생하는 요소 이동 문제를 해결할 수 있다. - 요소의 개수가 n인 배열에 계속해서 데이터가 입력될 때 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버리는 용도로 사용 가능.

※ 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘 선택 1-1. 검색 알고리즘 배열 검색에 사용되는 알고리즘 - 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행 - 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행 - 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행 방법 1) 체인법 : 같은 해시 갑스이 데이터를 선형리스트로 연결하는 방법 방법 2) 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법 1-2. 선형 검색 선형 검색(순차 검색)이란? 배열에서의 검색 : 원하는 키 값을 갖는 요소와 만날 때까지 맨 앞부터 순서대로 요소를 검색 ▷ 일반적으로 배열의 요소 개수가 n개일 때, 조건을 판단하는 횟수..

자료구조 : 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법. - 배열 : 같은 자료형으로 이루어진 요소가 모여 직선 모양으로 줄지어 있는 자료구조. | 상수식 : 상수만을 포함하는 식, 실행 시점이 아닌 컴파일 시점에 계산. | int a[5]; -> a[0]의 자료형은 int, 배열 a의 자료형은 int[5]형. - C언어 메모리 구조 : 프로그램이 실행될 때마다 RAM(메모리 영역)에 할당. | 데이터 영역 : 전역 변수와 정적 변수 할당, 프로그램 시작 시 할당하고 종료 시 메모리에서 해제. | 스택 영역 : 지역 변수와 매개변수 저장, 함수 호출 완료 시 사라짐. | 힙 영역(빈 공간) : 필요에 따라 동적 메모리 할당. - 난수 생성 | rand() : 이 함수가 반환하는 값은 0 ..

동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. -위키백과- 분할 정복과의 차이점 분할 정복은 큰 문제를 해결하기 어렵기에 작은 문제로 나누어 푸는 방법이다. 하지만 이 작은 문제가 포함된 큰 문제에서 이를 다시 풀어야 한다. 이러한 문제를 해결한 것이 동적 계획법이라고 할 수 있다. 동적 계획법은 큰 문제를 작은 문제로 나누어 푼다는 점에서 분할 정복과 유사하지만 작은 문제를 단 한번만 푼다는 점에서 차이점이 있다고 할 수 있다. 동적 계획법 풀이 한번만 푼 모든 작은 문제의 답을 어딘가(배열..

기록용 3줄 TMI 알고리즘 스터디 날짜가 조금씩 밀렸다. 이는 내가 나태해지고 있다는 걸 의미하는 것 같아 반성을 하고 있다. 이번주 활동부터는 정말 절대로 미루지 않을 것이다. 나는 약속을 정말 중요하게 생각하는데 활동이 밀리는 걸 보며 회의감이 든다. 백 트래킹이란? 모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. -나무위키- 라고 정의되어있긴 하지만 내가 생각하는 정의와는 좀 다르다..