본문 바로가기

# Foundation

(81)
# Foundation/알고리즘 [코딩테스트 대비] 트라이(Trie) 자료구조 개요 접근법 Trie라는 용어 자체는 생소할 수 있지만, 알게 모르게 실생활에서도 사용한 적이 있을만큼 매우 간단한 개념입니다. 예를 들어, 영어사전에서 apple 이라는 단어를 찾고 싶다면, 앞에서부터 a - p - p - l - e 순서로 prefix를 조합하면서 찾아갈 수 있습니다. // 영어사전에서 apple를 찾고 싶다면... 앞에서 a를 찾는다. -> a 이어지는 p를 찾는다. -> ap 이어지는 p를 찾는다. -> app 이어지는 l를 찾는다. -> appl 이어지는 e를 찾는다. -> apple 위와 비슷하게 xx시 xx고등학교 xx학년 xx반에 소속된 학생정보를 찾고 싶다면, 앞에서부터 prefix를 조합하면서 차례대로 접근하면 됩니다. step 1) xx시 step 2) xx시 xx고등..

2020. 9. 16. 19:37

# Foundation/알고리즘 [코딩테스트 대비] 순열(Permutation)과 조합(Combination) 알고리즘 개요 순열Permutation과 조합Combination은 코딩테스트에서 매우 빈번하게 사용되는 도구 중 하나입니다. 어떤 배열의 순열 또는 조합을 구하라!라는 직접적인 문제는 출제되지 않지만, 이것을 사용해야 문제가 풀리는 경우가 많으므로 순열과 조합 알고리즘 구현에 대해 정리하고자 합니다. 해당 포스팅에서는 TypeScript를 사용하여 구현했지만, 다른 언어에서도 충분히 구현할 수 있을만큼 상세하게 설명하겠습니다. 순열 (Permutation) 정의 길이가 $n$인 배열에서 $r$개의 요소를 차례대로 뽑아 새로운 배열을 만들었을 때, 가능한 모든 배열의 합입니다. 예를 들어 [1, 2, 3, 4]라는 배열에서 3개의 요소를 뽑아 새로운 배열을 만든다고 한다면, 아래와 같이 24개의 배열이 도출됩니다..

2020. 9. 15. 20:37

# Foundation/운영체제 운영체제 공룡책 정리 🦖 ch05. CPU 스케줄링 CPU 스케줄링 개념 하나의 시스템에서 여러개의 프로세스가 실행되고 있을 때 Running 상태의 프로세스가 CPU를 사용하지 않는 기능을 요구했다고 가정해봅시다. 예를 들면 키보드 입력을 기다린다던지 파일이 전부 읽어질 때 까지 기다린다던지와 같은 경우가 있겠네요. 결과적으로는 해당 입출력이 끝날 때 까지 대기해야 하므로 CPU를 사용할 수 있었지만 대기밖에 못하는 상태로 볼 수 있겠고, 이것은 다른 프로세스가 유효하게 사용할 수 있었던 CPU 시간을 낭비한 것과 같아집니다. 다른 시각에서 보면 CPU가 놀고있다라고 볼 수 있겠죠. 따라서 운영체제는 프로세스가 CPU를 사용하지 않는 기능을 실행하면 그 프로세스는 더 이상 CPU를 유효하게 사용하지 못하므로, 해당 프로세스의 CPU 이용권을 빼앗아 다른..

2020. 7. 30. 16:46

# Foundation/운영체제 운영체제 공룡책 정리 🦖 ch04. 다중 스레드 프로그래밍 스레드 개념 스레드는 CPU 이용의 기본 단위이며 프로세스를 이루는 단위이기도 합니다. 각각의 스레드는 스레드 ID 프로그램 카운터 레지스터 집합 스택으로 구성되며, 메모리 측면에서 보면 스레드 개인 메모리 + 프로세스 공유 메모리에 접근할 수 있습니다. 왜 필요한가? 현대 운영체에 스레드가 도입된 이유는 종래에는 프로세스가 하나의 동작밖에 하지 못했다는 것 입니다. 첫 번째 예시로 웹서버를 생각해보겠습니다. 현대는 각 클라이언트마다 하나의 스레드를 만들어 대응하고 있지만, 예전에는 각 클라이언트마다 하나의 프로세스를 만들어 대응해야 했기 때문에, 엄청난 병목을 감수할 수 밖에 없습니다. 프로세스를 생성하는 작업은 매우 무겁거든요. 두 번째 에시로 맞춤법을 교정해주는 워드프로세서를 생각해보겠습니다. 이 ..

2020. 7. 28. 15:44

# Foundation/운영체제 운영체제 공룡책 정리 🦖 ch03. 프로세스 프로세스 프로세스의 개념 비공식적으로 프로세스란 실행 중인 프로그램을 가르킵니다. 다음과 같이 텍스트 영역, 데이터 영역, 힙 영역, 스택 영역, 자유 공간이 할당된 프로그램 이상의 개념이며 프로그램 카운터를 갖는 능동적 개체입니다. 잡(Job)은 프로세스의 별칭입니다. 프로세스의 상태 프로세스는 실행되면서 그 상태가 변화합니다. 각 프로세스는 다음 상태들 중 하나입니다. 생성 (New) : 프로세스가 생성 중 입니다. 실행 (Running) : 해당 프로세스의 명령어가 실행 중 입니다. 대기 (Waiting) : 입출력의 완료 신호를 기다리고 있습니다. 준비 (Ready) : 프로세스의 실행 순번이 오길 기다리고 있습니다. 종료 (Terminated) : 프로세스가 종료되었습니다. 한 가지 시나리오를 ..

2020. 7. 27. 20:55

# Foundation/운영체제 운영체제 공룡책 정리 🦖 ch02. 운영체제 구조 운영체제 서비스 각각의 운영체제는 설계된 목적과 자신만의 고유한 기능이 있습니다. 운영체제들은 해당 목적을 효율적으로 달성하기 위해 각기다른 디자인과 알고리즘을 선택하지만, 보편적으로 다음 기능들은 공통으로 제공됩니다. 단일 사용자 기능 사용자 인터페이스 운영체제는 하드웨어와 사용자 사이를 중재하는 소프트웨어이므로, 사람이 사용하기 편리한 형태의 인터페이스를 제공해야 합니다. 보통 CUI 또는 GUI중 하나를 선택하지만, 경우에따라 두 개 다 지원하는 운영체제도 있습니다. 프로그램 실행 운영체제는 폰 노이만 구조에 따라 프로그램을 메모리에 적재하여 실행시킬 수 있어야 하며, 프로그램이 비정상적으로 종료된 경우에는 원인을 파악한 뒤 디스플레이할 수 있어야 합니다. 입출력 연산 프로세스는 파일, 키보드와 같..

2020. 7. 26. 11:44

# Foundation/운영체제 운영체제 공룡책 정리 🦖 ch01. 운영체제 개요 운영체제란? 운영체제의 정의 컴퓨터를 사용하여 특정 목적을 유용하게 달성하기 위한 도구. 하드웨어를 관리하는 소프트웨어. 하드웨어와 사용자 사이를 중재하는 소프트웨어. 운영체제의 목적 각 운영체제에는 달성하고자할 목적이 있으며 시스템의 크기에 따라 목적이 달라집니다. 대형 시스템 : 하드웨어 사용 최적화. 중형 시스템 : 대형 시스템과 소형 시스템의 중간지점. 소형 시스템 : 사용자가 편리하게 사용할 수 있는 인터페이스 제공. 프로그램의 구분 커널 : 운영체제의 핵심. 항상 실행되는 프로그램. 시스템 프로그램 : 운영체제와 연관되어 있으나 커널의 일부분은 아닌 프로그램. 응용 프로그램 : 그 이외의 프로그램. 부트스트랩과 Init 컴퓨터에 전원이 인가될 때 처음 실행되는 프로그램으로 펌웨어 또는 ROM에..

2020. 7. 25. 22:32

# Foundation/운영체제 운용체제 공룡책 정리 🦖 readme 공룡책 운영체제를 대표하는 귀염둥이 마스코트 공룡책입니다. 대학교부터 시작해서 취준 및 이직 기술면접에도 나와 저희를 괴롭히는 악당이죠. 운영체제를 공부할 때 마다 1000 페이지에 달하는 공룡책을 매번 펼칠수는 없기 때문에 면접에 필요한 챕터만 추려내어 중요한 내용만 따로 정리합니다. 정리한 목차 01장 : 운영체제 개요 02장 : 운영체제 구조 03장 : 프로세스 04장 : 멀티 쓰레드 프로그래밍 05장 : CPU 스케줄링 06장 : 프로세스 동기화 07장 : 교착상태 08장 : 메모리 관리 전략 09장 : 가상 메모리 12장 : 2차 저장장치 구조

2020. 7. 24. 22:39