SLAM 과목에서 이동체의 경로를 맵핑할 때 스쳐 배웠던 경험이 있다. 다익스트라 알고리즘은 두 정점 사이에 존재하는 최단 경로를 찾는 알고리즘이다. 그래프 구조로 이루어져 있고, 이진 힙을 사용한 우선순위 큐로 작동한다. 실생활에서 굉장히 빈번하게 사용되고 있는 알고리즘이다. 다익스트라 알고리즘 가중 그래프 다익스트라 알고리즘을 구현하기 전에 가중치 그래프를 먼저 소개하려 한다. 그래프의 정점들에 대해 가중치를 부여해 경로의 상대적인 길이를 알 수 있다. 일반적으로 구현했던 그래프의 연결 관계를 담는 키-값 객체에서 가중치가 추가로 매겨지게 된다. 시작점을 지정, 방문하여 다음 이동할 노드를 결정해야 한다. 이 때, 가장 작은 거리 가중치를 가진 노드를 선택한다. 다음 노드로 이동한 후, 그 노드의 인..
지난 시간 페이징 방식에 기반한 가상 메모리 기술인 디멘드 페이징에 대하여 학습하였다. 해당 방법론은 프로세스 크기에 비례하여 페이지 테이블 또한 커지는 문제가 발생하였는데, 이를 해결할 방법을 학습하고자 한다. 다계층 페이지 테이블 페이지 테이블 크기 문제를 해결하는 방법 4Kbyte 페이지에 4바이트 엔트리가 1,024개 담긴다. 코드가 많아지면 그에 따라 페이지 테이블을 담고 있는 엔트리도 증가하게 되고, 하나의 페이지에 담기지 않게 된다. 이 많은 양의 엔트리들을 페이지에 논리적으로 분배하기 위한 방법이 존재한다. 첫 번째는 멀티 레벨 페이지 테이블로, 계층적 특성(Hierarchical)을 가진다. 두 번째 방법으로는 Inverted 페이지 테이블이 있는데 성능 이슈로 요즘은 잘 사용하지 않는다..
그래프 순회와 노드 탐색 그래프 순회를 구현하기 위해서는 일반적인 트리 순회와 달리 루트가 존재하지 않기 때문에, 시작점을 정해주어야 한다. 또한 여러 순서가 존재할 수 있고, 이미 방문했던 노드를 다시 방문하거나 뒤로 돌아가야 하는 경우가 있을 수 있다. 해당 차이점을 제외하고는 트리 순회에서와 마찬가지로 BFS, DFS, 재귀형과 순환형을 통해 구현한다. 웹 크롤링, 최단거리 추천, 미로찾기, GPS 네비게이션 등에서 그래프 순회가 사용된다. 실생활과 굉장히 밀접한 알고리즘이다. 깊이 우선 그래프 순회 (DFS) 이전에 학습했던 트리 구조에서의 깊이 우선 그래프 순회를 간단히 정리하자면, 형제트리를 방문하기 전에 자식 노드를 먼저 방문하는 것을 말한다. 유방향 그래프를 기준 깊이 우선 그래프에서는 ..
1. 챗팟 졸작으로 진행되는 프로젝트로 개발이 한창이다. 최대한 이번 달 내로 마무리지을 예정. 완성되면 블로그와 리드미에 작성할 듯. 반응형 웹앱으로 개발 중인데, 웹 화면에서는 너무 휑해보인다. 앱 같기도 하고. 웹에서 별개의 인트로 페이지를 만들지, 레이아웃을 달리 할지 고민 중에 있다. 2. 알고리즘 알고리즘도 다음 주면 커리큘럼이 마무리된다. 그 후 JS 메서드를 한 번 복습 겸 정리하고, 제대로 코테 풀이에 들어갈 예정이다.
가상 메모리 페이징 이후의 메모리 관리 방법으로, 프로세스의 일부만 물리적 메모리에 저장하고, 나머지는 가상 메모리에 저장하여 필요할 때만 호출하여 사용하는 동적 메모리 관리법을 말한다. 보조기억장치에 가상 메모리 공간을 만들어, 프로세스 원본을 저장하고 직접적인 실행에 필요한 Instruction들만 메인메모리에서 실행시키켜 공간 효율 측면에서 굉장히 뛰어나다. 메모리 분류 실제 메모리 (Real memory) 주기억장치 주소 정보 (=real address, physical address, absolute address) 가상 메모리 (Virtual memory) 보조기억장치 가장 주소 공간 (=logical address, virtual address) 그러나 처리 과정에서 수시로 보조기억장치에 접..
주소 바인딩 주소 바인딩이란, Instruction이나 Data의 Physical Address를 결정하는 것을 말한다. 바인딩이 일어나는 시점에 따라 Compile Binding, Loading Binding, Execute Binding으로 분류할 수 있다. Compile Binding 프로그램 작성 후 소스코드를 바이너리코드로 변환하는 시점에 바인딩하는 것을 말한다. 프로세스 시작 지점($BA, 상대주소)을 100으로 지정해주고 컴파일 스캔 과정에서 계산한 코드의 길이에 따라 다음 변수의 절대 주소를 지정해준다. (I -> $BA + 406) Code Relocation 시 충돌로 인하여 명령어들이 꼬이게 된다. Load Time 실제로 메인 메모리에 데이터를 넣는 로딩 과정에서, 운영체제가 물리적..
그래프 소개 그래프는 유한하고 변할 수 있는 꼭지점이나 노드, 점들의 집합으로 이루어진 자료구조이다. 넓게 보면 트리 구조에 속하지만, 시작점이나 진입점들이 존재하지 않고 오로지 같은 레벨의 노드만 존재한다. 꼭지점 집합에 순서 규칙이 존재하는 경우 유방향 그래프, 존재하지 않는 경우 (양방 통행이 가능한 경우) 무방향 그래프로 분류한다. 또한 연결 관계에 가중치를 부여할 수도 있다. 그래프는 노드와 연결관계로 얽혀있는 메쉬 형태 구조라고 해도 될 듯 하다. 또한 기존에 칭하던 노드를 "Vertex (정점)"으로, 노드 간의 연결관계를 "Edge (간선)"이라고 부른다. 용례 SNS 관계망 지도 기능 : 방향 안내, 위치, 길 찾기 등 웹 라우팅 : 인터넷 생태계나, 특정 웹사이트의 연결 관계 추천 알고..
해쉬 테이블은 키-값 쌍을 저장하는데 사용하는 알고리즘으로, 값을 찾거나 (탐색), 추가하거나 (삽입), 제거하는 처리 속도가 굉장히 빠르다는 특징이 있다. 순서가 있고 연속적인 데이터라면 배열을, 그 밖의 경우 해쉬 테이블(딕셔너리, 객체 등)을 사용하면 된다. 굉장히 빈번히 사용되는 알고리즘으로 많은 프로그래밍 언어들에 해당 기능이 자체적으로 내장되어 있지만, 본 섹션에서는 해쉬 테이블의 알고리즘 구조를 이해하고 직접 구현해보고자 한다. 해쉬 함수 입력받은 키에 따라 무작위 인덱스를 부여하고, 배열에 넣어 데이터를 관리해주는 단방향 함수를 말한다. 이를 통해 String 형태로 이루어진 키를 이용해 원하는 값을 찾을 수 있게 된다. 좋은 함수를 만드는 기준 탐색, 삽입, 제거 등의 데이터 처리 속도가..
이진 힙 (Binary Heap) 기본적으로 힙은 트리 구조의 한 종류이다. 이진 힙 외에도 굉장히 많은 힙 알고리즘이 존재한다. 이진 힙은 최대 힙, 최소 힙으로 구분할 수 있다. 힙 구조는 그래프 순회를 위한 우선순위 큐 (Priority Queue) 구현에 주로 사용된다. 최대 이진 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가진다. 루트부터 노드를 타고 내려갈수록 더 작은 값을 갖는다는 뜻이다. 최소 이진 힙에서는 그 반대로, 부모 노드가 언제나 좌우의 자식 노드보다 작은 값을 갖는다. 오름차순, 내림차순으로 생각해도 될 듯 그럼 이진 탐색 트리(BST)와 비슷한 것 아닌가? 할 수 있곘지만, 이진 탐색 트리와 다르게 좌우 자식 노드의 크기 순서를 고려하지 않는다. 힙 정렬 트리 구조를 갖..
트리 순회 모든 노드를 한 번씩 도는 방법. 앞서 학습한 이진 탐색 트리 뿐 아니라, 모든 트리 구조에서 사용가능한 순회 알고리즘이다. 다른 섹션들보다 재귀를 더 많이 사용할 예정. 너비 우선 탐색 (BFS) 요소들을 거쳐가는 일반적인 순서를 기준으로 탐색 방식을 구분하였다. CSS Flexbox의 direction을 row로 주거나, column으로 주는 것도 이와 유사하다고 볼 수 있을 듯 하다. 너비 우선 탐색법(BFS)은 최상단 노드(Root)부터 가로 횡을 기준으로 수평으로 한 줄씩 내려가며 순회하는 방식이다. 구현 선입선출 구조를 갖는 큐 방식을 통해 BFS를 구현한다. 배열이나 리스트에서 Push / Shift 메서드를 사용하면 된다. 큐는 한 줄에 존재하는 노드를 담아놓는 버퍼 역할을 하며..
