'유클리드 호제법'이란? 유클리드 호제법(혹은 유클리드 알고리즘)은 빠르게 최대공약수(GCD)를 구하는 알고리즘입니다. 참고로 GCD는 Greatest Common Divisor의 약어! LCM은 Least Common MultiPle의 약어! '유클리드 호제법'의 원리 두 자연수 a, b가 주어졌을 때, a를 b로 나눈 나머지가 temp라고 하면, temp가 0일 때 b가 최대공약수(GCD)입니다. 만약 temp가 0이 아니면 a에 b값을 넣고, b에 temp값을 넣은 다음 위 과정을 반복합니다. '유클리드 호제법'의 구현 방법 반복문을 이용해 구현하거나 재귀함수를 이용해서 구현할 수 있습니다. 먼저 반복문을 이용해 구현하는 법을 소개하겠습니다. int gcd(int a, int b) { int tem..
다이나믹 프로그래밍과 메모이제이션 알고리즘을 비교해보겠습니다. 다이나믹 프로그래밍은 모든 subproblem들을 전부 구해야하는 문제에 적용하면 좋습니다. 메모이제이션은 모든 subproblem들을 전부 구해야하는 경우, stack에서 왔다갔다하는 overhead가 있기 때문입니다. 반면, 메모이제이션은 subproblem을 전부 다 계산하지 않아도 되는 문제에 적용하면 좋습니다. 이전에 계산한 결과를 다시 계산할 필요가 없기 때문입니다. 코드를 통해 비교 및 이해를 해보도록 하겠습니다. 피보나치 수열을 다이나믹 프로그래밍과 메모이제이션으로 각각 구현해보겠습니다. 먼저 다이나믹 프로그래밍 기법을 이용한 피보나치 수열 구현 방법입니다. int fibonacci(int n) { if (n < 2) { ret..
Binary Heap(이진 힙)은 Complete Binary Tree 형식의 자료구조입니다. Complete Binary Tree는 배열에 기반하고 있기 때문에 random access가 가능합니다. Complete Binary Tree에 대한 설명은 아래 게시물을 참고해주세요. http://dvpzeekke.tistory.com/m/45 BST(Binary Search Tree, 이진 탐색 트리) BST(Binary Search Tree, 이진 탐색 트리) BST(Binary Search Tree, 이진 탐색 트리)는 이진 탐색 알고리즘을 트리에 적용한 자료구조입니다. 이진 탐색 트리의 정의는 다음과 같습니다. - 노드에 저장된 Key(키).. dvpzeekke.tistory.com Heap에는 Ma..
BST(Binary Search Tree, 이진 탐색 트리) BST(Binary Search Tree, 이진 탐색 트리)는 이진 탐색 알고리즘을 트리에 적용한 자료구조입니다. 이진 탐색 트리의 정의는 다음과 같습니다. - 노드에 저장된 Key(키)는 유일하다. - 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다. - 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다. - 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 이진 탐색 트리의 탐색 연산은 O(log n)의 time complexity를 갖습니다. 이진 탐색 트리의 높이는 log (n + 1)이기 때문입니다. 하지만 이진 탐색 트리가 한 쪽으로 편향되어 있다면(Skewed Tree, 편향 트리) ti..
Tree(트리) Tree(트리)는 Hierarchical Relationship(계층적 관계)를 표현하는 자료구조입니다. 트리를 구성하는 구성 요소들은 다음과 같습니다. - Node(노드) : 트리를 구성하는 각각의 요소 - Edge(간선) : 노드와 노드를 연결하는 선 - Root Node(루트 노드) : 트리의 최상위 노드 - Terminal Node( = leaf Node, 단말 노드) : 트리의 최하위 노드 - Internal Node(내부 노드, 비단말 노드) : 단말 노드를 제외한 모든 노드(루트 노드 포함) - Sub-Tree(서브 트리) : 루트 노드를 제거한 후 남아있는 부분 트리 - Degree of Node(노드의 차수) : 특정 노드에 연결된 서브 트리의 수 - Level(레벨) :..
List(리스트)는 동일한 자료형으로 된 원소들의 모임으로 linear list(선형 리스트)와 linked list(연결 리스트)로 나뉩니다. Linear list의 종류로는 배열, 스택, 큐, 순환 큐 등이 있습니다. Stack(스택) stack은 linear list의 일종으로, LIFO(Last-In, First-Out) 특징을 가집니다. 즉, 나중에 들어간 원소가 먼저 나오고, 먼저 들어간 원소가 나중에 나옵니다. 선반에 접시를 차곡차곡 쌓는 것을 연상하시면 됩니다. 접시를 하나 쌓을 때 stack의 가장 위 접시에 쌓고, 접시를 하나 집을 때, stack의 가장 위 접시를 집는 상황과 일치합니다. Queue(큐) queue는 linear list의 일종으로, FIFO(First-In, Firs..
List(리스트)는 동일한 자료형으로 된 원소들의 모임으로 linear list(선형 리스트)와 linked list(연결 리스트)로 나뉩니다. linear list의 종류로는 배열, 스택, 큐, 순환 큐 등이 있습니다. 이번 포스팅에서는 배열과 연결 리스트의 차이에 대해 설명합니다. Array(배열) Array(배열)은 가장 많이 사용되는 자료구조 중의 하나로 자료형이 동일한 원소들의 유한집합으로 정의됩니다. array에 속한 각 원소들은 메모리에 연속적으로 저장되어 논리적 저장 순서와 물리적 저장 순서가 일치합니다. 따라서 고유의 index를 통하여 random access가 가능합니다. 따라서 찾고자 하는 index의 값을 알고 있으면 O(1)에 해당 원소로 접근이 가능합니다. 하지만 삭제 혹은 삽..
BFS 알고리즘은 깊이를 우선으로 탐색하는 알고리즘 입니다. 즉, 현재 정점에 갈 수 있는 노드까지 들어가며 탐색합니다. 주로 stack 혹은 재귀함수를 이용해서 구현합니다. c++로 dfs를 구현해보겠습니다. 위 그래프의 1 노드에서 갈 수 있는 노드까지 들어가며 탐색합니다. 아래 코드를 참고해주세요. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include #include using namespace std; vector graph(7, vector ()); vector visit(7, false); void..
BFS 알고리즘은 너비를 우선으로 탐색하는 알고리즘 입니다. 즉, 현재 정점에 연결된 가까운 노드부터 탐구합니다. 주로 queue를 이용해서 구현합니다. c++로 bfs를 구현해보겠습니다. 위 그래프에서 1 노드와 가까운 노드부터 탐색하고 노드 번호를 출력합니다. vector 타입의 graph는 각 노드 간의 연결 정보를 나타냅니다. queue 타입의 q는 노드들이 가까운 순서대로 출력되기 위해 사용됩니다. vector 타입의 visit은 노드 방문 여부를 나타냅니다. 아래 코드를 참고해주세요. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 4..
- Total
- Today
- Yesterday
- 구슬탈출
- 깊이우선탐색
- algorithm
- dp
- Programmers
- aws
- 백준
- 스위프트
- 삼성역량테스트
- Xcode
- 컬렉션
- 이진트리
- 자료구조
- dfs
- count
- 호제법
- Swift
- ec2
- c++
- 코딩테스트
- 시뮬레이션
- isempty
- 서머코딩
- 알고리즘
- ios
- SummerCoding
- BFS
- datastructure
- 프로그래머스
- Collection
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |