세밍 로그

그래프는 실제 세계의 현상이나 사물을 정점(Vertex 또는 Node)와 간선(Edge 또는 Link, branch)으로 표현하는 것입니다. 그래프의 구성요소는 다음과 같아요 - 정점 : vertex : 위치, 정점, 노드 - 간선 : 노드들간의 관계를 나타내는 선 - 인접 정점 : Adjacent Vertex : 간선으로 이어진 정점 - 정점 차수 : Degree : 무방향 그래프에서 하나의 정점으로 인접한 정점의 수 - 진입 차수 : In-Degree : 외부 정점에서 들어오는 간선 수 - 진출 차수 : Out - Degree :외부 정점으로 나가는 간선의 수 - 경로 길이 : Path Length : 경로를 구성하기 위해 사용된 간선의 수 - 단순 경로 : Simple Path : 처음 정점과 마지..

이진탐색은 쉽게 생각해서 up-down 게임이랑 똑같습니다. 저희가 친구들 나이 맞추기 할때, up-down 많이 하잖아요? 어떤 수를 부르고 상대가 up하면 더 큰 수를 부르고, 거기서 down이라고 얘기하면 처음 불렀던 수와 두번째로 불렀던 수 사이를 얘기하는 것처럼요 이진탐색도 그렇습니다. 어떤 정렬된 숫자열이 있을때, 숫자열의 가운데에 위치한 요소와 탐색 타겟을 비교해서 더 크면 숫자열을 반으로 나눈 뒤, 가운데 수보다 큰 영역을 잡아서 또 그 가운데 수를 비교합니다. 만약 작다면 작은 영역을 잡아서요. 이렇게 계속 반복해 가는 것입니다. 반복한다는 점에서 재귀 용법을 사용하지요 코드는 다음과 같습니다. def binary_search(data_array, target): if len(data_a..

오늘은 정렬 파트 마지막! 퀵소트와 병합 소트를 해보려고 합니다. 퀵 소트 퀵소트는 말그대로 빠른 정렬입니다. 퀵소트는 한 요소를 기준으로(보통 0번째 요소) 해당 요소보다 작은 것은 작은 리스트(왼쪽 리스트)에 더 큰 것은 큰 리스트(오른쪽 리스트)에 넣어요 나눠진 리스트를 또 가지고 와서 똑같이 한 요소를 기준으로 잡고 작은것은 왼쪽에, 더 큰 것은 오른쪽에 배치해서, 리스트의 길이가 1개 남을때까지 반복하다가 다시 그것들을 합치는 것입니다. 커다란 것을 작게작게 쪼개가다가 전체 답을 호로록 구한다는 점에서 분할정복에 해당하고, 계속 같은 함수를 함수 내에서 호출한다는 점에서 재귀용법이 사용되어요(분할정복이 원래 재귀용법을 사용하긴 하지만요ㅎㅎ) def qsort(data): if len(data) ..

동적계획법과 분할정복은 서로 비슷한 듯 다릅니다. 이번 시간에 동적계획법과 분할정복에 대해서 자세히 알아봅시다 동적계획법은 Dynamic Programming으로 흔히 DP라고 부릅니다. 동적계획법은 큰 문제를 해결하기 전, 작은 문제부터 해결해서 해당 해를 이용해 큰 문제를 풀어나가는 상향식 접근 방법입니다. 작은 문제의 결과값으로 큰 문제를 해결해나가는 것입니다. 동적계획법은 Memozation 기법을 활용합니다. Memozation 기법이란 컴퓨터가 이전에 계산한 값을 저장해 두어 다시 계산할 필오 없게 해서 전체의 실행 속도를 높이는 것을 말합니다. 이처럼 작은 문제의 결과값을 저장해서 큰 문제를 해결할 때 재활용해서 사용합니다. 이런 특성을 가지고 있기 때문에 피보나치 수열 등에 활용할 수 있습..

재귀호출은 함수 안에서 같은 함수를 또 호출하는 것입니다. 재귀는 문제가 어떤 일정한 규칙이 있는지 살펴보면 됩니다. 팩토리얼을 봐볼게요 1! = 1 2! = 2 * 1 = 2 * 1! 3! = 3 * 2 * 1 = 3 * 2! 4! = 4 * 3 * 2 * 1 = 4 * 3! 이렇게 n! = n * (n-1)! 형태 입니다. 이것을 재귀 함수로 표현해보면 def factorial(n): if n > 1 : return n * factoria(n-1) else : return n 점화식도 마찬가지 입니다 대표적인 피보나치를 살펴볼게요 0 1 1 2 3 5 8 13 .... 1 = 0 +1 2 = 1+1 3 = 3 +2 f(n) = f(n-1) + f(n-2) 임을 알 수 있습니다. 이를 재귀 함수로 표현..

Heap은 최소값이나 최댓값을 알게 쉽게 하는 완전이진트리 입니다. 완전 이진트리란 왼쪽부터 차례대로 넣어지는 이진트리입니다. (그렇기 때문에 BST처럼 노드 균형에 대해서 신경쓸 필요가 없습니다) Heap은 앞서 얘기한 것처럼 최소값과 최댓값을 더 쉽게 알기 위해 고안되었습니다. 그래서 만약 최대값을 알고 싶은 최대 힙(max heap)이라면 head 위치(맨 처음위치)에 최대값이 위치하게 됩니다. 이런 구조를 만들기 위해서, 새로운 값이 힙에 들어오게 되었을때 완전이진트리 구조에 의해 맨 마지막 위치에 새로운 값이 위치하게 되는데, 부모 노드와 비교해서 자식 노드가 더 크다면 계속 자리를 바꾸게 됩니다.(swap) 이런 구조에 의해 부모와 자식노드를 비교했을 때 크기 gap이 규칙으로 있지, BST처..

앞선 BST 게시글에서 자가 균형 BST가 있다고 얘기 드렸습니다. 자가 균형 BST 중에 AVL과 레드-블랙 트리가 있습니다. 이 게시글에서는 AVL 트리를 알아볼게요 AVL 트리 AVL 트리는 트리가 편향되었는지 아닌지를 확인하기 위해서 BF(Balance Factor)을 사용합니다. BF는 왼쪽 서브트리 높이 - 오른쪽 서브트리의 높이 인데, AVL이 균형있다고 판단되려면 모든 노드의 BF가 -1,0,1 중 하나여야 합니다. 만약 위 3수가 아니라면 회전을 통해 균형을 맞춥니다. 회전에는 2가지 종류가 있습니다. 우회전은 BF가 -1,0,1이 아닌 회전해야 할 노드(T)의 왼쪽 자식 노드(L)의 오른쪽 서브트리를 T의 왼쪽 자식 위치에 붙이고, T의 부모 노드로 L을 지정하는 것입니다. 좌회전은 T..

일단 트리는 노드를 이용해서 사이클 없이 데이터를 적재하는 구조입니다. 이때 자식수가 2개인 트리를 이진 트리(Binary Tree) 자식수가 2개이면서 특별한 규칙에 의해 바로 정렬까지 되는 트리를 Binary Search Tree(BST) 라고 합니다. 특별한 규칙이란, 현재 노드를 기준으로 현재 노드보다 작은 값은 왼쪽에, 더 큰 값은 오른쪽에 배치되는 것입니다. 그래서 왼쪽 서브트리는 기준 노드보다 다 작고, 오른쪽 서브트리는 기준 노드 보다 더 큽니다. BST를 구현할때는 링크드 리스트와 비슷하게 노드로 구현을 합니다. 다른 것은 다 괜찮은데, BST에서 삭제를 하는 경우가 약간 복잡합니다. 경우의 수가 많기 때문인데요, 아래의 경우들로 나뉘게 됩니다. 삭제할 노드의 자식 노드가 없는 경우 삭제..

지난 게시글에 이어서 해쉬테이블에 대해서 알아보도록 할게요 지난 게시글에서 해쉬가 검색, 삽입, 삭제에서 O(1)을 보여주며 굉장히 빠르게 작동하지만 해쉬함수에 따라 해쉬값이 겹치는 Collision(충돌)이 일어날 수 있다고 말씀드렸어요. 애초에 해쉬 값이 겹치지 않을 수 있는 해쉬 함수를 만들거나, 해쉬 테이블이 크면 너무 좋겠지만, 현실에서는 그럴수 없는 경우도 있으니까요 해쉬테이블의 Collision이 발생해도 처리할 수 있는 방법의 흐름에는 크게 2가지가 있습니다. Open Hashing과 Close Hashing이 있어요 Open Hashing은 Collision이 일어났을 때, 외부 저장공간(메모리)를 활용하는 방법입니다. 특히 LinkedList나 BST를 이용하지요. 그래서 Seperat..

Hash Table? 해쉬테이블은 (키-밸류)쌍으로 저장하는 구조이다. 조금 더 정확하게 얘기하자면 (키-밸류)에서 해슁함수를 통한 키값인 해쉬값 위치에 해쉬테이블 주소를 두고 키와 밸류를 저장하는 것을 말한다. (키-밸류)쌍으로 저장하기 때문에 삽입, 삭제, 검색이 모두 O(1)로 정말 빠르다. 하지만 그만큼 공간을 많이 차지하게 되어서 공간과 시간을 맞바꾼 자료구조로 볼 수 있다. 파이썬에는 딕셔너리 구조가 해당된다. 그래서 파이썬에서는 특별하게 해쉬 테이블을 구현할 필요는 없다. 그래도 조금 더 해쉬테이블을 톱아보자 Direct Address Table 해슁 함수를 통한 해쉬 테이블이 있기 전에는 Direct Address Table(직접 주소화 테이블)이 있었다. 직접 주소화 테이블은 키와 밸류가..