알고리즘, 자료구조
알고리즘 4-2강. 너비 우선 탐색(Breadth First Search)
알고리즘 4-2강. 너비 우선 탐색(Breadth First Search)
2013.08.07[탐색 알고리즘 강좌] 살펴보면서 전진하자! 너비 우선 탐색(BFS, Breadth First Search) 이번에는 너비 우선 탐색(BFS, Breadth First Search) 알고리즘에 대해 알아보려고 합니다. 우리가 전에 알게된 깊이 우선 탐색(DFS)과는 달리 스택을 이용하지 않고 큐를 이용하며, 너비 우선 탐색도 트리나 그래프에서의 탐색에 사용되는 알고리즘입니다. 이 너비 우선 탐색은 깊이가 1인 모든 정점을 방문하고 나서, 그 다음에는 깊이가 2인 모든 정점을, 깊이가 3인 모든 정점을 방문하는 식으로 계속 방문하다가 더이상 방문할 곳이 없으면 탐색을 마칩니다. 너비 우선 탐색은 깊이 우선 탐색과는 다르게 무작정 막힐때까지 탐색을 진행하는게 아니라, 이곳저곳 살펴보면서 탐색을 진행하는 것이..
알고리즘 4-1강. 깊이 우선 탐색(Depth First Search)
알고리즘 4-1강. 깊이 우선 탐색(Depth First Search)
2013.08.05[탐색 알고리즘 강좌] 해를 찾기위해 전진, 또 전진! 깊이 우선 탐색(DFS, Depth First Search) 이번에는 깊이 우선 탐색(DFS, Depth First Search)이라는 알고리즘에 대해 알아보려고 합니다. 일반적으로 이 DFS 알고리즘을 구현할때는 스택을 이용하고, 트리 혹은 그래프 같은 자료구조에서 데이터를 탐색할 때 사용하는 알고리즘 입니다. 너비 우선 탐색이라고 해서 깊이 우선 탐색과 비슷한게 있는데, 너비 우선 탐색은 다음 강좌에서 소개할 예정입니다. 이 DFS 알고리즘은 더이상 나아갈 길이 보이지 않을 만큼 깊이 들어가는 특징을 지니고 있는데, 만약 나아갈 길이 존재하지 않으면 이전의 위치로 돌아와 다른 길을 선택하여 움직입니다. 이해하기 쉽도록 그래프를 보면서 설명을 하도..
알고리즘 3강. 탐욕 알고리즘(Greedy Algorithm)
알고리즘 3강. 탐욕 알고리즘(Greedy Algorithm)
2013.07.25[탐욕 알고리즘 강좌] 매 순간마다 최선의 선택! 탐욕 알고리즘(Greedy Algorithm) 오늘 알아볼 알고리즘은 '탐욕 알고리즘(Greedy Algorithm)' 입니다. 알고리즘의 이름 그대로, 상당히 욕심이 많은 알고리즘 입니다. 탐욕 알고리즘이 어떤 알고리즘이냐면, 매 순간마다 최선의 선택을 하는 녀석입니다. 즉, 선택할때마다 가장 좋다고 생각되는 것을 선택해나가며 최종적인 해답을 구하는 알고리즘이라고 말할 수 있습니다. 그러나, 이 알고리즘을 설계할 때 유의할 점은 전체를 고려하는게 아니라 문제를 부분적으로 나누어, 나누어진 문제에 대한 최적의 해답을 구하므로 전체적인 최적의 해가 될 수 있는 경우가 존재합니다. 한번 예를 보아볼까요? 탐욕 알고리즘의 대표적인 문제로 거스름돈을 계산하는 문..
자료구조 5강. 힙(Heap)
자료구조 5강. 힙(Heap)
2013.05.31[자료구조 강좌] 특별한 트리를 기본으로 하는 자료구조! 힙(Heap) 오늘은 '힙(Heap)'이란 자료구조에 대해서 알아보려고 합니다. 이 힙(Heap)이란 자료구조는 위키백과에 따르면 '특별한 트리를 기본으로 하는 자료구조이다.'라고 설명되어 있습니다. 여기서 특별한 트리란 우리가 전에 배운 완전 이진 트리를 말하며, 힙 자료구조는 최대 힙(Max Heep)과 최소 힙(Min Heep)으로 나뉘며 이러한 힙은 최대값 또는 최소값을 짧은 시간내에 찾기 위해서 만들어진 자료구조입니다. 최대 힙이란 부모 노드의 값이 항상 자식 노드의 값보다 크다는 것이며, 최소 힙은 부모 노드의 값이 항상 자식 노드의 값보다 작다는 것입니다. 예를 들어, 부모 노드의 값이 항상 자식 노드의 값보다 작은 최소 힙(Min H..
알고리즘 2-3강. 탐색 알고리즘 - 이진 탐색 트리(Binary Search Tree)
알고리즘 2-3강. 탐색 알고리즘 - 이진 탐색 트리(Binary Search Tree)
2013.05.28[탐색 알고리즘 강좌] 데이터를 찾아보자! 이진 탐색 트리(Binary Search Tree) 이번에는 이진 탐색(Binary Search)이 적용된 이진 트리(Binary Tree)에 대해서 알아볼 것입니다. 이진 트리(Binary Tree)에 대해 더 상세한 설명을 보고싶으시면 아래 링크를 방문하여 이진 트리에 대한 설명을 읽어보시기 바랍니다. 이진 트리(Binary Tree): http://blog.eairship.kr/215 우리가 알고 있는 이진 트리는 자식 노드가 최대 두 개의 노드를 지니고, 네 가지 성질을 지닙니다. 자식 노드가 아에 없거나, 왼쪽 자식 노드 혹은 오른쪽 자식 노드 하나만 존재하거나, 왼쪽과 오른쪽 자식 노드를 모두 지니는 경우입니다. 그렇다면, 우리가 배우게 될 이진 탐색..
알고리즘 2-2강. 탐색 알고리즘 - 이진 탐색(Binary Search)
알고리즘 2-2강. 탐색 알고리즘 - 이진 탐색(Binary Search)
2013.05.25[탐색 알고리즘 강좌] 데이터를 찾아보자! 이진 탐색(Binary Search) 이번에는 순차 탐색에 이어 이진 탐색(Binary Search)에 대해 알아보도록 할텐데, 이 '이진 탐색(Binary Search)'이 왜 이진인지 짐작이 가시나요? 이진 탐색이란 이름이 붙여진 이유는 한번 비교를 거칠때 탐색 범위가 반(1/2)으로 줄어들기 때문에 그렇습니다. 이 탐색 알고리즘은 순차 탐색과는 달리 정렬된 배열을 전제로 합니다. 이진 탐색이 얼마나 빠른 알고리즘이냐면, 70억 명 중에서 특정한 정보를 탐색하려 할 때, 순차 탐색은 평균적으로 35억 번을 비교하고, 이진 탐색은 최대 33번의 비교로 데이터를 찾을 수 있습니다. 놀랍죠? 이진 탐색(Binary Search)의 탐색 과정 이제 한번, 위같은 정..
알고리즘 2-1강. 탐색 알고리즘 - 순차 탐색(Sequential Search)
알고리즘 2-1강. 탐색 알고리즘 - 순차 탐색(Sequential Search)
2013.05.23[탐색 알고리즘 강좌] 데이터를 찾아보자! 순차 탐색(Sequential Search) 이 강좌에서 알게될 '순차 탐색(Sequential Search)'는 바로 데이터가 모인 데이터 배열이 있으면 이 데이터 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘입니다. 이 순차 탐색은 데이터를 따로 조작할 필요가 없어 단순하지만 비효율적이라는 단점을 지니고 있습니다. 추가로 순차 탐색은 단방향으로 탐색을 수행하기 때문에 선형 탐색(Linear Search)라고 부르기도 합니다.위에서 말했듯이, 순차 탐색 알고리즘은 단순하여 구현이 정말 간단합니다. 순차 탐색은 정렬되어 있지 않은 데이터 배열에서 평균적으로 (n+1)/2번의 비교를 거치며, 최악의 경우 n번의 비교를 거칩니다. 시간 ..
자료구조 4강. 트리(Tree)
자료구조 4강. 트리(Tree)
2013.01.23[자료구조 강좌] 나무와 유사한 계층적 구조!트리(Tree) 오늘 배우게 될 트리(Tree)란 자료구조는 나무와 유사하게 계층적 구조를 띄고 있는 자료구조입니다. 트리 그대로죠. 나무에 뿌리와 가지, 잎이 있듯 트리라는 자료구조에서도 나무와 뿌리 그리고 가지가 존재합니다. 여기서 뿌리 노드는 루트 노드라 하고, 가지와 잎은 그대로 가지 노드, 잎 노드와 같이 부릅니다. 트리가 응용되는 분야에는 무엇이 있을까요? 트리의 주된 목적은 탐색이며, 의사 결정, 파일 시스템(디렉터리 구조), 검색 엔진, DBMS, 라우터 알고리즘, 계층적 데이터를 다루는 등 매우 다양한 곳에서 응용이 되고 있습니다. 전에 배운 자료구조와 트리가 다른게 있다면, 리스트와 스택, 큐는 모두 선형 구조를 띄고 있다면 이 트리는 계층 ..
자료구조 3강. 큐(Queue)
자료구조 3강. 큐(Queue)
2013.01.15[자료구조 강좌] 선입선출!큐(Queue) 큐(Queue)란 자료구조는 앞서 배웠던 스택(Stack) 자료구조와는 달리 선입선출(First In, First Out: FIFO)의 구조를 지니고 있습니다. 한마디로 먼저 들어온 데이터는 먼저 나간다는 소리입니다. 예를 들면, 점심시간에 학생들이 점심을 먹으러 일렬로 줄을 서있다고 가정합시다. 줄을 선 순서대로 차례차례 급식을 받고 빠져나가죠? 이러한 구조를 지닌 자료구조가 바로 큐(Queue)라고 말할 수 있습니다. 오늘은 순환 큐(Circular Queue)와 링크드 큐(Linked Queue)에 대해 알아보기 전에, 기본적으로 짚고 넘어가야 할 사항들이 있습니다.우리가 리스트(List)에서는 가장 앞에있는 노드를 헤드(Head), 가장 뒤에 있는 노드를..
자료구조 2강. 스택(Stack)
자료구조 2강. 스택(Stack)
2013.01.09[자료구조 강좌] 선입후출! 후입선출!스택(Stack) 오늘 알아보게될 스택(Stack)이란 자료구조는 선입후출(First In, Last Out: FILO), 후입선출(Last In, First Out: LIFO)의 구조를 가지고 있습니다. 예를 들자면, 어느 개발자의 책상에 빼곡히 쌓여있는 책을 정리하기 위해 가장 위에있는 책부터 꺼내들어 차례대로 정리합니다. 여기서, 먼저 쌓인 책들보다 나중에 쌓인 책들이 먼저 밖으로 나간다고 해서 후입선출의 구조라 말하고, 반대로 나중에 쌓인 책들보다 먼저 쌓인 책들이 늦게 밖으로 나간다고 해서 선입후출의 구조라고 말하는 것입니다. 스택(Stack)도 마치 개발자의 책상에 빼곡히 쌓여있는 책들과 비슷합니다. 1. 스택(Stack) 데이터의 삽입과 제거가 한쪽 끝에..
자료구조 1강. 리스트(List)
자료구조 1강. 리스트(List)
2013.01.01[자료구조 강좌] 데이터의 목록을 다루는 자료구조리스트(List) 리스트(List)는 데이터의 목록을 다루는 구조가 단순한 자료구조 입니다. 구조가 단순하면서도, 가장 널리 쓰이며 리스트는 다른 자료구조들을 이해하는데 필요한 기초를 제공합니다. 이 리스트란 자료구조는 데이터를 순차적으로 저장하며, 이 때문에 선형 구조를 띕니다. 여기서 선형 구조란 데이터가 순차적으로 저장되기 때문에 끊어지지 않으며, 한 줄로 계속되기 때문에 마치 선과 같은 형태를 띈다 하여 선형 구조라고 하는 것입니다. 1. 링크드 리스트(Linked List) 노드의 연결로 이루어져 있다! 가장 먼저 링크드 리스트(Linked List)란 녀석에 대해 설명을 하도록 하겠습니다. 이 링크드 리스트(Linked List)는 노드(Node..
비주얼베이직6 움직임에 관한 수학공식 정리
비주얼베이직6 움직임에 관한 수학공식 정리
2012.10.031. 부드러운 움직임( Smooth movement) 폼에 커맨드박스와 타이머를 배치하고, 타이머의 Interval를 1로두시고 코드 편집으로 돌아갑니다. Private Sub Timer1_Timer() Command1.Left = Command1.Left + 0.1 * (4000 - Command1.Left) '개체의 X축 = 개체의 X축 + 속도 * (종착 X축지점 - 개체의 X축) End Sub 코드를 보시면 먼저 괄호 안의 식부터 계산됩니다. 종착 X축지점인 4000에서 0만큼 뺍니다. (Command1.Left의 초기값이 0이라고 가정) 그 후에 4000이란 값이 나와서 10으로 나누어 400이란 값을 가집니다. 그리고 다시 실행되어 4000에서 400을 뺀 3600에다 10을 나누고 그 값에다..