전체 글 205

[깃/git] 커밋 기록들을 다른 브랜치로 옮겨보자

방금까지 너무 우울했다... 우테코 프리코스를 진행하는데 main에서 작업하지 말라는 피드백 사항이 있었음에도 나는 main에서 작업을 해버린 것... (진짜 신경쓰는 버릇을 들여야하는데 여간 쉬운게 아니다...) 무튼 그래서 커밋 내역을 확인해보니 무려 23개나.. 사실 푸시하려다가 메인에 푸시해도 되나..? 라는 생각에 떠올라버린 것.. 23개를 손으로 일일이 옮길 수도 없는 노릇이고, 나는 다른 사람들처럼 깃에 대한 이해도가 높다고 생각하지 않아서 reset과 merge같은 것에 대한 숙련도가 부족해 그런 것도 할 수 없었다. 그래서 내가 가끔 애용하는 cherry-pick을 사용해보기로 했다. 보통 cherry-pick을 나는 unstaged에 있는 변경내역을 다른 브랜치로 옮길 때 사용했지만, ..

기타 2023.11.08

[알고리즘] 선택 알고리즘이란?

오늘은 선택 알고리즘에 대해서 알아봅시다. 선택 문제 선택 알고리즘을 알아보기 전에, 이 알고리즘이 어떻게 나오게 되었는지를 알아봅시다. 그러기 위해서 선택 문제를 우선 설명해야할 것 같은데, 선택 문제란 정렬되지 않은 길이가 n인 수열에서 k번째로 작은 숫자를 찾는 문제를 의미합니다. 통상 이 문제를 해결하기 위한 단순한 알고리즘은 아래의 두가지 일 것입니다. 1. 주어진 수열에서 가장 작은 수를 찾는 과정을 k번 반복했을 때, k번째 작은 수를 찾을 수 있습니다. 선택된 가장 작은 수는 해당 수열에서 삭제하는 방식으로 말이죠. 이렇게 된다면 시간복잡도는 아마 O(kn)이 될 것입니다. 2. 숫자들을 정렬한 이후에, k번째에 위치한 수가 k번째로 작은 수가 될 것입니다. 이는 정렬 알고리즘의 시간복잡도..

CS/Algorithm 2023.11.02

[운영체제] 리눅스의 파일 시스템

이전 글에서 다뤘던 파일 시스템의 예제 중 하나인 리눅스에 대해서 알아봅시다. Address of Data Blocks 리눅스에서는 데이터 블록 할당 기법 중에 indexed allocation method를 사용합니다. indexed allocation method는 이전 글에서 설명했으므로, 해당 글을 참고해주시기 바랍니다. 우리는 이번 글에서 조금 더 메모리 용량에 관한 부분을 알아봅시다. 보통 데이터 block은 1개당 4kb입니다. 또한 리눅스에서의 file control block의 구조를 보고 하나의 file에 사용할 수 있는 최대 용량을 알아봅시다. 리눅스의 file contro block 형태입니다. 위에 것은 무시하고 direct block와 indirect block을 살펴봅시다. 말..

CS/OS 2023.11.02

[운영체제] 파일 시스템

오늘은 파일 시스템에 대해서 알아보겠습니다. 파일 시스템 파일 시스템은 파일을 저장하는 거대 자료구조로, 여러 물리적인 파일의 종류별로 효율적인 관리를 위해 사용되는 시스템입니다. 리눅스 운영체제 기준으로 파일 시스템에는 boot block, super block, FCB list(inode list), data blocks가 있습니다. Boot Block boot block은 최초 운영체제 실행 시, 보조기억 장치에서 운영체제 이미지를 불러와 실행시키는 역할을 합니다. 운영체제 최초 실행 시, boot block을 메인 메모리로 복사하고 OS의 위치를 파악합니다. 이후, 보조기억장치에서 OS의 위치로 접근하여 OS를 메모리에 로드합니다. 이렇게 되면 OS가 최초로 실행하는 다양한 작업(프로세스 생성, ..

CS/OS 2023.10.28

[운영체제] 디렉토리

오늘은 디렉토리에 대해서 알아봅니다. 디렉토리 디렉토리는 파일의 속성을 저장하는 파일을 의미합니다. 정확히는 file의 이름과 FCB의 식별자만을 저장합니다. 디렉토리에 파일을 복사하여 저장하는 것은 비효율적이기 때문이죠. 보통 디렉토리에 저장되는 정보들은 아래와 같습니다. 여기서 inode는 index node의 약자로 리눅스에서의 FCB를 호칭명입니다. 디렉토리에는 현재 파일과 상위 파일의 정보까지 저장한다는 것을 기억해두시면 좋습니다. Hierachical Directory 우리가 흔히 쓰는 디렉토리는 계층 구조를 가집니다. 가장 루트 노드를 필두로 하여 여러 디렉토리들이 있고 이러한 것을 계층으로 관리하기 때문이죠. 이러한 계층 구조를 이용해서 디렉토리가 파일을 찾는 과정을 예시를 통해 확인해봅시..

CS/OS 2023.10.28

[운영체제] File

오늘은 File에 대해서 알아봅시다. File 파일은 보조 기억 장치에 저장되어서 전원이 꺼져도 지워지지 않는 저장 단위를 일컫습니다. FCB 우리는 전에 프로세스, 쓰레드 부분에서 PCB, TCB가 존재한다는 것을 알았습니다. 이와 같이 file도 FCB가 존재합니다. 이름만 다를 뿐 목적은 비슷하지만, 파일을 관리하기 위해 PCB, TCB와는 다른 정보들을 포함하고 있습니다. 기본적으로 file name, file size, create time 등.. 우리가 어떤 파일에 대해서 기본적으로 확인할 수 있는 정보들부터 자세한 정보들이 담겨있습니다. FCB와 PCB... 다른점이 분명 존재합니다. File와 FCB는 컴퓨터의 전원이 꺼져도 존재해야합니다. 그래서 이러한 정보들은 메인 메모리가 아닌 보조 ..

CS/OS 2023.10.28

[운영체제] Deadlock 처리

오늘은 앞선 글에서 다룬 Deadlock에 대해서 OS는 어떻게 처리하는지 알아봅시다. Deadlock을 처리하는 방법 Deadlock을 처리하는 방법에는 3가지가 있습니다. Deadlock이 발생되지 않도록 예방하는 방법 Deadlock이 발생되었다면 이를 감지하고 해결하는 방법 Deadlock이 발생되어도 아무것도 하지 않는 방법 Deadlock 예방하기 우리는 이전 글에서 Deadlock이 발생하는 조건에 대해서 알아봤습니다. Mutual Exclusion, Hold-and-Wait, No Preemption, Circular wait. 이 네가지 조건을 모두 만족해야 Deadlock이 발생했었죠. 그렇다면 우리는 이 네 가지 조건 중 하나만 성립하지 않게 한다면 Deadlock이 발생되는 것을 막..

CS/OS 2023.10.21

[운영체제] Deadlock

오늘은 이전 포스팅들에서 간단히 언급되었던 Deadlock에 대해 다뤄보겠습니다. Deadlock 데드락. 우리는 이 개념을 설명하기 위해 Starvation이라는 개념을 먼저 소개했었습니다. Starvation은 프로세스가 critical section을 실행하려고 하는데, 다른 프로세스가 이미 critical section을 실행 중이여서 이를 위해 평소보다 오래 기다리는 상태를 의미합니다. 이에 확장 개념인 Deadlock은 Starvation이 영원히 지속되는 것을 의미합니다. 아래의 그림은 Deadlock을 아주 잘 나타내는 그림입니다. 데드락이 발생하는 경우 Reusable Resource 중 하나인 메모리의 할당량이 200Kb라고 해봅시다. P1, P2는 특정 용량만큼의 메모리를 요구하는 프..

CS/OS 2023.10.21

[알고리즘] 그리디 알고리즘이란? - 1

오늘은 그리디 알고리즘에 대해서 알아보겠습니다. 그리디 알고리즘 그리디 알고리즘, 욕심쟁이 알고리즘이라고 불리는 이 방식은 문제를 해결하기 위핸 문제해결 패러다임 중 하나입니다. 매순간마다 직면한 상황에서 가장 좋은 선택지를 선택하는 알고리즘이죠. 그리디 알고리즘에 속하는 많은 알고리즘이 있습니다. 동전 거스름돈 문제 최소 신장 트리(MST) 구하기 최단 경로 찾기 부분 배낭 문제 집합 커버 문제 작업 스케쥴링 허프만 압축 오늘은 이 중에서 집합 커버 문제까지 다뤄보겠습니다. 동전 거스름돈 문제 음료수 자판기가 있다고 해봅시다. 각 자판기는 현금을 받고 음료수를 줍니다. 거스름돈이 있다면 거스름돈을 어떻게 줄지에 대해서 결정해야합니다. 이 때, 그리디 알고리즘이 쓰입니다. 대한민국 기준으로 동전은 500..

CS/Algorithm 2023.10.17

[알고리즘] Floyd-Warshall 알고리즘이란?

오늘은 그래프의 최단 경로를 찾는 알고리즘 중 마지막 Floyd-Warshall 알고리즘에 대해서 알아보겠습니다. Floyd-Warshall 알고리즘 Floyd-Warshall 알고리즘은 기존 Dijkstra와 Bellman-Ford의 단점을 모두 보완한 알고리즘입니다. 총 n번 반복하는동안 i(i=0, 1, ..., n-1)번째 정점을 경유하여 가는 경우들을 갱신하는 방법을 이용합니다. Floyd-Warshall은 DP(Dynamic Programming)에 속합니다. 결국 Floyd-Warshall 알고리즘을 이용하여 결과를 도출할 때, 각 정점 사이의 거리를 이용하여 결과를 도출하기 때문입니다. 예제를 통해 Floyd-Warshall 알고리즘의 과정을 살펴봅시다. 위와 같은 그래프와 우측에는 D라는..

CS/Algorithm 2023.10.16