그래프 (Graph) 정점과 간선으로 이루어진 자료구조 (Cyclic) 지하철 노선도, 통신 네트워크 등에 사용 그래프의 종류 (1) 무방향 그래프 : 간선에 방향이 없는 그래프 (양방향 이동 가능) (2) 방향 그래프 : 간선에 방향이 있는 그래프 (해당 방향으로만 이동 가능) (3) 가중치 그래프 : 간선에 값이 있는 그래프 (이동 비용) (4) 완전 그래프 : 모든 정점이 서로 연결되어 있는 그래프, 노드가 N 개일 경우, 간선의 수는 N(N-1)/2개 그래프 탐색 (1) 깊이 우선 탐색 (Depth First Search; DFS) DFS는 그래프 또는 트리에서 모든 노드를 탐색하는 알고리즘으로 스택 또는 재귀 함수를 사용하여 구현할 수 있다. 시작 노드를 방문하고 방문한 노드를 스택에 push ..
해시 (Hash) 해시는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 매핑하는 과정 또는 그 결과를 말한다. 해시 함수 (Hash Function) 매핑 과정을 수행하는 함수로서, 입력 데이터를 받아서 해시 값을 계산하여 반환하는 함수 동일한 입력에 대해서는 항상 동일한 해시 값을 반환하며, 입력 데이터가 조금이라도 변경되면 다른 해시 값을 생성 데이터의 무결성을 검증하거나 데이터의 식별을 위해 사용 Divison 기법 : 간단한 해시 함수, 입력값을 특정 수로 나눈 나머지를 해시 값으로 사용 H(k) = k mod m, k = 입력값, m = 해시 테이블 크기) Multiplication 기법 : 입력값과 곱셈을 통해 해시 값을 계산하는 방법 0에서 1사이의 상수 A를 선택하고 k * A 의 소수..
이진 탐색 트리 (Binary Search Tree) 아래의 규칙으로 구성된 이진 트리이다. 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다. 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다. 각각의 서브 트리도 이진 탐색 트리이다. 중복된 키를 허용하지 않는다. 이진 탐색 트리의 특징 이진 탐색 트리 규칙에 의해 데이터가 정렬되어 있다. 이진 트리에 비해 탐색이 빠르다. 균형 상태 일때 : O(log n) 불균형 상태 일때 : O(n) 이진 탐색 트리 - 탐색 찾고자 하는 데이터를 루트 노드부터 비교하여 탐색한다. 대소 비교를 하여 찾는 데이터가 현재 노드보다 작으면 왼쪽, 크면 오른쪽 노드로 이동한다. 찾는 데이터가 없으면 null을 반환한다. 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 ..
CPU 스케줄링 운영 체제에서 다중 프로세스를 관리하고 CPU의 사용을 최적화하기 위한 방법 여러 프로세스가 CPU를 공유하는 다중 프로그래밍 환경에서 CPU 스케줄러는 어떤 프로세스가 CPU를 사용할 수 있는지 결정하고, 프로세스들 사이의 우선순위를 관리한다. 선점 스케줄링 vs 비선점 스케줄링 선점 스케줄링 (Preemptive Scheduling) 현재 실행 중인 프로세스가 다른 프로세스에 의해 강제로 중단되고, 다른 프로세스가 CPU를 차지할 수 있는 방식 우선순위가 높은 프로세스가 CPU 시간을 뺏어갈 수 있다. 실시간 시스템에서 중요하다. 프로세스의 응답 시간을 보장하고 우선순위가 높은 작업을 즉시 처리할 수 있다. 컨텍스트 스위칭에 따른 오버헤드가 발생할 수 있다. 종류 : SRTF, 우선순..
이 글은 '스프링 부트 핵심 가이드 - 스프링 부트를 활용한 애플리케이션 개발 실무' 책을 통해 학습한 내용을 정리한 글입니다. 04장. 스프링 부트 애플리케이션 개발하기 프로젝트 생성 spring initializer를 통해 생성 프로젝트 이름, 생성할 위치, 언어, 타입(Gradle, Maven), 그룹과 아티팩트, 자바 버전, 패키지 생성 옵션 선택 의존성은 프로젝트를 생성할 때 추가 가능하고, 생성 이후에도 추가 가능 Maven / Gradle maven : pom.xml 파일에 프로젝트 설정과 의존성 관리 gradle : build.gradle 파일에서 프로젝트 설정과 의존성 관리 05장. API를 작성하는 다양한 방법 GET API 1. @RequestMapping @RequestMapping..
IPC (Inter Process Communication) 프로세스는 독립적으로 실행되는 단위이므로 기본적으로 다른 프로세스와의 통신이 어렵다. 이를 해결하기 위해 운영체제의 커널 영역에서 IPC 기능을 제공한다. IPC 종류 1. PIPE(Anonymous PIPE) 파이프는 두 개의 프로세스를 연결 하나의 프로세스는 데이터를 쓰기만, 다른 하나는 데이터를 읽기만 할 수 있다. 한쪽 방향으로만 통신이 가능하기 때문에 단방향 통신 또는 Half-Duplex(반이중) 통신이라고 부른다. 파이프는 하나의 통신 선로로 읽기 또는 쓰기 중 하나만 가능하므로, 송수신을 동시에 수행해야 하는 경우 두 개의 파이프를 사용해야 한다. 같은 부모 프로세스를 가지는 프로세스들 사이에서만 통신이 가능하다. 읽기/쓰기 중 ..
PCB (Process Control Block) PCB는 운영체제가 각 프로세스를 관리하기 위해 유지하는 자료구조이다. 각 프로세스마다 하나의 PCB가 할당되며, PCB에는 해당 프로세스에 대한 정보가 저장된다. PCB에 저장되는 정보 프로세스 식별자(Process Id) 각 프로세스에는 고유한 식별자가 할당된다. 프로세스를 식별하고 구분하기 위해 사용 프로세스 상태(Process State) 프로세스의 현재 상태를 나타낸다. new, ready, running, waiting, terminated가 있다. 스케줄링 및 운영체제의 상태 관리에 사용 프로그램 카운터(Program Counter) 현재 프로세스가 다음에 실행할 명령어의 주소를 가리키는 레지스터 값 프로세스가 중단되었다가 다시 실행될 때, ..
시스템 콜 (System Call) 시스템 콜 : 운영체제 커널의 기능을 사용하기 위해 사용자 프로그램이나 응용 프로그램이 호출하는 인터페이스 시스템 콜은 프로세스가 운영체제의 커널 모드로 전환되어 특정 기능을 수행하고, 이후 다시 사용자 모드로 돌아가 프로그램이 실행되는 원리로 동작한다. 시스템 콜 사용 운영체제가 제공하는 다양한 서비스와 리소스에 접근하기 위해 사용 ex) 파일 시스템 접근, 네트워크 통신, 메모리 관리, 프로세스 관리 등 시스템 콜은 운영체제의 기능을 사용하기 위해 특정 함수를 호출하는 형태로 제공된다. 시스템 콜 호출 방식 프로그래밍 언어의 라이브러리 함수나 시스템 인터페이스를 통해 간접적으로 호출 시스템 콜의 종류 1. 파일 관련 시스템 콜 open() : 파일을 열고 사용하기 ..
힙(Heap) 완전 이진 트리 형태 중복 값 허용 반 정렬 상태 최솟값 또는 최댓값을 빠르게 찾아내는데 유용한 자료구조 최소 힙, 최대 힙 우선순위 큐(Priority Queue)를 구현하는데 사용 최소 힙(Min Heap) 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태 (루트 노드가 최소값을 가지는 힙) 최대 힙(Max Heap) 부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태 (루트 코드가 최대값을 가지는 힙) 힙 구현 배열을 사용하여 구현 완전 이진트리의 특성에 따라 배열에서 각 노드는 인덱스로 표현 루트 노드는 인덱스 0에 위치하며, 자식 노드들은 특정한 방식으로 인덱스를 계산하여 배열에 저장 # 부모 노드와 자식 노드의 관계 왼쪽 자식 index = 부모 index * 2 오른쪽..
트리(Tree) 노드와 링크로 구성된 자료구조 계층적 구조를 나타낼 때 사용 ex) 폴더 구조, 조직도, 가계도, etc. 트리의 특징 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다. 노드가 N개인 트리의 Edge의 수는 N-1개 이다. Cycle이 존재하지 않는다. (Acyclic) 모든 노드는 서로 연결되어 있다. 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리된다. 이진 트리 종류 1. 이진 트리(Binary Tree) 각 노드는 최대 2개의 자식을 가질 수 있다. 자식 노드는 좌우를 구분한다. 2. 포화 이진 트리(Perfect Binary Tree) : 모든 레벨에서 노드들이 꽉 채워져 있는 트리 3. 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하..
