본문 바로가기

STUDY

 (40)
01) Kernel Compile 사전지식 커널(Kernel) - 운영체제의 코어에 해당하는 부분으로, 시스템 제어 등을 담당한다. - 컴퓨터를 부팅하면 자동으로 실행되어 메모리 상에 올라가게 된다. 커널 컴파일(Kernel Compile) - 운영체제를 설치하면 커널도 자동으로 설치되게 되는데 커널을 내가 원하는 버전으로 바꿔주고 싶을 때 사용하는 방식이다. 루트(root) 권한 주기 - 우분투 작업할 때 루트 권한을 주고 시작하면 편하다. 루트 권한을 주기위한 명령은 다음과 같다. - $ sudo su 현재 커널 버전 확인 $ uname -r 새로운 커널 소스 다운로드 커널 소스는 http://kernel.org에서 다운받거나, 명령을 통해 다운받을 수 있다. 나는 명령을 통해 다운받는 방식을 선택하였다. 명령어는 아래와 같다. 이 ..
Dijkstra의 개념 및 구현 들어가며 오늘은 엄청 유명한 '다익스트라 알고리즘'에 대해 공부해 볼 예정이다. 그래프와 트리에 관한 알고리즘에 특히 약한 편이라 더더 열심히 해야할 것 같다. 개념 및 특징 한 정점에서 나머지 모든 정점까지의 최단 경로를 찾는 알고리즘 음수인 간선을 포함하는 경우 최단 경로를 찾을 수 없는 경우가 있음 구현 연결되지 않은 정점들 간의 거리는 INF(무한대)로 표현 알고리즘 모든 정점을 미방문 상태로 표시한다. 모든 정점 간의 거리를 INF(무한대)로 표시한다. 이어진 정점 간의 거리를 표시한다. 현재 정점(초기값은 시작점)을 방문 상태로 표시한다. 현재 정점과 이어진 정점들에 대해 (시작점에서 현재 정점까지의 거리) + (현재 정점에서 이어진 정점까지 거리) < (시작점에서 이어진 정점까지 거리)을 만..
02) 스택(Stack)의 개념 및 구현 들어가며 과외를 시작했다. 편입을 준비하는 학생인데 내가 사실 컴퓨터 분야 과외는 처음이고 편입 과외는 더더욱 처음이라, 뭐부터 시작해야할지 잘 모르겠다. 과외를 빌미삼아 자료구조랑 알고리즘을 더 열심히 정리하는 기회로 삼아야겠다. 오늘은 자료구조 중에 가장 기초라할 수 있는 스택(stack)에 대해 포스팅 해보고자 한다. 스택을 공부하면서 나에게 가장 어려웠던 점은, 이 스택이라는 용어를 너무 여기저기 쓴다는 점이었다. 자료구조에도 나오고 프로세스 구조에도 나오고 심지어는 C++ STL에서도 등장한다. 여기서 주목할 점은 스택은 LIFO의 방식으로 데이터를 처리하는 자료구조인데 이러한 자료구조를 따르는 모든 아키텍처에 스택이라는 이름을 붙여놨다는 점이다. 이 점만 기억하면 스택은 정말 쉬운 개념이다. ..
01) 힙(Heap)의 개념 및 구현 들어가며 알고리즘 카테고리의 정렬(sorting)에 대한 포스팅을 하고 있다. 오늘은 힙 정렬(heap sorting)에 대해 포스팅 하려고 했는데 이를 위해서는 힙(heap)에 대해 먼저 공부해야 했다. 따라서 오늘은 힙(heap)에 대해 포스팅 해보고자 한다. 개념 및 특징 완전 이진 트리 우선순위 큐를 위해 만들짐 최댓값이나 최솟값을 빠르게 찾기 위해 만들어짐 반정렬(느슨한 정렬) 상태 부모 노드의 키 값이 자식 노드의 키 값보다 크거나(혹은 작거나) 같은 이진 트리 중복 값을 허용 종류 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 구현 보통 배..
[Sorting 05] Insert Sort의 개념 및 구현 들어가며 날이 엄청 춥다. 드디어 겨울이 오나보다. 오늘은 개념은 쉽지만 비효율적인 알고리즘 중에 하나인 'Insert Sort'에 대해 알아보자. 개념 및 특징 이미 정렬된 리스트를 앞에서 부터 값을 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘이다. in-place 알고리즘이다. 시간 복잡도: O(N2) 선택정렬이나 거품정렬에 비해서는 빠르다.* 알고리즘 앞에서부터 차례대로 이미 정렬된 리스트와 비교하여 자신의 위치를 찾아 삽입한다. 리스트의 모든 원소에 대해 위와 1과 같은 과정을 반복한다. 소스코드(C++) #include #include #include #include using namespace std; typedef vector::iterator IT; void insertSor..
[Sorting 04] Bubble Sort의 개념 및 구현 들어가며 이제 주요 정렬(sort) 알고리즘의 반정도 포스팅을 했다. 어떻게 이렇게 다양한 정렬 알고리즘들을 생각해냈는지 그저 신기할 따름이다. 그간 알고리즘들이 머릿 속에서 정리가 안된 채 널부러져 있는 느낌이었는데 블로그 포스팅을 하면서 점점 정리가 되는 기분이 들어서 좋다. 오늘은 쉬운 정렬 알고리즘 중에 하나인 'Bubble Sort'에 대해 알아보자. 개념 및 특징 비교횟수: O(N2) 자리 교환 횟수 최선의 경우 - 이미 정렬이 된 경우 - 한번도 바꾸지 않아도 된다. - O(1) 최악의 경우 - 꺼꾸로 정렬이 된 경우 - O(N2) 알고리즘 인접한 두 수를 비교하여 큰 수를 뒤로 보낸다. 한번 순회할 때마다 비교하는 수가 하나씩 줄이면서, 정렬이 완료될 때까지 1의 과정을 반복한다. 소스코드..
[Sorting 03] Merge Sort의 개념 및 구현 들어가며 복잡한 정렬 알고리즘 중에서 가장 간단하다는 합병정렬(merge sort)에 대해 포스팅해 볼 것이다. 알고리즘을 막 공부하기 시작했을 때, merge sort를 구현하다가 막혀 며칠을 끙끙댔던 기억이 있다. 이제 그 때보다는 실력이 조금 나아졌으리라 기대하면서 포스팅을 시작해본다. 개념 및 특징 존 폰 노이만이 1945년에 개발했다. 분할정복(divide and conquer) 알고리즘 중 하나이다. 결과를 임시 배열에 저장했다가 다시 복사하는 과정이 발생하므로, 추가적인 메모리 공간도 요구되고 배열 복사에 시간이 소요된다. 최악 시간 복잡도: O(NlogN) 최선 시간 복잡도: O(NlogN) 평균 시간 복잡도: O(NlogN) 알고리즘 리스트의 길이가 1 이하면 이미 정렬된 것으로 본다. ..
[Coursera / ML] 01_Introduction 들어가며 며칠 전, 누군가가 같이 ML 공부를 해볼 것을 제안하였다. ML이 워낙 핫한 주제라 전공자로써 한 번쯤은 공부해야겠다는 생각을 하고 있었는데 이번을 계기로 ML 공부를 시작하게 되었다. 전 세계적으로 가장 유명한 ML 강의인, 코세라(Cource)에 올라온 앤드류 응(Andrew Ng) 선생님의 강의를 통해 공부를 시작해 볼 생각이다. 이제 막 ML에 대해 공부를 시작하는 단계라, 이와 관련된 포스팅은 강의 복습용으로 작성된다고 생각하면 될 것 같다. ML Definition Arthur Samuel(1959). Machine Learning: (영문) Field of study that gives computers the ability to learn without being explicit..

티스토리툴바