Computer Science

정의및장단점 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 이진트리와 힙 공통점: 힙과 이진 탐색 트리는 모두 이진 트리임 차이점: 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우) 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오..

정의 및 장단점 순차탐색(일반적인 탐색)과 달리 이진 탐색은 배열내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐색은 매우 빠른 탐색이다. 탐색범위를 절반씩 좁혀가며 데이터를 탐색한다. 이진탐색은 위치를 나타내는 변수3개를 사용하는데 탐색하고자 하는 범위의 시작점(low),중간점(middle),끝점(high)이다. 찾으려는 데이터와 중간점(mid)위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. log2N의 시간이 걸리고 빅오 표기법에 따라 간단하게 표현하면 O(logN)이다. 탐색대상의 데이터가 큰 문제의 경우 이진탐색을 이용하여 풀어야 한다. 문제조건을 잘 살피자. 이진탐색문제의 경우 이진탐색코드형식을 미리 암기 해놓으면 아주 쉽게 구현할 수..

해시(Hash) 자료구조 해시(Hash) 구조란, 키(Key)와 값(Value) 쌍으로 이루어진 데이터 구조입니다. 해시 구조에서는 Key 를 이용하여 데이터(value)를 빠르게 찾을 수 있는 장점이 있습니다. 파이썬에서 사용하는 dictionary type 이 해시구조입니다. 해시와 관련된 몇가지 용어들에 대해 알아보겠습니다. 키 (Key) : 해시 함수의 input 이 되는 고유한 값. 키(key)는 해시함수(hash function)를 통해 해시(hash)로 변경되어 value 값과 매칭되어 저장소에 저장됩니다. 해시 (Hash) : 임의의 값을 고정 길이로 변환하는 것 key 값 그대로 저장소에 저장되게 되면 다양한 길이의 저장소를 구성해야하기 때문에 효율성을 위해 일관적으로 해시(hash)로 ..

트리 자료 구조중에서 가장 간단한 형태가 이진 탐색 트리이다. 이진탐색트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리) 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 예를 들어 다음과 같은 트리가 이진탐색트리이다. 이진 탐색 트리의 특징 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 ..

정의 및 장단점 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열 하는 것을 말한다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 있어야 한다. 정렬 알고리즘은 굉장히 다양한데 대표적인 몇가지만 설명하겠다. 여러정렬은 각각의 장단점이 존재한다. 각 상황에 맞는 정렬을 선택하여야한다. 일반적으로 라이브러리에서 제공하는 정렬은 퀵소트 또는 변형된 퀵소트이다. 평균 nlogn에서 n^2의 시간복잡도를 가진다. 기수정렬: O(N) 또는 O(N+K) N은 개수, K는 숫자범위크기 (ex. 0~99면 100) 계수정렬: O(N) 또는 O(N+K) N은 개수, K는 최대자리수 선택 정렬(selection) 선택정렬은 앞에서부터 차례대로 정렬하는 방법입니다. 먼저 주어진 리스트 중에 최소값을 찾..

정의 트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조입니다. 트리는 다음과 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사합니다. 트리는 또한 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 합니다. 컴퓨터의 direcory구조가 트리 구조의 대표적인 예가 될 수 있습니다. 트리 구조에서 사용되는 기본 용어 노드 (Node) 트리를 구성하고 있는 기본 요소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음. A, B, C, D, E, F, G, H, I, J 간선 (Edge) 노드와 노드 간의 연결선 루트 노드 (Root Node) 트리 구조에서 부모가 없는 최상위 노드 root node : A 부모 노드 (Pare..

정의 및 장단점 BFS는 Breadth First Serach로 너비우선탐색이다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리있는 노드를 찍고 돌아오고 멀리갔다가 돌아로는 탐색이다. BFS는 그 반대이다. 구현방법 BFS는 큐 자료구조를 이용한다. 큐를 이용하면 자연스럽게 먼저들어온것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다. 파이썬에서는 deque라이브러리를 이용한 큐 자료구조를 사용하는 것이 보편적이다. 시간복잡도는 O(N)의 시간이 소요된다. 일반적인 경우 실제 수행시간이 DFS보다 좋은편이다. 문제에 따라 DFS의 경우 무한굴레에 빠져 시간이 엄청 길어 질수 있다. 하지만 BFS는 가까운노드에서부터 점차적으로 넓혀가기 때문에 보다 안정적이다. 모든 경우의..

정의 및 장단점 DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 연결되어 있는 노드를 깊숙히 바고 들어간다. 그 노드의 끝을 보고 다시 돌아오면서 연결되어있는 다른 노드를 찾을시 이번엔 그 노드를 끝까지 파고든다. 스택을 기초로 하고 있다. 구현방법 스택, 재귀함수를 이용하여 구현한다. 스택을 기초로 하지만 직접적으로 사용하지는 않음. O(N)의 시간이 소요. 문제 예시 NxM의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구머이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크..