👩🏻‍💻 은진의 로그파일 ✍️

다익스트라(Dijkstra) 최단 경로 알고리즘 최단 경로 탐색 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 음의 간선을 포함할 수 없다. 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 적합하다. 인공위성 GPS 소프트웨어 다익스트라 알고리즘은 그리디 알고리즘 / 다이나믹 프로그래밍으로 분류 단계마다 가장 비용이 적은 노드를 선택한다. (그리디) 최단 거리는 여러 개의 최단 거리로 이루어져있으므로, 최단거리를 구할 때 이전까지 구했던 최단 거리 정보를 그대로 사용한다. (DP) 최단 거리 테이블 최단 거리 테이블은 각 노드까지의 현재 최단 거리 정보를 저장한다. 더 짧은 경로(비용이 더 적은 경로)를 찾은 경우 갱신한다. 동작..

셸 정렬의 등장 삽입 정렬의 보완 삽입 정렬은 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다. 역순으로 정렬된 최악의 경우, 이동을 많이 해야 최종 위치에 다다를 수 있다. 삽입 정렬의 시간복잡도 O(n) : 이미 정렬된 최선의 경우, n-1번의 1회차 비교만 수행한다. O(n^2) : 역순으로 정렬된 최악의 경우 1+2+3+ ... + (n-2) + (n-1) = 총 n(n-1)/2번 이동한다. 셸 정렬 데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다. 데이터를 다시 잘게 나누어서 삽입 정렬한다. 이렇게 계속 하여 마침내 정렬이 된다. 나누는 간격 k 간격 k의 초깃값 : (데이터 개수) / 2 매 회전마다 k는 절반으로 나눈다. 단, 항상 홀수가 되도록 값을 수정한다. (짝수인 경우 +1..

정수를 2진수로 변환 2를 나눈 나머지를 역순으로 읽음 실수를 2진수로 변환 실수부도 정수부처럼 처리할 때 문제 : 중복 발생 1.9 -> 1.1001 1.41 -> 1.100 1 해결 : 2를 곱하면서 정수 (1, 0)을 뽑아냄 실수 0.625 --> 이진수 0.101 0.625 * 2 = 1.25 -> 정수 1 뽑기, 나머지 0.25 0.25 * 2 = 0.5 -> 정수 0 뽑기, 나머지 0.5 0.5 * 2 = 1.0 -> 정수 1 뽑기, 나머지 0이 나오면 종료, 뽑은 숫자를 순서대로 읽어줌 고정소수점 (Fixed Point) 32비트 실수를 고정 소수점 방식으로 표현할 경우 실수 7.625 --> 2진수 111.101 16비트 체계를 쓴다고 가정하면 다음과 같다. 부호 비트 : 숫자 자체가 양수..

컴파일 언어 소스 코드 전체를 컴파일 한 후 (기계어로 번역한 후) 기계어를 CPU/메모리를 통해 읽어 실행하는 방식으로 동작하는 언어 컴파일 언어 특징 규모가 큰 프로그램은 컴파일 시 오래 걸릴 수 있다. 컴파일 후에는 모든 소스코드가 기계어로 변환되어 있기 때문에 실행 시간이 빠르다. 컴파일 언어 종류 C, C++, Java, C# 빌드 빌드(Build) : 컴퓨터에서 이해할 수 있는, 즉 실행 가능한 파일로 만드는 과정이다. 우리가 만든 소스코드를 '빌드'하면 실행 파일을 얻는다. 실행파일은 exe, exec 등등 여러 종류가 있고, 실행파일은 CPU가 읽을 수 있는 이진코드인 기계어(Machine Code)로 이루어져 있다. 인터프리터 언어 (스크립트 언어) 소스 코드를 컴파일하지 않고 인터프리터..

context switching 컨텍스트 스위칭 인터럽트나 시스템 호출 등으로 실행 중인 프로세스의 제어를 다른 프로세스에 넘겨 실행 상태가 되도록 하는 것을 프로세스 컨텍스트 스위칭 (문맥 교환)이라고 한다. 컨텍스트 스위칭이 일어나면 프로세서의 레지스터에 있던 내용을 나중에 사용할 수 있도록 저장한다. "준비 -> 실행" 상태, "실행 -> 준비" 상태, "실행 -> 대기" 상태로 바뀔 때 발생한다. 이전 프로세스의 상태 레지스터 내용을 보관하고, 다른 프로세스의 상태 레지스터를 적재하여 프로세스를 교환한다. 컨텍스트 스위칭의 단점 프로세스 P1이 "실행 -> 유휴 (준비 or 대기상태를 말함)" 상태가 될 때 P1이 바로 실행되지 않고, 유휴 상태를 좀 더 유지하다가 실행 상태가 된다. 왜냐하면 P..

DFS : 깊이 우선 탐색, 루트 노드의 한 브런치의 마지막 노드까지, 모든 노드를 탐색한 후 다음 브런치를 탐색하는 방법. 한 방향으로 계속 탐색하다가 마지막 노드에 도달하면 가장 가까운 갈림길로 돌아가 새로운 브런치를 탐색한다. 모든 노드를 방문할 때, 완전 탐색을 할 때 사용한다. 재귀적으로 동작하며, 자기 자신을 호출하는 순환 알고리즘의 형태이다. Stack 자료구조를 사용하여 후입선출(LIFO) 원칙으로 탐색한다. BFS : 너비 우선 탐색, 루트 노드와 인접한 노드부터 우선적으로 탐색하는 알고리즘 최단 경로를 찾을 때 사용한다. 시작점에서 목적지까지 한 단계씩 탐색하기 때문. 목적지에 도달하는 순간 알고리즘을 종료한다. 더 많은 단계를 거쳐야 목적지에 도달할 수 있는 경로는 더 이상 탐색할 필..

구현이 간단하지만 비효율적인 정렬방법 : 삽입 정렬, 선택 정렬, 버블 정렬 구현이 복잡하지만 효율적인 정렬방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬 버블정렬 서로 인접한 두 원소를 비교하여 순서대로 교환한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외된다. 정렬을 1회전 수행할 때마다 정렬에서 제외되는 원소가 하나씩 증가한다. 시간복잡도 O(n^2) 회차마다 비교를 n-1, n-2, … , 2, 1 번하므로 총 n(n-1)/2 선택정렬 최소값을 찾은 후 첫번째 원소와 교환한다. 1회전을 수행하고 나면 첫번째 원소를 제외한 최소값을 찾은 후, 두번째 원소와 교환한다. 정렬을 1회전 수행할 때마다 정렬에서 제외되는 원소가 하나씩 증..

[1] RESTful API란? 1. 웹 애플리케이션 상에 존재하는 모든 리소스에 대해 고유의 URI를 부여하고 HTTP URI를 통해 자원을 명시한다. 리소스는 미디어, DB 데이터 등을 모두 포함한다. 2. HTTP Method(GET, POST, PUT, DELETE)를 이용해 리소스에 대해 CRUD (CREATE, READ, UPDATE, DELETE) 명령을 적용하는 것을 의미한다. HTTP Method POST URI 요청 시 리소스를 생성한다. (CREATE) GET 리소스 조회 및 자세한 정보를 가져온다. (READ) PUT 리소스를 수정한다. (UPDATE) DELETE 리소스를 삭제한다. REST = Representational State Transfer 의 약자 (대표 상태 전달) ..

스레드 한 프로세스 내에서 구분지어진 실행 단위이다. 프로세스가 다수의 스레드로 구분되어있지 않으면, 단일 스레드 하나로 프로세스가 실행된다. 즉, 프로세스의 하나밖에 없는 스레드가 실행 단위가 되는 것이다. 위의 경우 통상적으로 프로세스를 실행 단위로 본다. 스레드의 컨텍스트 스위칭 하나의 프로세스 안에 다수의 스레드가 있을 때, 공유하는 자원이 있다. 스레드는 코드, 데이터, 힙 영역을 공통된 자원으로 공유해서 사용한다. 각 스레드는 스택 영역만을 따로 가지고 있다. 공유하는 자원이 있기 때문에, 컨텍스트 스위칭이 일어날 때 *캐시 적중률이 올라간다. 컨텍스트 스위치를 할 때 모든 자원을 대상으로 하지 않기 때문에 효율적이다. * 캐시 적중률 (Hit Rate) 원하는 정보가 캐시 메모리에 기억되어 ..

메모리 = 메인 메모리 (RAM) 메모리란 주소를 통해 접근하는 객체로, 메인 메모리는 주기억장치를 의미합니다. 따로 언급이 없으면 메모리는 메인 메모리를 의미합니다. 컴퓨터에서 메모리는 중요한 작업공간입니다. 프로세스는 CPU에서 바로 계산을 할 수 없고, 메모리에 적재한 후에 실행할 수 있습니다. 프로그램이 프로세서(CPU)에 할당되려면 (프로그램이 프로세스가 되어 실행하려면) 메모리에 적재되어야 합니다. 메모리 = 주소로 인덱싱하는 커다란 배열 컴퓨터를 부팅하면 텅텅 비어있던 메모리에 운영체제, 사용자 프로그램이 배열 원소처럼 메모리에 채워집니다. 이들은 CPU를 점유할 기회를 노립니다. 컴파일러 CPU는 메모리에 채워진 프로그램 코드를 곧장 읽을 수 없고, 컴퓨터가 이해할 수 있도록 숫자로 바꿔줘..