컴퓨터 6

알고리즘 실전 활용을 위한 요약

알고리즘을 실전에 활용하기 위해서, 간단하게 어떤 알고리즘이 어떤 역할을 수행하는지에 대한 요약글을 적어보려한다.나동빈님의 알고리즘 강의를 수강하면서 차곡차곡 적어나가보도록 하겠다. 등장하는 사진의 출처는 역시 나동빈님의 블로그/강의다.영어/한국어/줄임말 모두로 제목을 걸어놓았으니 Ctrl + F로 원하는 알고리즘을 찾으면 된다. 너비 우선 탐색 (Breath First Search, BFS)최단 길이를 보장해야 할 때 많이 사용한다. 현재 노드에서 가장 가까운 노드부터 방문하는 것으로,위와 같은 그래프일때 1부터 탐색을 시작하면 1 - 2 - 3 - 4 - 5 - 6 - 7의 순서로 방문하게 된다. 추후 다른 알고리즘에 활용되는 기본 알고리즘이다. 깊이 우선 탐색 (Depth First Seach, D..

[C++] 이진 탐색 트리 구현하기 (Binary Search Tree)

이진 탐색 트리 (Binary Search Tree)이진 탐색트리는 데이터의 크기에 따라 노드의 위치가 다르다.정의는 아래와 같다. (1) 모든 원소는 서로 다른 유일한 키를 갖는다.(2) 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다.(3) 오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 크다.(4) 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다. 이진 탐색 트리 C++ 구현이제 이진 탐색트리를 구현할텐데,- 탐색(search)- 삽입(insert)두 가지 기능을 수행하도록 할 것이다.구현해볼 이진 탐색트리는 아래와 같이 생겼다. 주황색 표시된 부분은 새로 추가해볼 노드다.1234567891011121314151617181920212223242526272829303132333..

[C++] 이진 트리 구현하고 순회하기 (Binary Tree in C++)

이진트리(Binary Tree)란?모든 노드의 차수를 2 이하루 정하여 전체 트리의 차수가 2 이하가 되도록 만든 것이 이진트리다.이진트리는 왼쪽 자식노드와 오른쪽 자식노드 2개만을 가질 수 있으며, 공백노드도 이진트리의 노드로 취급한다.이진트리의 서브트리 모두 이진트리이다. 이진트리의 종류이진트리는 포화 이진 트리(Full binary tree), 완전 이진트리(Complete binary tree), 편향 이진트리(Skewed binary tree) 3가지가 있다.포화 이진트리는 모든 레벨에 노드가 꽉찬 이진트리를 말하며, 공백 노드가 없다.즉 트리의 높이가 h 일때 2^(h+1) - 1 개의 최대 노드수를 갖는 이진트리이다. 완전 이진트리는 노드 개수가 n 개일 때, 노드의 위치가 포화 이진트리의 ..

Insertion Sort Algorithm (삽입 정렬 알고리즘)

Insertion Sort(삽입정렬)의 방식은 이렇게 이해하면 쉽다. 내가 트럼프카드를 패로 쥐고 있고, 그게 오름차순으로 정렬되있다고 가정하자. 그러고 새 카드를 뽑으면 정렬된 패의 정렬순서에 맞게 새 카드를 어딘가에 삽입해야한다. 그것이 삽입정렬이다. 도식화 한 Insertion Sort리스트 그림을 통해 삽입정렬의 작동원리를 보자! 0~5번째 위치까지 정렬된 리스트 6번째 위치에 5라는 숫자가 들어왔다. 마지막 위치에 있는 5를 key라고 하자. key는 왼쪽으로 움직이면서 어디에 들어갈지 본다. key가 왼쪽으로 움직이면서 앞자리와 숫자 대소비교를 하게된다. 5번째 자리로간 key는 리스트의 5번째 원소인 13과 값을 비교한다. 이때 key > 13 이므로 5번째 원소의 값 13은 뒤로 밀려난다...

Binary Search Algorithm (이진 검색 알고리즘)

Binary Search는 순서대로 정렬된(sorted) 리스트에서 아이템을 찾는데 유용한 알고리즘이다.Binary Search는 아이템이 있는 범위까지 계속해서 반으로 나누면서 찾는다.1부터 10까지 수 중 아무거나 하나를 생각해서 맞추는 게임의 알고리즘과 동일하다. Binary Search의 의사 코드는 다음과 같다. 1. min은 범위 중 가장 낮은 것, max는 범위 중 가장 높은 것이다.min = 1, max = n2. min과 max의 평균값을 구해서 반내림을 한다. 이게 추정치다. (정수가 되도록)3. 만약 숫자를 맞췄다면, stop!4. 만약 추정치가 너무 낮다면 min을 그 추정치보다 높게 변경.5. 만약 추정치가 너무 높다면 max를 그 추..

존 손메즈 <소프트 스킬>

요즘 읽고 있는 책은 존 손메즈의 이다.나는 아직 개발자라 하기에는 너무 모르는게 많지만, 일단은 읽었다.생각외로 개발자가 아닌 사람들에게도 도움이 되는 책이다.삶을 주체적으로 살기 위해서 어떻게 해야하는지 이 아저씨가 알려준다.시중에 나와있는 자기계발서처럼 '창의적으로 살아라, 현명한 선택을 해라' 같은 뜬구름 잡는 소리 안 한다.부적절할 수 있는 예시지만 이력서는 업체에다 맡기라는 식의 구체적이고 상세한, 또는 현실적인 조언을 해준다.아직 다 못읽었지만 회사에서 은퇴전까지 미네랄만 캐는 SCV 중의 한 명이 되기 싫은 사람,성공적인 프리랜서 생활을 꿈꾸는 사람들에게 추천한다.

나/독후감 2016.01.25