K-MOOC 스터디 - 알고리즘, 자료구조

Recursion - 재귀

분할 정복(Divite-and-Conquer)

배열, 다항식 표현법, 희소행렬 표현법

해시

스택 스택은 가장 최근에 입력된 데이터가 가장 먼저 출력되는 입출력 자료구조이다. (후입선출, LIFO: Last-In-First-Out) 스택의 구조는 리스트가 스택 하단(bottom)부터 쌓이는 요소로 구성되며, 스택 상단(top)에 삽입되고 삭제되는 함수가 있다

리스트 리스트의 특징 리스트에서 항목들은 차례대로 저장된다. 리스트의 항목들은 순서 또는 위치를 가진다. 각 항목 간 순서의 개념이 없는 집합과는 다르다. 스택과 큐도 넓게 보면 리스트의 일종이다. 리스트의 기본 연산 삽입: 리스트에 새로운 항목을 추가 삭제: 리스트에서 항목을 삭제 탐색: 리스트에서 특정한 항목을 찾음 리스트의 구현 배열을 이용한 구...

힙(heap)은 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 수행하기 위해 고안된 이진 트리이다. 부모 노드의 키 값이 자식 노드의 키 값보다 크거나(혹은 작거나) 같다. 최댓값 또는 최솟값을 가장 먼저 출력하는 우선순위 큐라고 볼 수 있다. 힙의 종류에는 최대 힙, 최소 힙이 있다. 최대 힙: 가장 큰 값을 먼저 찾는 힙 최소 힙: 가장 작은 값을 먼저...

스택 활용 스택을 활용하여 괄호 검사 문제 프로그램을 만들 수 있다. 왼쪽 괄호가 입력되면 스텍에 push하며 오른쪽 괄호가 입력되면 스택에서 pop된다. 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다. 또한 스택을 활용하여 후위 표기 수식의 계산을 하는 프...

https://hongjw1938.tistory.com/78 를 참고하여 작성함. 완전탐색 알고리즘 완전탐색 알고리즘은 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법. "Brute Force"라고 부르며, 직관적으로 이해하기 쉽고 문제의 정확한 결과값을 얻어

큐 활용 큐를 활용하여 은행 대기 시간 계산 시뮬레이션 프로그램을 만들 수 있다. 은행에서 고객이 들어와서 서비스를 받고 나가는 과정을 시뮬레이션하여 고객들이 기다리는 평균 시간을 계산한다. 현재 시각을 나타내는 clock 변수 값을 1 증가하면서 [0, 10] 난수를 생성하여 3보다 작으면 새로운 고객이 은행에 들어온 것(enqueue)으로 판단한다. 만...

그리디 알고리즘(Greedy algorithm)은 최적해를 구하는 데에 사용되는 근시안적(local)인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

트리는 비선형적(nonlinear) 자료구조 중에서 계층적(hierarchical) 자료구조이다.

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드라고 부른다. 이진 트리의 종류 루트 이진 트리 : 하나의 루트 노드를 가지며 모든 노드가 최대 두 개의 자식 노드를 갖는다. 정 이진 트리 : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리다. 포화 이진 트리 : 모든 내부 노드가 두 개...

깊이 우선 탐색 깊이 우선 탐색(DFS)은 맹목적 탐색 방법의 하나. 탐색 트리의 최근에 추가된 노드를 선택하고, 노드에 적용 가능한 동작 방법 중 하나를 적용하여 트리에 다음 레벨의 한 개의 자식노드를 추가하여, 추가된 자식 노드가 목표 노드일 때 까지 앞의 자식 노드 추가 과정을 반복해 가는 방식이다. 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 ...

[geek-for-geeks의 원문을 참고하여 작성한 글입니다.] 동적 프로그래밍(DP)은 대개 일반 평문 재귀함수에 대한 최적화 과정입니다. 반복적인 함수 호출에 대해 우리는 DP를 사용하여 최적화 할수 있다. DP는 나중에 필요할 때 다시 연산하지 않기 위해서 subproblem들의 결과값을 간단히 저장합니다. 이 최적화 방식은 지수 다항식으로부터의 ...

그래프 그래프는 정점과 간선으로 구성된 비선형 데이터 구조입니다. 정점은 노드라고도 불리며 간선은 그래프에서 두 노드를 연결하는 선이나 호로 표시됩니다. 공식적으로 그래프는 정점(V)의 집합과 간선(E)의 집합으로 구성됩니다. 그래프는 G(V, E)로 표시됩니다. 그래프 데이터 구조는 오브젝트나 엔티티 사이의 복잡한 관계를 분석하고 표현하는데 강력한 도구...