Dominic Repo

트리(Tree) 데이터의 검색과 탐색에 아주 널리 이용되는 자료 구조. 트리란, 뿌리(루트; root)노드에서 간선(edge)들이 마치 나무에서 뿌리로부터 잔가지로 뻗어나가듯이 가지치기된 구조를 말한다. 딱딱하게 말하면, 순환하는 길이 없는 그래프(graph)로 정의 트리에 대한 학습의 바탕을 마련하기 위해, 아래와 같은 용어들이 무슨 뜻인지를 배운다. 노드(nodes) : 트리에서 각각 원소들을 의미한다. 간선(edges) : 노드들을 이어주는 것 루트 노드(root node) : 최상위 노드 리프 노드(leaf nodes) : 더이상 가지를 치지 않는 노드 내부 노드(internal nodes) : 루트 노드와 리프 노드 사이에 있는 노드들 부모(parent)노드와 자식(child)노드 노드의 수준(..

큐(Queue) 스택과 더불어 매우 빈번하게 이용되는 자료 구조가 큐(queue)이다. 선형(linear)구조라는 점에서는 지금까지 배워온 선형 배열, 연결 리스트, 그리고 스택과 같은 성질을 가지고 있지만, 스택과는 어떻게 보면 반대인 특성을 가지고 있다. 큐는 선입선출(FIFO; First-In First-Out), "파이포" 라고도 많이 부른다. 환형 큐(Circular Queue) 큐(queue) 또한 스택과 마찬가지로 컴퓨터 시스템을 구성하는 많은 곳에서 이용된다. ex) 어느 컴퓨터 시스템에서 서로 다른 응용 프로그램들이 프린터에 인쇄할 문서를 보낸다고 생각해보자. 시스템(보다 명확하게는 운영체제) 내에서는 프린팅 큐라는 자료 구조를 유지하여 프린터에 보내진 인쇄할 문서들을 유지할 수 있다.(..

스택(Stack) 마치 접시를 차곡차곡 쌓았다가 맨 위의 접시부터 다시 꺼내어 사용하는 것처럼, 추가된 데이터 원소들을 끄집어내면 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료구조를 스택(stack)이라고 한다. 스택은 후입선출(LIFO; Last-In First-Out)자료구조 그러면 이러한 스택은 어디에 쓰일까?? 컴퓨터 내부에서 프로그램이 실행할 때 함수 호출이 일어나고 함수들이 리턴하면 마지막 호출된 곳으로 동작을 구현하는 데에도 스택이 이용되고, 이러한 일은 컴퓨터의 동작에 핵심적인 것이기 때문에 컴퓨터 하드웨어(프로세서)는 어떤 방식으로든 스택을 내부적으로 관리하는 기능을 갖고 있습니다. 쉽게 이야기하면 재귀함수가 줄줄이 호출되었다가 리턴하는 모습을 생각하면 편합니다. 스택의 응용..

양방향 연결 리스트(Doubly Linked Lists) 말 그대로 노드들이 앞/뒤로 연결되어 있는 리스트를 뜻한다. 단점링크를 나타내기 위한 메모리 사용량이 늘어난다. 또한, 원소를 삽입/삭제하는 연산에 있어서 앞/뒤의 링크를 모두 조정해 주어야 하기 때문에 귀찮다. 그럼에도 불구하고 아래와 같은 장점이 있기에 쓴다. 데이터 원소들을 차례로 방문할 때, 앞에서도 할 수 있지만 뒤에서부터 앞으로도 할 수 있다는 점, 컴퓨터 시스템의 주요 구성 요소인 운영체제(Opeation System)등에서는 리스트를 대상으로 앞/뒤로 왔다 갔다 하면서 작업을 행하는 일들이 빈번히 요구되고, 따라서 양방향 연결 리스트가 많이 이용되고 있다. 본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니..

연결리스트(Linked Lists) 선형 배열과는 다르다. 선형 배열은 "번호가 붙여진 칸에 원소들을 채워 넣는" 방식이라면 연결 리스트는 "각 원소들을 줄줄이 엮어서" 관리하는 방식이다. 장점으로는 삭제하거나 삽입하는것이 선형 배열의 경우보다 쉽다. (빠른 시간 내에 처리할 수 있다는 뜻) 이러한 이점 때문에, 원소의 삽입/삭제가 빈번히 일어나는 경우에는 연결 리스트가 많이 이용됩니다. 컴퓨터 시스템을 구성하는 중요한 요소인 운영체제(Operation System)의 내부에서도 이러한 연결 리스트가 여러 곳에서 이용되고 있습니다. 단점으로는 선형 배열에 비해 데이터 구조 표현에 소요되는 저장 공간(메모리) 소요가 크다. 또 "i번째의 원소"를 찾아가는 데에 시간이 더 걸린다.(앞에서부터 하나씩 링크를 ..

알고리즘의 복잡도란? 알고리즘이 실행함에 있어, 문제의 크기(일반적으로 데이터 원소의 개수를 뜻함)가 커짐에 따라서 얼마나 큰 시간을(또는 공간을) 요구하느냐를 뜻한다. 시간 복잡도, 공간 복잡도로 나누어진다. 시간 복잡도는 문제가 커짐에 따라 이 문제를 해결하는데 소요되는 시간이 어떤 양상으로 증가하는가를 다루고 공간 복잡도는 문제가 커짐에 따라 이 문제를 해결하는데 소요되는 기억 공간(메모리)의 필요가 어떤 양상으로 증가하는가를 다룬다. 본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다. 출처 : 프로그래머스 : 어서와! 자료구조와 알고리즘은 처음이지?

알고리즘의 아니라 성질이다. 주어진 문제가 있을 때, 이것을 같은 종류의 보다 쉬운 문제의 답을 이용해서 풀 수 있는 성질을 이용해서, 같은 알고리즘을 반복적으로 적용함으로써 풀어내는 방법이다. 일반적으로, 주어진 문제에 대해서 반복적인 알고리즘이 재귀적인 알고리즘보다 문제 풀이의(시간적) 효율이 높다. 그럼에도 불구하고, 쓰는 이유는 매우 직관적으로 적용할 수 있는 경우가 많기 때문이다. 본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다. 출처 : 프로그래머스 : 어서와! 자료구조와 알고리즘은 처음이지?

정렬(Sort)이란? 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업 Python의 list를 정렬하는 법 파이썬 내장 함수 sorted() 리스트에 쓸 수 있는 메서드 .sort() Python 문자열은 대문자가 소문자에 비해서 무조건 우선합니다. 탐색(Search)이란? 복수의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업. 선형 탐색(linear search) or 순차 탐색(sequential search): 순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아냄. O(n) 이진 탐색(binary search): 탐색하려는 배열이 이미 정렬되어 있는 경우에만 적용 가능, 미들값을 정해 반씩 쪼개서 찾아감. O(log_n) 본 문서는 프로그래머스 어서와! 자료구조와 알고리..

선형 배열(Linear Array) 선형 배열은 데이터들이 선(line)처럼 일렬로 늘어선 형태를 말함. Python 리스트에 활용할 수 있는 연산들 리스트 길이와 관계 없이 빠르게 실행 결과를 보게되는 연산들 원소 덧붙이기 .append() 원소 하나를 꺼내기 .pop() 리스트의 길이에 비례해서 실행 시간이 걸리는 연산들 원소 삽입하기 .insert() 원소 삭제하기 .del() 추가 다른 연산 원소 탐색하기 .index() 본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다. 출처 : 프로그래머스 : 어서와! 자료구조와 알고리즘은 처음이지?