문제 해결을 하다 보면 함수에서 다른 함수를 호출해야 할 때가 있다. 이때 함수가 자기 자신을 호출할 수도 있는데, 이를 재귀 라고 부른다.함수가 자신을 호출하는 단계를 재귀 단계(recursion step)라고 부른다. basis라고도 불리는 재귀의 베이스(base)
알고리즘은 어떤 일을 하기 위한 명령의 집합이다. 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미한다.알고리즘은 각기 다른 모양과 형태를 가지고 있기 때문에 타임 복잡도를 설명하는데 자주 사용된다.시간 복잡도를 분석하는 것은 알고리즘이
가장 큰 값이 버블처럼 위로 올라가는 모양을 하게 되는 알고리즘버블 정렬은 O(n^2)이기 때문에 성능이 좋지 않다.
알고리즘 문제를 풀다보면 완전탐색으로 해결해야 하는 문제들이 있다.완전탐색은 단어 그대로, 생길 수 있는 모든 경우의 수에 대해서 조건이 성립하는 지를 알아보는 것 자체를 말한다.순열과 조합을 사용해서, 완전탐색을 할 대상에 대해 자료형을 구축해보자.조합은 서로 다른
A와 B의 공통된 약수 중에 가장 큰 정수를 최대 공약수라고 한다.2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.유클리드 호제법의 기본 원리는 A를 B로 나눈 나머지를 R라고 했을 때
자료구조가 무엇인지 설명할 수 있다.Stack, Queue, Tree, Graph 자료구조에 대해 이해할 수 있다.알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내낼 수 있다.각 자료구조의 개념과 구조를 파악하고 목적을 이해할 수 있다.알고리즘
그래프는 단순히 정점(vertex, node)과 간선(edge)으로 구성된 자료구조이다.도로로 연결된 여러 마을을 표시한 지도를 생각해보자.지도도 일종의 그래프라고 할 수 있다.지도에서 각 마을은 정점이며 도로가 간선이다.간선은 (v1, v2)와 같은 쌍으로 정의하며,
그래프 탐색이란?하나의 정점에서 시작해서 그래프의 모든 정점들을 한번씩 탐색하는 것을 말한다.그래프 전체를 탐색하는 방법 중 하나.루트 노드 (혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법.넓게(wide) 탐색하기 전에 깊게(deep) 탐색한다.모든 노드를 방문 하고자 하는 경우에 이 방법을 사용한다.DFS가 BFS보다 좀
노드로 구성된 계층적 자료구조.노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.트리는 1개 이상의 노드로 구성되며, 하나의 루트 노드를 갖는다.최상위 노드인 루트는 0개 이상의 자식 노드를 갖는다.그 자식 노드의 자식 노드가 존재하는 구조가 반복
트리를 순회할 수 있는 세 가지 방법은 전위 순회, 중위 순회, 후위 순회입니다. 이 순회 방식과는 논외로, 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽입니다.
우선순위 큐를 위해 만들어진 자료구조, heap일반적인 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.즉, 어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조이다.우선순위 큐(Prior
힙 중에서 가장 널리 쓰이는 형태 중 하나로 이진 트리 형태의 힙.이진 트리는 각 노드의 자식 노드가 반드시 2개 이하인 트리이다.이진 힙은 완전 이진 트리라는 조건을 만족해야 한다.모든 레벨의 노드가 채워져 있어야 하며, 마지막 레벨은 왼쪽부터 채워져 있어야 한다.새
힙(Heap)에는 최대힙(Max heap), 최소힙(Min heap) 두 종류가 있다.최대 힙: 부모 노드는 항상 자식 노드보다 크거나 같아야 한다.최소 힙: 부모 노드는 항상 자식 노드보다 값이 작아야 한다.즉, 최대 힙의 루트는 힙 내에서 가장 큰 값, 최소 힙의