전체 글

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

문제 링크https://www.acmicpc.net/problem/2609문제 풀이 과정최대공약수와 최소공배수 문제에 대해 효율적으로 풀기 위해서는 유클리드 호제법에 따라 최대공약수를 푸는 방법에 대해 알아야 손쉽게 풀 수 있다.유클리드 호제법이란 2개의 자연수에 대한 최대공약수를 구하는 방식이다. 쉽게 설명하면 두 수 a,b에 대해서 더 작은 수로 나눈 나머지로 끊임없이 0이 될때까지 나누는걸 의미한다. 이걸 쉽게 설명하려면 아래 예시가 가장 쉽게 이해가 된다.더보기1. 1500 ÷ 3261500을 326으로 나눈 몫은 4이고, 나머지는 196이야.즉, 1500 ÷ 326 = 4 (몫), 나머지 1962. 326 ÷ 196이제 326을 196으로 나눠. 몫은 1이고, 나머지는 130이야.즉, 326 ÷..

"이것이 취업을 위한 컴퓨터 과학이다 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 운영체제의 역할운영체제에서 설명하는 자원이란 프로그램 실행에..