코딩아 재윤해

연결 리스트(linked list) 자료구조는 선형으로 그룹화된 데이터의 집합으로 데이터와 다음 데이터의 주소를 포함하고 있는 하나의 노드가 선형으로 연결된 자료구조이다. 예를 들어, 보물 찾기를 한다면 힌트 메모지 하나하나를 노드로 만들고 첫 번째 힌트 메모지에는 다음 메모지가 어디 있는지를 표시해 놓는 방식이다. 특징 배열에 비해 노드의 추가와 삭제가 용이하다. 노드가 메모리에 흩어져 있어서 특정 노드로 쉽게 접근할 수 없다. 즉, 노드의 값을 찾으려면 전체를 순회해야 할 수도 있다. 배열은 데이터에 접근하는데 O(1)의 시간 복잡도를 가지지만, 연결 리스트는 최악의 경우에 O(n)의 시간 복잡도를 갖는다. 종류 단순 연결 리스트(Singly Linked List) : 다음 노드에 대한 참조만을 갖는..

이진 탐색 알고리즘은 검색 범위를 줄여 나가면서 원하는 데이터를 검색할 때 사용하는 알고리즘이다. 오름차순으로 정렬된 리스트를 반으로 나누고 찾는 원소가 중간에 있는지 확인하고, 없으면 위쪽 또는 아래쪽에 있는지를 판단하여 다시 같은 방식으로 원소를 찾는 방법이다. 게임 'up & down'을 예로 들면, 1부터 100까지의 수 중에서 41이라는 숫자를 찾는다고 한다. 먼저 중간 값인 50이나 51중에서 찾으려는 41이 두 값보다 작기 때문에 1부터 49를 새로운 범위로 설정해서 찾는다. 다시 절반인 25를 기준으로 찾으려는 41이 크기 때문에 26부터 49까지 새로운 범위로 설정해서 찾는다. 이렇게 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 방법을 이진 탐색 알..

컴퓨터 과학에서 Brute Force는 시행착오 방법론을 말한다. 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 모두 나열하면서 답을 찾는 방법이다. 이 방법은 직관적이어서 이해하기 쉬우며 문제의 정확한 답을 얻어낼 수 있는 가장 확실하고 기초적인 방법이다. 예를 들어, 4개의 숫자로 구성된 자물쇠를 푼다고 하면 0000부터 9999까지 모두 시도해 보면 해결할 수 있다. 이렇게 하나하나 대입하여 시도하는 방식 완전 탐색 알고리즘이라고 한다. 완전 탐색 알고리즘은 공간 복잡도와 시간 복잡도의 요소를 고려하지 않고 솔루션을 찾으려고 하는 방법이기 때문에 최적의 솔루션은 아닐 수 있다. 사용 완전 탐색 알고리즘은 크게 다음과 같은 두 가지 경우에 사용한다. 프로세스 속도를 높이는 데 사용할 수 있는 ..

덱(Double-Ended Queue, Deque)은 양방향 대기열이라고도 불리는 자료구조이다. 외형적으로는 queue와 비슷한 구조를 갖고있으며, 한 방향인 queue와 stack과는 다르게 LIFO, FIFO같은 순서에 구속되지 않는다. 즉, 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하며 어떤 쪽으로 입력하고 출력하느냐에 따라서 stack과 queue로 사용할 수 있다. 이때, 한쪽으로만 입력이 가능하도록 설정한 덱을 스크롤(scroll)이라고 하고 한쪽으로만 출력이 가능하도록 설정한 덱을 셸프(shelf)라고 한다. 특징 덱은 다음과 같은 특징을 갖고 있다. Stack 및 Queue를 모두 사용할 수 있다. 덱은 양쪽으로 데이터를 추가하고 삭제할 수 있기 때문에 둘 다 구현이 가능하다. 만약 양쪽 ..

탐욕 알고리즘(greedy algorithm)은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 즉, 최적해를 구하는 데에 사용되는 근사적인 방법이다. 순간마다 하는 선택은 그 순간에 한해서는 최적이지만 그러한 선택들을 통해 최종적인 해답을 얻었다고 해서 그 해답이 최적이라는 보장이 없다. 예외의 상황이 있을 수 있기 때문이다. 따라서, 이러한 예외 상황을 배제하고 탐욕 알고리즘을 통해 최적의 해를 구하기 위해서는 다음과 같은 두 가지 조건을 만족시켜야 한다. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최적해가 부분문제에..

알고리즘 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 생각하는 것이다. 즉, 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킨다. 효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성한다는 것이다. 시간 복잡도를 표기하는 방법은 Big-O, Big-Ω, Big-θ가 있으며, 이 세 가지 표기법은 각각 최악, 최선, 평균의 경우에 대하여 나타내는 방법이다. 주로 Big-O 표기법을 사용한다. Big-O 표기법을 주로 사용하는 이유는 다음과 같다. 바로 프로그램이 실행되는 과정에서 소요되는 최악의 경우 시간까지 고려할 수 있기 때문이다. '최소 이 정도 시간 이상이 걸린다' 고려하기보다는 ..

탐색 알고리즘이란 방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘이다. 알고리즘의 영역은 그 범위가 매우 넓어서 프로그래밍을 하는 개발자라면 의도하지 않아도 특정 알고리즘을 사용하는 경우가 대부분일 정도이며, 알고리즘의 종류 중에서도 탐색 및 정렬은 가장 많이 사용된다. 그래프의 탐색은 하나의 노드에서 시작해서 모든 노드들을 한 번씩 탐색하는 것이 목적이다. 예를 들면, 특정 장소에서 다른 장소로 갈 수 있는지, 최단 경로를 찾는 경우 등 있다. 그래프의 데이터는 배열처럼 정렬되어있지 않기 때문에 원하는 데이터를 찾기 위해서는 모두 방문해서 찾아야 한다. 너비 우선 탐색(Breadth-First Search, BFS) 너비 우선 탐색이란 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는..

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회(tree traversal)라고 한다. 선형 자료 구조(stack, queue 등)는 순차적으로 요소에 접근하지만, 트리 구조는 계층적 구조라는 특징을 갖고 있기 때문에 모든 노드를 순회하기 위해서는 다른 방식을 사용해야 한다. 트리를 순회하는 방법은 크게 전위 순회, 중위 순회, 후위 순회가 있으며, 노드를 방문하는 순서에 의해 결정된다. 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽으로 한다. 전위 순회(preorder traversal) 전위 순회는 다음과 같은 방법으로 진행한다. 루트 또는 서브트리의 루트 노드를 방문한다. 왼쪽 서브 트리를 방문한다. 오른쪽 서브 트리를 방문한다. 방문 순서 : 1 ..

이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다. 여기서 자식 노드들은 왼쪽 자식 노드, 오른쪽 자식 노드로 나뉜다. 이진 트리는 자료의 삽입, 삭제 방법에 따라서 다음과 같이 나뉜다. 정 이진 트리(ful binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다. 포화 이진 트리(perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 트리이다. 완전 이진 트리(complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있으며, 마지막 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다. 이진 탐색 트리(bi..

그래프(graph)는 여러 개의 점들이 서로 복잡하게 연결되어 있는 그래프이다. 그래프는 연결할 객체를 의미하는 정점(vertext)과 객체를 연결하는 간선(edge)의 집합으로 구성되어 있다. 두 정점을 이어주는 선이 있으면 직접적인 관계이고 몇 개의 점과 선에 걸쳐서 이어진다면 간접적인 관계이다. 이어진 선에 화살표 방향이 없으면 무방향 간선, 하나의 방향이 있으면 단방향 간선, 양쪽 모두 방향이 있으면 양방향 간선이라고 한다. 실사용 예시로는 포털 사이트의 검색 엔진, 네비게이션(길 찾기) 등이 있다. 표현 방식 인접 행렬 : 두 정점을 바로 이어주는 간선이 있다면 두 정점은 인접하다고 말하며, 가장 빠른 경로를 찾고자 할 때 주로 사용한다. 인접 리스트 : 각 정점이 어떤 정점과 인접하는지를 리스..