이번달 코딩테스트 중에서 이거 딱 다익스트라인데 하면서 못 푼 문제가 있었다. 끝나고 후기를 찾아보니 정말 다익스트라로 풀 수 있는 문제여서 아쉬웠던 기억이 있다. 이참에 다익스트라 알고리즘을 복습해보자. 최단 경로 알고리즘 말 그대로 가장 짧은 경로를 찾는 알고리즘. 그래프를 이용해 표현하며 각 지점은 노드로, 지점간의 연결은 간선으로 표현한다. 다익스트라 알고리즘 다익스트라 알고리즘은 그래프의 여러개의 노드가 있을 때 특정한 노드에서 출발해 다른 노드로 가는 각각의 최단경로를 구하는 알고리즘이다. 과정은 다음과 같다. 출발 노드 설정 > 최단 거리 테이블 초기화 > 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택 > 해당 노드에서 부터 다른 노드로 가는 거리를 계산한 후 테이블 갱신 > 반..

* 강의를 듣고 복습하며 정리한 내용입니다. 운영체제 컴퓨터 하드웨어 바로 위에 설치. 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어. 운영체제의 목적 1. 하드웨어 자원(CPU, 메모리)을 효율적으로 관리 2. 응용프로그램 및 사용자에게 편리한 인터페이스 제공 운영체제의 기능 CPU 스케줄링 : CPU 큐에서 기다리는 프로그램 중 어떤 프로그램에게 먼저 CPU 사용권을 줄까? 1. FCFS (First Come First Served) 먼저 온 프로그램 순서대로. 📌단점: CPU를 길게 쓰는 프로그램이 먼저 도착한다면 전체 프로그램의 대기 시간이 늘어난다. 2. SJF (Shortest Job First) CPU를 짧게 쓰는 프로그램 먼저 사용. 📌단점: Starvation(기아 현상..

간단하지만 많이 쓰이는 데이터 구조 세 가지를 살펴보자. 학습 목표 스택, 큐, 딕셔너리의 원리와 구조를 설명할 수 있다. 큐 큐(Queue)는 값이 아래로 쌓이는 구조다. 값을 넣고 뺄 때 선입 선출(FIFO, First in first out) 방식을 따른다. 배열이나 연결 리스트를 통해 구현할 수 있다. 스택 스택(Stack)은 값이 위로 쌓이는 구조다. 값을 넣고 뺄 때 후입 선출(LIFO, last in first out) 방식을 따른다. 배열이나 연결 리스트를 통해 구현할 수 있다. 딕셔너리 딕셔너리(Dictionary)는 키(Key)와 값(Value)이라는 요소로 이루어져 있다(쌍으로 이루어짐). 키에 해당하는 값을 저장하고 읽어오는 방식이다. 일반적으로 해시 테이블과 동일한 개념이라 할 수..

학습 목표 트라이의 원리와 구조를 설명할 수 있다. 트라이 트라이(trie)는 기본적으로 트리 형태의 자료 구조다. 트라이는 각 노드가 배열로 이루어져 있다는게 특징이다. 예시를 보자. 영어 알파벳으로 이루어진 문자열 값을 저장한다고 생각해보자. 노드는 a부터 z까지의 값을 가지는 배열이 될 것이다. 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z배열)를 가리킨다. 트라이의 시간 복잡도 앞선 예시와 같은 트라이에서 값을 검색하는데 걸리는 시간은 문자열의 길이에 의해 정해진다. 일반적인 영어 이름의 길이를 n이라고 했을 때, 검색 시간은 O(n)이지만, 대부분의 이름은 그리 크지 않은 상수이기 때문에 O(1)이나 마찬가지다. 생각해보기 트라이가 해시 테이블에 비해 가지는 장점과 단점은 무엇일까. 트라..

연결 리스트나 트리에서 값을 검색할 땐 O(n) 또는 O(log n)의 시간이 걸린다. 이 시간을 단축해서 거의 O(1)에 가깝게 할 수 있을까? 학습 목표 해시 테이블의 원리와 구조를 설명할 수 있다. 해시 테이블 해시 테이블(hash table)은 자료 구조 중 하나로 연결 리스트의 배열을 사용해 데이터를 저장한다. 각각의 데이터는 해시 함수를 통해 고유한 인덱스를 생성하고, 이를 활용해 값을 저장하거나 검색하게 된다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 쉬운 예시를 보자. 예시에서는 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 '이름의 가정 첫 글자'이다. 이 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳을 시작으로 하는 이름..