본문 바로가기

전체 글71

스택(stack), 큐(queue) 스택(stack) 스택은 제약을 갖는 배열로, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 LIFO 자료 구조이다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 나중에(최근에) 푸쉬한 자료부터 나오게 된다. 나중에 넣은 값이 먼저 나오는 Last In, Frist Out(LIFO) 구조로 이루어져 있다. 제약을 갖는 자료 구조인 스택이 중요한 이유 1) 잠재적 버그를 막을 수 있다. 스택 위 항목을 제외하고는 삭제할 수 없으므로 배열 중간의 데이터를 삭제하는 코드를 작성하면 오류가 발생한다. 2) 문제를 해결하는 새로운 사고 모델을 제공한다. 스택은 마지막에 들어온 데이터부터 먼저 처리하는 후입 선출 방.. 2022. 1. 20.
소프트 링크, 하드 링크 링크(Link) 링크는 컴퓨터 상에서 어떤 대상으로의 연결이나 그와 연관한 복사본을 가리킨다. 우리가 윈도우에서 보는 모든 파일도 실제 파일에 대한 파일 시스템의 링크이다. 파일 시스템은 하드디스크 안의 실제 데이터에 쉽게 접근할 수 있도록 파일을 조직하고 관리하는 체제이다. 우리는 디스크에 기록된 실제 데이터를 직접 보는 게 아니라 파일 시스템에 기록된 파일의 정보(Inode)를 보고 있는 것이다. 파일 시스템 정보에는 파일에 대한 여러 정보와 함께 실제 파일이 저장된 디스크에 찾아갈 수 있는 링크 또한 저장되어 있다. 심볼릭 링크와 하드 링크를 이해하기 위해서는 Inode 개념을 먼저 이해해야 한다. 아이노드(Inode) 위키피디아 Inode는 유닉스 계통의 파일 시스템에서 사용하는 자료 구조다. I.. 2022. 1. 18.
표준 스트림(Standard Stream), 파이프(pipe) 표준 스트림 위키피디아 유닉스 및 유닉스 계열 운영 체제에서 프로그램(프로세스)과 주변 장치 사이에 미리 연결된 입출력 통로이다. 보통 입출력은 물리적으로 연결된 시스템 콘솔의 키보드와 모니터를 통해 일어나는데, 표준 스트림은 이것을 추상화한 것이다. 🔎 키보드와 모니터 같은 장치들의 입출력을 추상화한다는 것은 대체 무슨 뜻일까? 예전에는 입출력 장치를 다룰 때 각각의 장치들마다 전용 함수가 존재했다. 전용함수가 존재한다는 것은 어떤 입출력 장치를 사용할 때 어떤 데이터 형식을 사용할 것인지가 이미 정해져 있다는 뜻이다. 예를 들어, 키보드로 키를 입력받는 경우 getch와 같은 콘솔함수를 사용했고 이 함수는 4바이트 정수형 데이터 값을 반환하게 된다. 그래서 다양한 입출력 장치를 사용하기 위해서는 각 .. 2022. 1. 17.
도커를 위한 리눅스 쉘(bash) 이해 Docker는 기본적으로 리눅스 커널이 제공하는 기능 위에서 동작한다. 커널은 시스템 자원들을 관리하는 운영체제의 핵심이라고 했다. 쉘이라는 인터페이스를 통해 사용자의 명령어를 커널에 전달하여 시스템 자원들을 관리할 수 있다. 즉, 리눅스 커널을 조작하기 위해 리눅스 쉘 사용법을 알아야 한다. 리눅스 쉘에는 Bourne shell(sh), Bourne-again shell(bash), C shell, Korn shell(ksh) 등이 있는데, 현재 linux의 기본 shell 이자 가장 범용적으로 사용되는 것은 Bourne-again shell(bash)이다. 리눅스 bash는 사용자가 명령 줄을 입력하는 방식(CLI)의 장치이므로, 리눅스 명령어를 익힌다는 것은 결국 bash가 제공하는 명령어를 배우는.. 2022. 1. 17.
현대의 운영체제: 인터럽트 기반 시스템, 컴퓨터 버스 컴퓨터의 전원을 켜면 먼저, POST 과정이 시작되고 그 후에 부트 로더가 하드 디스크에 있는 운영체제 프로그램을 RAM으로 가져와 할당한다. 할당된 운영체제의 커널은 컴퓨터의 전원이 꺼질 때까지 메모리에 상주한다. 이제 부팅이 다 끝나고 우리는 운영체제(윈도우) 화면을 보게 되었다. 사용자가 운영체제에서 마우스를 움직인다고 가정하자. 이 동작을 컴퓨터는 어떻게 알고 실행할 수 있을까? 바로 인터럽트를 통해 알 수 있다. 이벤트와 인터럽트 사용자가 키보드를 입력하고 마우스를 클릭하는 등의 동작이나 사건을 이벤트라고 한다. 이벤트가 발생하면 CPU에게 이벤트 발생을 알리는데, 이벤트 발생을 알리는 것을 인터럽트(Interrupt)라고 부른다. 인터럽트는 '방해하다’라는 뜻인데, 컴퓨터 용어에서는 신호를 보.. 2022. 1. 16.
운영체제의 개념과 역할, 구조 참고 Operating System Concepts 10th Edition https://en.wikipedia.org/wiki/Terminal_(macOS) 운영체제 강의(KOCW 양희재 교수님) 컴퓨터 시스템은 크게 CPU, 메모리, 하드 디스크로 구성되어 있다고 볼 수 있다. 이 각각의 하드웨어를 연결했다고 해서 우리가 원하는 프로그램을 수행할 수 있는 것은 아니다. 이 컴퓨터라는 하드웨어에서 사용자가 프로그램들을 사용하려면 하드웨어와의 원활한 소통 수단(인터페이스)이 필요했다. 이를 위해 등장한 것이 운영체제다. 운영체제 의미와 커널 운영체제는 컴퓨터의 하드웨어를 관리하고, 하드웨어/사용자/소프트웨어를 매개하는 시스템 소프트웨어이다. 커널(Kernel)은 사전적인 의미인 '단단한 껍질 안의 씨앗'.. 2022. 1. 14.
컴퓨터 동작 원리: BIOS와 부트 로더 참고: 운영체제(KOCW 양희재 교수님) 컴퓨터의 메모리 계층 구조를 공부하기 전에 컴퓨터가 동작하는 원리를 먼저 이해해야 속이 편한다. https://bentist.tistory.com/62 컴퓨터 구조와 메모리 계층 구조(Memory hierarchy) 참고: 위키피디아, https://www.samsungsemiconstory.com 메인보드 컴퓨터 내에서 기본 회로와 부품들을 담고 있는 가장 기본적이고 물리적인 하드웨어이다. 마더보드(mother board) 또는 주기판이라고도 한 bentist.tistory.com 1. 컴퓨터가 처음에 켜지면? 컴퓨터가 켜지자마자 메인보드에 내장된 부품인 ROM을 자동으로 읽어서 해야 할 일들을 하나씩 수행한다. 그래서 가장 먼저 ROM에 기본으로 설치되어 있는.. 2022. 1. 13.
컴퓨터 구조와 메모리 계층 구조(Memory hierarchy) 참고: 위키피디아, https://www.samsungsemiconstory.com 메인보드 컴퓨터 내에서 기본 회로와 부품들을 담고 있는 가장 기본적이고 물리적인 하드웨어이다. 마더보드(mother board) 또는 주기판이라고도 한다. 메인보드의 구성에는 CPU 소켓, 메모리 슬롯, 칩셋, 그리고 각종 확장카드 슬롯 및 저장장치 포트 등이 있다. CPU와 프로세서, 코어, 스레드 컴퓨터를 뇌에 비유하면 단기기억 담당은 RAM, 장기기억은 하드디스크, CPU는 사고를 담당하는 대뇌피질이다. 대뇌피질 없이 인간의 사고가 성립하지 않듯이 컴퓨터도 CPU 없이는 그냥 전기 먹는 기계가 된다. 1. CPU 트랜지스터라고하는 반도체를 이용해서 만들어진 CPU는 수십억개의 트랜지스터를 통해 전기 신호를 1(켜짐).. 2022. 1. 12.
합병 정렬(merge sort) 모두를 위한 컴퓨터 과학(데이비드말란 교수님) 강의 1.1. 합병 정렬 합병 정렬(병합 정렬)은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가는 정렬을 하는 방식이다. 분할 정복(divide and conquer) 알고리즘의 하나로 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다 1.2. 합병 정렬 구현 1) 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. n개의 원소가 있을 때 배열을 계속해서 반으로 나누기 때문에 호출되는 함수의 개수는 log N개 2) 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 다시 분할한다. 3) 결합(Combine): 정렬.. 2022. 1. 12.
재귀(Recursion)와 스택(stack)영역 다른 알고리즘과는 다르게 제목에 재귀와 함께 스택 영역을 적어놓은 이유가 있다. 재귀 함수를 호출하는 것과 메모리 스택 영역의 연관성은 마지막 부분에 정리하겠다. 1.1 재귀(Recursion) * 위키피디아 정의 컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 프로그래밍에서는 함수가 자기 자신의 함수를 호출하도록 구현한다. 보통 알고리즘을 구현할 때, 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 더 직관적이고 이해하기 쉬운 경우가 많다. 재귀는 마치.. 무의식 속의 무의식으로 들어갔다가 결국 현실로 되돌아오는 인셉션과 비슷하다. 용어만으로는 헷갈리니 파이썬 코드로 알아보자. def recursion(): print("난 재귀 함수야") recursion() .. 2022. 1. 9.
버블 정렬(bubble sort) 참고: 누구나 자료 구조와 알고리즘(개정2판) 4장, 모두를 위한 컴퓨터 과학(데이비드말란 교수님) 강의 정렬 알고리즘 시각화 사이트 https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html 4.1. 버블 정렬 이번 4장에서는 현실적인 문제를 푸는 코드를 작성해보고, 빅 오를 사용해 작성한 알고리즘을 평가해보겠다. 정렬 알고리즘은 컴퓨터 과학 분야에서 폭넓게 연구된 주제이며, 이러한 알고리즘은 모두 다음 문제를 해결한다. 정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까? 4장과 5장에서는 이런 정렬 알고리즘을 많이 다룰 것이다. 매우 기본적인 정렬 알고리즘인 버블 정렬부터 알아본다. 버블 정렬은 두 인접한 원소의 대소.. 2022. 1. 9.
선택 정렬(selection sort) 참고: 누구나 자료 구조와 알고리즘 2장, 모두를 위한 컴퓨터 과학(하버드 데이비드말란 교수님) 강의 1.1. 선택 정렬 정렬을 위한 알고리즘 중 선택 정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 선택해놓은 다음, 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다. 선택 정렬은 버블 정렬처럼 쌍을 이뤄 앞/뒤 순서를 교환하지 않는다. 매번 가장 작은 값을 선택해놓는 것이 목표다. 즉, 반복할 때마다 가장 작은 수를 선택하는 것이다. 버블 정렬은 인접한 두 원소를 비교할 때마다 교환이 발생하지만, 선택 정렬은 교환 횟수를 최소화한다. 1.2. 선택 정렬 구현 1부터 N개의 원소가 있다고 하자. (인덱스 번호로는 0번째부터 N-1번째에 원소가 있는 것) for .. 2022. 1. 8.

티스토리툴바