Computer Science

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.그래프는 연결 관계를 표현하는 자료구조이다. 네트워크, 운영체제 등 다양한 분야에서 범용적으로 사용하며, 알고리즘 분야에서도 자주 나오는 굉장히 중요한 자료구조라고 할 수 있다. 한 번 알아보자.1. 그래프의 종류와 구현그래프란 정점(vertex)이라 불리는 데이터를 간선(edge) 혹은 링크(link)로 연결한 형태의 자료구조를 의미한다. 이전 시간에 학습했던 트리구조 역시 노드와 노드를 간선으로 연결했었던 그래프의 일종으로, 노드 간의 상하 관계를 고려한 그래프라고 할 수 있다. 일반적인 그래프는 사이클(어떤 정점에서 다시 돌아올 경로가 있는 경우)을 형성하거나, 이웃한 정점끼리 별도의 상하 관계를 가지지 않는다.그래프는..

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.1. 트리트리는 주로 계층적인 구조를 표현하기 위한 자료구조이다. 데이터가 저장되는 노드(node), 노드와 노드를 연결하는 간선(edge 혹은 link라고도 부른다.)으로 이루어져 있으며, 간선으로 연결된 노드는 상하 관계를 형성한다. 다양한 용어가 있는데, 차례대로 알아보자.노드 간 형성된 상하 관계에서 상위는 부모 노드, 하위는 자식 노드라고 부른다.두 개념 모두 상대적인 개념이기 때문에, 자식 노드이면서 부모 노드일 수 있다.노드는 하나 이상의 자식을 가질 수 있지만, 부모 노드는 하나만 있을 수 있다.형제 노드(sibling node) : 같은 부모 노드를 공유하는 노드를 의미한다.조상 노드(ancestor node..

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.1. 배열 & 연결리스트프로그래밍 언어를 기반으로 학습을 단 한 번이라도 해봤다면 익숙한 자료구조인 배열과 연결리스트다. 배열과 연결리스트는 상황에 따라서 다른 자료구조를 만드는 재료로도 활용되기 때문에 깊게 이해하는 것이 좋다. 차근차근 알아보자.1-1 배열배열(Array)이란 일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조를 의미한다. 각 요소에는 0부터 시작하는 고유한 순서 번호인 인덱스가 매겨지며, 이 인덱스를 기준으로 요소들을 식별할 수 있다. 다음과 같은 특징을 지닌다.특정 요소 접근 시간은 요소의 개수와 무관하게 일정한 O(1)이다. 인덱스만 찾아서 조회하면 되기 때문.앞에서부터 차례대로 ..

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.1. 자료구조 개요자료구조는 말 그대로 데이터를 어떻게 효율적으로 관리하고 저장할지에 대해서 다루는 부분이다. 다양한 자료구조가 있겠지만, 대표적인 자료구조 위주로 학습할 예정이며 자료구조와 연관된 개념인 알고리즘, 그리고 시간, 공간 복잡도에 대해서도 차근차근 확인해보자.1-1 자료구조와 알고리즘앞에서 컴퓨터 구조와 운영체제를 학습하면서 자료구조에 대해서 간접적으로나마 다루었던 내용이 있었다. 예를 들어 메모리 내에 존재하는 스택 영역의 스택이나 CPU 스케줄링에 대해서 설명하면서 스케줄링 큐 같은 개념이 자료구조의 일종이었다.그렇다면 알고리즘은 무엇일까? 알고리즘은 간단하게 말하면 어떤 목적 달성을 위해 필요한 일련의 연..

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.1. 가상 메모리지난 시간까지 우리는 운영체제에서 어떻게 멀티프로세스나 멀티스레드 환경에서 통신을 관리하고, CPU 자원을 효율적으로 활용하는지에 대해서 알아봤었다. 이번에는 운영체제의 메모리 관리 기법인 가상 메모리가 무엇인지에 대해서 알아보자.앞의 내용을 본다면 자칫 CPU가 프로세스들이 메모리 속 어디에 저장되어 있는지 이미 알고 있다고 착각할지도 모른다. 하지만 그렇게 되면, 레지스터가 메모리만큼 커야 할 텐데 거기에는 무리가 있다. 또 사용 중이지 않은 프로세스는 메모리에서 해제된다. 그렇다면 어떻게 CPU는 메모리에 적재된 프로세스의 주소를 인식하고 관리할까? 이를 설명하기 위해 물리 주소와 논리 주소에 대해 먼저..

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.1. 동기화와 교착 상태앞에서 프로세스 간 통신에 대해 설명했는데, 그 상황을 한 번 상기해 보자. 프로세스 A가 공유 메모리 공간에 글을 쓰고 프로세스 B가 읽는다고 가정하면, 두 프로세스는 서로 같은 공간에서 자원을 공유하고 있다. 혹은 프로세스 내부의 스레드 2개가 프로세스가 할당받은 파일을 수정하게 되는 경우 두 스레드는 하나의 파일 자원을 공유하고 있다. 이렇게 프로세스나 스레드가 공유하는 자원은 공유 자원(shared resource)라고 한다.만약 공유 자원을 다수의 프로세스나 스레드가 동시에 어떤 규칙 없이 마구잡이로 접근하게 된다면 어떻게 될까? 이때 공유 자원에 접근하는 코드 중 동시 실행 시 문제가 발생할..

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.1. 운영체제의 큰 그림스마트폰의 운영체제인 안드로이드나 iOS나 데스크톱 PC의 윈도우나 맥OS의 경우 형태는 다른 것 같지만 제공하는 핵심적인 기능은 비슷하다. 이런 운영체제의 핵심적인 기능을 담당하는 부분을 커널(Kernel)이라고 하는데, 별다른 언급이 없다면 이제부터 운영체제라고 설명하는 부분은 이 커널을 지칭한다고 이해하면 된다.운영체제에는 2가지의 큰 핵심 기능이 있다. 하나는 자원을 할당하고 관리하는 역할이고, 다른 하나는 프로세스 및 스레드를 관리하는 역할이다. 이제 이 핵심 기능들을 차례대로 살펴보면서 전체적인 큰 그림을 그려보며 설명하겠다.1-2 운영체제의 역할운영체제에서 설명하는 자원이란 프로그램 실행에..

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.1. 메모리이전 장에서 CPU에 대해서 설명할 때, 현재 실행 중인 프로그램은 메모리에 저장되어 있고, CPU가 실행할 명령어는 메모리에 저장되어 있어야 한다고 추가적으로 설명했었는데, 이번에 좀 더 알아보자.1-1 RAM메인 메모리 역할을 하는 하드웨어에는 크게 RAM과 ROM이 있다고 했었고, 대부분 메인 메모리의 경우에는 RAM을 지칭한다. RAM은 전원 종료시 데이터가 모두 날라가는 휘발성 저장장치이며, 위에서 설명했던 것처럼 CPU가 실행할 대상을 저장하는 부품이다. 보조기억장치에 있는 프로그램을 CPU가 바로 불러올 수 없기 때문에 메모리로 불러오는 과정을 거쳐야하는데, 이 과정에서 RAM의 크기가 성능에 많은 영..