![]()
힙(heap) 은 최댓값 또는 최솟값을 빠르게 찾아낼 수 있는 트리형 자료구조입니다.힙은 완전이진트리 형식을 따르며 모든 부모 노드의 값이 자식 노드들의 값과 일정한 대소 관계를 가지게 되는 규칙을 가지고 있습니다.또한 자식노드 사이의 상관관계는 없으므로 유의하여야 합니다.부모 노드의 값이 자식 노드의 값보다 크다면 최대 힙(Max Heap), 부모 노드의 값이 자식 노드의 값보다 작다면 최소 힙(Min Heap) 으로 부릅니다.힙의 규칙에 따라 트리의 가장 상단에는 최댓값 또는 최솟값이 있는 것이 자명하기 때문에, O(1) 만에 최댓값과 최솟값을 찾을 수 있습니다.힙의 삽입은 트리의 가장 마지막 부분에 데이터를 삽입한 후, 부모 노드와 삽입 부분 노드의 대소 관계를 확인하여 힙의 규칙에 맞도록 부모 노..
![]()
트리는 자식과 부모의 관계로 이루어진 계층적인 구조입니다. 필요에 따라 다양한 종류로 나뉘게 되는데 이번에는 제일 간단한 트리인 이진 트리에 대해서 설명하려고 합니다. 먼저 이진 트리에서 사용하는 용어들을 정리해보면 다음과 같습니다. Root : 트리에서 가장 최상위에 존재하는 노드Child : 어떠한 노드의 자식 노드Parent : 어떠한 노드의 부모 노드Siblings : 같은 부모를 갖는 형제 노드Leaf / Terminal : 자식 노드를 갖지 않는 노드Branch / Internal : 자식 노드를 적어도 1개 이상 갖는 노드Degree : 노드가 가지고 있는 자식 노드의 개수Height : 해당 노드부터 Leaf 노드까지의 가장 긴 거리Level : 트리 각 층의 단계 (Root 노드의 경우 ..
![]()
스택은 선형 구조이며, 마지막으로 삽입된 값이 가장 먼저 나오는 LIFO(Last in First Out)으로 되어 있습니다. 이 때 삽입하는 과정을 push라고 하며 값을 빼내는 과정을 pop이라고 합니다. 예를 들면 a, b, c 순서로 push하고 스택에 있는 값들을 모두 pop하면 c, b, a 순서로 나오게 되는 것입니다. 또한 스택에는 size, top, empty라는 함수가 있으며 size는 스택에 들어있는 값들의 수를 반환하는 함수이고, top은 마지막으로 삽입된 값을 반환하는 함수, empty는 스택이 비어 있는지 여부를 반환하는 함수입니다.아래의 두 그림은 stack의 push, pop 과정을 보여주는 그림입니다. 그리고 이러한 스택을 만드는 방법에는 2가지 방법이 있습니다. 하나는 ..
![]()
큐는 선형 구조이며, 삽입된 순서대로 값이 나오는 FIFO(First in First Out)로 되어 있습니다. 이때 삽입하는 과정을 enqueue라고 하며 값을 빼내는 과정을 dequeue라고 합니다.예를 들면 a, b, c 순서로 enqueue하고 큐에 있는 값들을 모두 dequeue하면 a, b, c 순서로 나오게 됩니다.또한 큐에는 size, front, empty라는 함수가 있으며 size는 큐에 들어있는 값들의 수를 반환하는 함수이고, front은 큐에서 가장 먼저 삽입된 값을 반환하는 함수, empty는 큐가 비어 있는지 여부를 반환하는 함수입니다. 그리고 이러한 큐를 만드는 방법에는 2가지 방법이 있습니다. 하나는 배열을 이용한 방법이고, 다른 하나는 링크드 리스트를 이용한 방법입니다. ..
![]()
연결리스트는 랜덤 접근이 가능한 배열과는 다른 순차적인(sequential) 자료구조입니다.연결리스트는 노드들로 구성되어 있습니다. 노드는 저장할 값과 다음 노드를 가리키는 포인터로 이루어져 있습니다. 연결리스트의 첫 노드인 헤드(Head)로 부터 노드에 다음 노드를 가리키는 포인터를 사용해 리스트를 순회할 수 있게 됩니다.위와 같은 연결리스트를 Singly Linked List라고 합니다.Singly Linked List의 각 노드에 이전 노드를 가리키는 포인터를 추가하게 되면 양방향으로 순회가 가능한 Doubly Linked List가 되고, 환형 큐(Circular Queue)와 같이 연결리스트의 마지막 노드인 테일(Tail)과 헤드를 이으면 Circular Linked List가 됩니다. 각 노드..
![]()
그래프란 어떤 상태 혹은 객체 간의 관계를 나타내는 자료구조입니다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성됩니다.정점이란 어떠한 상태 혹은 객체를 나타냅니다. 간선은 그러한 정점 간의 관계, 그중에서도 연결성을 표현하는 요소입니다. 아래 그림은 그래프의 개념이 퍼지기 시작한 '쾨니히스베르크의 다리 건너기 문제'의 쾨니히스베르크의 다리를 도식화한 두 그림입니다.A, B, C, D로 나눠진 4개의 구역과 각 구역을 잇는 a, b, c, d, e, f, g 7개의 다리가 있습니다. 왼쪽이 일반적으로 사용되는 그림이며, 이를 그래프 형태로 나타낸 것이 오른쪽의 그림입니다.여기서 원으로 표현된 A, B, C, D가 정점이며 이 정점들을 연결하는 실선 a, b, c, d, e, f, g가 두 지역을..
![]()
깊이 우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 않은 정점으로 이동하는 것입니다.이 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없으면 마지막으로 통과한 간선을 통해 뒤로 돌아가서 해당 정점에서 방문할 수 있는 정점을 탐색합니다. 이러한 과정을 반복하여 그래프의 모든 정점을 방문하는 알고리즘이 DFS 알고리즘입니다. 이해를 돕기 위해 움직이는 그림으로 그래프를 설명하도록 하겠습니다. 위의 그림과 같은 유향 그래프가 존재하고 한 정점에서 여러 개의 정점으로 이동이 가능할 때 정점의 번호가 더 작은 쪽을 먼저 방문한다고 가정을 하겠습니다. 이 때, 정점 1에서 깊..
이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 시간복잡도 O(log N) 만에 찾아내는 탐색하는 방법입니다.오름차순으로 정렬된 사이즈가 N인 배열 D에서 원하는 값 k(k = 11)를 찾는 방법은 다음과 같습니다.먼저 탐색할 데이터의 범위를 두 개의 인덱스(왼쪽, 오른쪽)로 지정하고 이를 L, R이라고 하겠습니다. 정렬되어있기 때문에 D[L]은 최솟값, D[R]은 최대값이 됩니다.L M R01234567-3014791116당연히 처음 탐색 시에는 전체영역이므로 L = 0, R = N - 1 입니다. 이중 중앙값(Median)을 찾아 찾으려는 값 k와 비교합니다. 중앙값 M은 (L+R)/2 로 구할 수 있습니다.중앙값인 D[M]과 K를 비교하였을 시, K가 더 크므로 [0, M]..
![]()
에라토스테네스의 체는 특정 범위의 수들이 소수(Prime)인지 아닌지를 판별하는 알고리즘입니다. 예를 들어 1부터 50까지 수 중에서 소수를 구하고자 한다면 다음과 같은 배열이 필요합니다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950먼저 가장 작은 소수인 2부터 시작합니다. 그리고 2의 배수에 해당하는 수들은 모두 소수가 아닙니다. 따라서 범위 안의 2의 배수들을 소수가 아니라고 체크해줍니다.(일반적으로 boolean타입이나 int형 변수를 만들어주어 체크) 아래에서 색이 칠해진 수는 소수가 아님을 나타냅니다.12345678910111213141516171819202122232425262..
![]()
거품정렬(Bubble Sort)은 인접한 원소들의 대소관계를 비교하여 일정한 대소관계를 만족하지 않을 시, 인접한 원소를 교환하는 방법으로 진행되는 정렬입니다. 다음은 버블 정렬을 쉽게 시각화 한 내용입니다.더보기버블 정렬을 쉽게 도식화 한 그림과 설명을 보면 한번 위치 교환을 통해 가장 큰 원소가 마지막으로 가는 것을 확인할 수 있습니다. 이를 통해 마지막 원소가 정렬되었다고 볼 수 있고, 이를 N-1번 반복한다면 버블 정렬이 끝납니다.N개의 원소가 있다면, N-1번의 교환을 통해 정렬할 수 있습니다. 이를 시간 복잡도로 나타내면 (정렬해야 할 원소의 개수 - 1) *(최대 교환 수) 이므로 O(N²)이 됩니다.힙 정렬, 퀵 정렬과 같은 정렬보다 비효율적이므로 자주 쓰지 않습니다.다음은 C++로 나타낸..
삽입정렬은 배열을 정렬된 부분, 정렬되지 않은 부분으로 나눈 후, 원소를 순차적으로 탐색하면서 해당 원소를 정렬이 된 부분에 끼워 넣는 정렬입니다.맨 처음 원소(1)를 정렬되었다고 가정한 후, 정렬되지 않은 다음 원소(2)를 정해 최근에 정한 원소(1)와 비교한 후 크다면 (1)의 오른쪽에 그렇지 않다면 그 자리에 그대로 정렬합니다.시간복잡도는 각 원소에 대해 적당한 위치를 찾아주어야 하므로 총 원소의 개수 O( N ), 순차적으로 삽입 위치를 찾는데 O( N )이 들므로 O(N²)으로 힙정렬이나 합병정렬에 비해 비효율적(O(N log N))으로 잘 쓰이지 않습니다.다음은 C++로 나타낸 코드입니다.더보기#include #define MAX 5005using namespace std;int d[MAX],..
![]()
선택 정렬은 매 차례마다 정렬되지 않은 원소들을 모두 확인하여 각 인덱스에 맞는 원소를 선택하여 해당 인덱스의 원소와 교환해주는 정렬입니다. 매 차례마다 남은 원소들을 모두 확인하기 때문에 시간 복잡도는 최악의 연산 횟수나 평균 연산 횟수나 O(N^2)입니다.그림을 통해 각 순서에 대해 설명하도록 하겠습니다. 먼저 가장 작은 값을 첫 번째 값인 15로 지정하고, minimum index를 0으로 놓습니다.그 수의 뒤에 있는 모든 수와 비교하면서, minimum index에 있는 수보다 작은 수일 경우 minimum index를 해당 수의 인덱스로 바꿔줍니다.연산이 끝나면 마지막 수인 1이 minimum index가 되고 해당 수와 처음 인덱스를 바꿔줍니다.첫 번째 수는 제대로 정렬된 수이..
변수 (Variable) : 변하는 수자료를 처리하기 위해 이름이 부여된 기억 공간변수의 선언 형식자료형 변수 이름, [변수 이름, ...];ex) int a = 10;변수의 종류..
자바의 작동 원리 소스 코드 작성 기계어 코드 생성 프로그램 실행 사람이 읽을 수 있는 문자열 기계가 읽을 수 있는 문자열로 변경 (컴파일) 하드웨어가 기계어를 해석해 실행 식별자(Identifier) 작성 규칙 유니코드 문자를 사용합니다. 공백이 없는 한 개의 단어로 구성되어야 합니다. 문자, 숫자, '_', '$'를 사용할 수 있습니다. 반드시 문자, '_', '$'로 시작해야 합니다. 길이 제한이 없습니다. 영어 대 · 소문자를 사용합니다. 자바 키워드를 사용할 수 없습니다. 올바른 식별자 잘못된 식별자 식별자 올바른 이유 식별자 잘못된 이유 User_name 대문자 시작 User name 자바 식별자 내에 공백 사용 user_name 소문자 시작 사용자 이름 " _User_name '_'로 시작 ..
![]()
2년 전에 사서 다 읽고도 이해하지 못한 채 그대로 책장에 가둬버리고 다시금 코딩에 손을 대려고 하니 엉망진창으로 쓰이는 내 코드가 너무 마음에 들지 않아 오늘부터 책의 내용을 분석 및 정리하려고 한다.코드 리뷰가 아닌 책 리뷰가 끝났을 때 내가 조금이라도 Clean Code에 와닿길 바란다.책은 총 17개의 챕터와 3개의 부록으로 되어있으며 가능한 한 1개의 챕터를 모두 이해했다는 확신이 들 때 다음 글을 작성하려 한다. 옮긴이의 서문에서 책을 읽을 때 어떻게 읽어야 할 지에 대해 조언이 나와있다.코드를 짜다 보면, 코드를 쓰는 시간보다 코드를 읽는 시간이 훨씬 더 많다는 사실을 알고 있다면, 이 책에서 제시하는 보이스카우트 규칙을 다른 모든 규칙에 앞서 특히 신경을 써서 봐야한다. 보이스카우트 단원..
