Algorithm/기본적으로 알아야 할 것들

Algorithm 핵심 개념들

Algorithm은 '문제를 어떤 식으로 푸는 것이 최선인가' 로 정의될 수 있다. Time Complexity Algorithm 문제들을 풀 때는 문제에 대한 해답을 찾는 것도 중요하지만 '더 효율적인 방법은 없을까?'에 대한 고민도 중요하다. 효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같다. 그리고 시간 복잡도를 고려한다는 것은 한 문장으로 정리하자면 다음과 같다. 입력값의 증가 및 감소에 따라 시간이 얼마만큼 비례하여 증가 및 감소하는가? Big-O 표기법 시간 복잡도를 표기하는 방법 중에는 다음과 같은 방법들이 있다. Big-O Big-Ω Big-θ 위 표기법들은 각각 최악, 최선, 평균의 경우 입력값의 증가에 따라 시간 복잡도가 얼마나 증가하는지 표기하는 방법들이다. 이 중에..

Data Structure 핵심 개념들

"자료 구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것" 데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다. 우리의 이름, 나이, 키, 집 주소, 목소리 혹은 유전자 DNA까지 데이터로 분류할 수 있다. 그러나 데이터는 그 자체만으로 어떤 정보를 가지기 힘들다. 예를 들어 나이라는 데이터만 알고 있다면, 사람의 나이인지 나무의 나이인지 알 수 없다. 이처럼 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다. 뿐만 아니라 데이터를 사용하려는 목적에 따라 형태를 구분하고, 분류하여 사용할 수 있다. 전화번호부를 작성할 때, 숫자를 3개 또는 4개씩 묶음짓고 하이픈(-)으로 합친다. 이 숫자의 묶음에 이름을 붙여 보관해야 한다면, 해당 데이터를 꺼낼..

Binary Tree의 3가지 순회방법 구현하기

Binary Tree Traversal Binary Tree를 횡단하면서 Tree의 모든 데이터를 가져오는 방법에는 3가지 방법이 있다. Inorder (Left, Root, Right) Preorder (Root, Left, Right) Postorder (Left, Right, Root) Inorder 우선 왼쪽 자식을 따라서 끝까지 탐색한다. 왼쪽 끝 leaf에 도달하면 해당 leaf를 출력하고, 해당 leaf의 Root인 부모 Node를 출력한다. 그 다음에는 해당 부모 Node의 오른쪽을 탐색하기 시작하며, 끝에 도달하면 똑같이 출력 이후에 Root로 돌아온다. Preorder 자기 자신을 먼저 출력하고 그 다음에 왼쪽 - 오른쪽 순서로 탐색을 하는데, 역시나 자기 자신을 먼저 출력하고 왼쪽과 ..

Graph 기본 개념

Tree와 Graph 사실 Tree는 Graph의 한 형태이다. Tree는 root가 있고, 단방향이며, cycle이 있을 수 없는, 아래로만 흐르는 방향 그래프이다. Graph의 방향 Graph는 방향이 있을 수도 있고, 없을 수도 있다. 있으면 Direted Graph가 되고, 없으면 Undirected Graph가 된다. Graph 안에서의 Circle 하나 이상의 Circle이 있으면 Cyclic Graph라고 하며, 단 한개의 Cycle도 없다면 Acyclic Graph라고 한다. Graph를 표현하는 방법 Adjacency Matrix Adjacency List Adjacency Matrix는 2차원 배열에 표현하는 방법이고, Adjacency List는 배열에 Node들을 나열하고 관계를 L..

Tree의 종류

What is Tree Array, LinkedList, Stack, Queue는 일직선 데이터 구조이다. 반면에 Tree는 부모 - 자식 관계를 갖는 데이터 구조이다. 따라서 Tree에는 계층과 그룹이 있다. 그리고 Tree의 맨 끝, 더이상 자식이 없는 Node를 leaf라고 부른다. Binary Tree (이진 트리) Child Node가 최대 2개까지만 붙는 Tree가 Binary Tree이다. Child Node가 3개씩 붙게 되면 Ternary Tree라고 부른다. 우리가 특히 관심을 갖고 공부하기 되는 Tree는 Binary Tree이다. Binary Search Tree (이진 검색 트리) Binary Tree는 Child Node가 최대 2개라는 조건 외에 다른 조건은 필요 없다. 하지만..

Big-O 표기법

What is Big-O? Algorithm의 성능을 수학적으로 표현해주는 표기법 Algorithm의 시간과 공간 복잡도를 표현할 수 있게 해줌 Algorithm의 실제 러닝 타임을 표기해주기 보다는 데이터나 사용자의 증가에 따른 Algorithm의 성능을 예측하는 것이 목표 O(1) constant time F (int[] n) { return (n[0] == 0) ? true : false; } 입력 데이터의 크기에 상관 없이 언제나 일정한 시간이 걸리는 Algorithm O(n) linear time F (int[] n) { for i = 0 to n.length print i; } 입력 데이터의 크기에 비례해서 처리 시간이 걸리는 Algorithm O(n²) quadratic time F (int..