IT's 2 EG

다익스트라 알고리즘 이란? 다익스트라 알고리즘은 그리디한 방식을 통해 한 점에서 다른 모든점까지의 최단 경로를 구하는 알고리즘입니다. 다만 경로의 길이가 음수인 경우는 최단 경로를 구할 수 없습니다. 경로의 길이가 음수인 경우 최단거리를 구하는 알고리즘은 벨만 포드(Bellman-Ford) 알고리즘이 있습니다. 처음 고안된 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가졌습니다. 이후 우선순위 큐를 이용한 개선된 알고리즘을 통해 O(ElogV)의 시간복잡도를 가지게 되었습니다. 다익스트라 알고리즘 계산 과정 다음은 예제 그래프를 통해 다익스트라 알고리즘이 시작점에서 다른 모든점까지의 최단경로를 구하는 방식입니다. 빨간색 노드는 현재 위치의 노드를 의미하며, 파란색 노드는 우선순위 큐에 존재하는 노드,..

1. 이진탐색(Binary Search) 1.1. 이진탐색 이란? 'Up and Down'이라는 게임이 있습니다. 사회자는 일정 범위의 수 'x'를 생각한다. 참가자가 어떤숫자 'a'를 말했을때, 'a'가 'x' 보다 작으면 사회자는 'Up'이라고 말하며 'a'가 'x'보다 크면 'Down'이라고 말을 합니다. 그렇다면 가장 빠르게 'x'를 찾는 방법은 무엇일까요? 이에 대한 해답은 해당 범위의 중간값을 말하면서 'x'의 범위를 좁혀나가는 방법입니다. 이러한 방법으로 탐색을 해 나가는 것을 이진탐색이라고 합니다. 이진 탐색을 위해서는 우선 정렬이 되어있어야 한다는 조건이 있지만, 매우 큰 범위내에서 빠르게 찾고싶은 데이터를 찾을 수 있는 장점이 있습니다. 결과적으로 이진탐색은 O(logN) 라는 시간복잡..

너비 우선 탐색(BFS) 이란? 너비 우선 탐색 (BFS, Breadth First Search)은 DFS와 함께 대표적인 그래프 탐색 방법 중 하나입니다. BFS 알고리즘은 현재의 위치에서 방문할 수 있는 모든 정점을 방문한 뒤 다음 단계로 넘어가는 방식입니다. 일반적으로 BFS 알고리즘을 구현할 때 큐를 이용합니다. 너비 우선 탐색(BFS) 방법 아래는 BFS를 설명하기 위해 작성한 간단한 그래프입니다. 원안의 1,2,3.. 등을 정점(Vertex)라 하고, 정점과 정점을 잇는 선을 간선(Edge)이라고 합니다. 우선 시작점을 1로 정하고 BFS 알고리즘을 바탕으로 탐색을 해보겠습니다. 시작점인 1번 정점을 큐에 넣고 해당 위치에 방문을 했다고 표시합니다. 1번 정점과 연결된 2번, 3번 정점을 큐에..

깊이 우선 탐색(DFS) 이란? 깊이 우선 탐색 (DFS, Depth First Search)은 BFS와 함께 대표적인 그래프 탐색 방법 중 하나입니다. 일반적으로 DFS 알고리즘을 구현할 때 스택을 이용하고, 유사하게 재귀함수를 이용하여 구현하기도 합니다. DFS 알고리즘은 스택을 이용해서 갈 수 있는만큼 최대한 이동을 하며, 만약 갈 수 없다면 이전 정점으로 돌아갑니다. 깊이 우선 탐색(DFS) 방법 아래는 DFS를 설명하기 위해 작성한 간단한 그래프입니다. 여기서 원으로 둘라싸인 1, 2, 3 .. 등은 정점(Vertex)라 하고, 정점과 정점을 잇는 선을 간선(Edge)이라고 합니다. 우선 시작점을 1로 정하고 DFS 알고리즘을 바탕으로 탐색을 진행해 보겠습니다. 출발점인 1을 스택에 입력하고, ..

메모리 레이아웃 프로그램을 실행하면, 커널은 그 Image 를 메모리에 올리고(load), 실행을 시작하는데 그 실행환경(context)와 메모리에 올라온 이미지를 프로세스라고 하며, 리눅스에서는 이를 task 라고 부른다. OS에서는 일종의 Segmentation 기법인 VMA(Virtual Memory Area)를 구현하여 한 프로세스가 Address space 를 사용할 수 있도록 한다. 이러한 Area 들은 Stack, bss, Data, Text 가 존재하며 다음과 같은 개념으로 존재한다. Text 는 Code Section 이라고 부르며, Start_routine 과 실제 프로그램 코드(실행되는 이미지)가 적재된다. 이 Section 은 읽기만 가능하며, 로더에 의해서 메모리에 로드된다. Da..

레지스터란? CPU 레지스터란 데이터를 고속으로 처리하기 위해 CPU 내부에 존재하는 다목적 저장 공간을 말한다. 디버깅을 하기 위해서는 어셈블리 명령어를 잘 알아야 하고, 이러한 어셈블리 코드를 잘 이해하기 위해서는 레지스터에 대한 이해가 필수이다. 범용 레지스터 (General Purpose Register) 32비트(4바이트)의 크기를 가지는 범용 레지스터는 주로 상수나 주소를 저장할 때 사용되며 특정 어셈블리 명령에서는 레지스터 조작을 위해 사용된다. EAX (Accumulator for operands and results data)EBX (Pointer to data in the segment)ECX (Counter for string and loop operations)EDX (I/O poi..