세밍 로그

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

멀티 프로세스는 프로세스가 동시에 실행되는 것을 말합니다. 동시에 실행되는 것을 좀 자세히 뜯어보면 CPU 코어가 1개일때의 동시성과 코어가 여러개일 때의 병렬성으로 나눠집니다. 프로세스가 실행될때는 메모리와 CPU를 사용하게 됩니다. 메모리는 여러 프로세스가 함께 담겨있을 수 있는데, CPU는 한 프로세스만 연산할 수 있습니다. 그래서 코어가 여러개일때는 프로세스는 진짜로 동시에 실행될 수 있습니다. 이를 병렬성(parallelism)이라고 합니다. 반면 코어가 1개일때는 진짜로 동시에 실행될 수는 없습니다. 하지만 빠르게 프로세스를 바꿔가며 번갈아 실행하며 동시에 실행되는 것처럼 보일 수 있습니다. 이를 동시성(Concurrency)이라고 합니다. 그리고 프로세스를 바꿔가며, 짧은 시간동안 번갈아가며..

프로세스는 무엇일까요? 흔히들 "프로세스가 실행 중입니다" 라는 안내 문구를 종종 보셨을거에요. 이걸 보고 프로세스가 실행중이면 프로그램이 실행중이구나 라고 생각하실텐요, 프로세스는 실행중인 프로그램 파일을 말합니다. 실행 파일 형태로 된 프로그램이 메모리인 RAM에 적재되어서 CPU에 의해 연산이 되는 것이지요. 메모리는 CPU가 직접 접근할 수 있는 휘발성 내부 저장장치 입니다. CPU가 살아 있을때 접근할 수 있는 저장장치라, CPU가 꺼졌을때, 즉 컴퓨터의 전원이 꺼졌을때, 메모리에 저장된 내용도 함께 날아가지요. 그래서 컴퓨터가 꺼져있을때, 또는 해당 프로그램이 실행중이 아닐때, 하드디스크 등의 보조기억장치에 프로그램 실행파일들이 저장되어 있습니다. 그러다가 CPU가 켜졌을때, CPU가 일하고자..

이진탐색은 쉽게 생각해서 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에서 삭제를 하는 경우가 약간 복잡합니다. 경우의 수가 많기 때문인데요, 아래의 경우들로 나뉘게 됩니다. 삭제할 노드의 자식 노드가 없는 경우 삭제..