![]()
인터럽트(Interrupt)인터럽트는 프로그램을 실행하는 도중에 예기치 않은 상황이 발생할 경우 현재 실행 중인 작업을 일시 중단하고, 발생된 상황을 우선 처리한 후 실행 중이던 작업으로 복귀하여 계속 처리하는 것을 말한다.즉, 인터럽트는 어떤 신호가 들어왔을 때 CPU를 잠깐 정지시키고 다른 작업을 처리한다.인터럽트가 발생되면 인터럽트 핸들러 함수가 모여 있는 인터럽트 벡터로 가서 인터럽트 핸들러 함수가 실행된다. 인터럽트가 필요한 이유선점형 스케줄링 알고리즘을 보면 어떤 프로세스가 Running 상태에서 다른 프로세스로 교체하기 위해 스케줄러가 작업을 중단시키게 된다.프로세스가 스스로 결정하는 것은 진행 중에 I/O 장치 혹은 다른 작업을 진행해야 해서 Block 상태가 되는 것과 프로세스가 종료되서..
![]()
해시(Hash)해시는 데이터를 다루는 기법 중 하나로 검색과 저장을 아주 빠르게 하는 자료구조이다.데이터를 저장할 때 키-값 형태로 데이터가 존재하고 키 값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어난다.해시 자료구조는 데이터를 키-값 형태로 저장해 준다고 했는데 그러기 위해서 키 값을 고정된 길이의 값으로 바꿔주는 해시 함수와 해싱이라는 과정 그리고 키-값 데이터를 저장해 주는 해시 테이블을 이해해야 한다. 해시 함수(Hash Function)와 해싱(Hashing)해시 함수라고 불리는 것으로 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 알고리즘이다.해시 함수는 키 값을 고정된 길이의 hash로 변환하는 역할을 한다. 그림과 같이 사람의 이름을 해시 함수를 거쳐서 ..
완전 탐색 알고리즘완전 탐색 알고리즘은 모든 경우의 수를 시도하는 기법으로 가장 기본적이고 간단한 유형의 알고리즘이다.될 수 있는 모든 조건 혹은 모든 조합을 다 대입해보며 해답을 찾는 알고리즘이다.모든 경우의 수를 전부 탐색하기 때문에 100% 정확성을 보장하지만 반대로 높은 시간 복잡도를 가진다. 완전 탐색 알고리즘에는 선형 구조와 비선형 구조로 나눌 수 있다.선형 구조브루트 포스모든 경우의 수를 다 검사하여 원하는 값을 탐색하는 방법경우의 수가 적을 때 사용하는 것이 좋다.비트마스크이진수의 비트 연산을 통해 경우의 수를 줄여가며 탐색하는 방법비트 마스크를 사용하여 하나의 변수에 여러 개의 상태 정보를 저장할 수 있으며 이를 통해 복잡한 조건문을 간단하게 처리할 수 있다. 경우의 수가 많을 경우에 유..
![]()
힙(Heap)힙은 완전 이진트리의 일종으로 부모 노드와 자식 노드 간에 특정한 조건을 만족하는 자료구조이다.이진 트리에 대해서 잘 모른다면 밑의 글을 읽고 나서 힙을 공부해 보자. 자료구조 - 이진 트리(Binary Tree)이진 트리(Binary Tree)이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리를 뜻한다.트리 영역에서 가장 많이 사용되는 형태로 트리를 1차원 배열로 표현해준다. 이진 트리의hotechstory.tistory.com 힙의 특징힙 자료구조에는 여러 가지 특징이 있는데 하나씩 살펴보자.1. 힙은 완전 이진트리다. 즉, 왼쪽에서 오른쪽으로 채워지는 마지막 수준을 제외하고 트리의 모든 수준이 완전히 채워진다. 이 속성은 트리가 배열을 사용하여 효율적으로 표현되도록..
![]()
레드/블랙 트리(Red/Black Tree)레드/블랙 트리는 균형을 유지하기 위해 일련의 규칙을 사용하는 자가 균형 이진 탐색 트리의 유형으로 트리의 초기 모양에 관계없이 삽입, 삭제, 검색과 같은 작업에 대한 O(log n) 시간 복잡도를 보장한다.레드/블랙 트리는 각 수정 후 트리를 조정하기 위해 간단한 색상 코딩 체계를 사용하여 자체 균형을 유지한다.레드/블랙 트리는 각 노드가 빨간색 또는 검은색일 수 있는 색상이라는 추가 속성을 갖는 자체 균형 이진 탐색 트리이다.삽입 및 삭제 중에 균형을 유지하여 효율적인 데이터 검색 및 조작을 보장한다. 레드 블랙 트리의 속성레드/블랙 트리에는 여러 가지 속성들이 있는데 이러한 속성들을 알아야 동작 과정을 이해할 수 있다.어떤 속성들이 있는지 하나씩 살펴보자...
![]()
대규모 데이터 처리에 대한 내 생각최근에 취업을 준비하며 여러 채용 공고를 확인해 보면 많은 회사들이 대용량 트래픽이나 데이터를 처리해 본 경험이 있는 사람들을 우대하고 있다.내가 근사한 서비스를 만들어서 많은 사람들이 사용하거나, 서비스 기업에 취업하지 않고서는 그러한 경험을 한다는 게 쉽지 않은 부분이다.직접 경험해보지는 못하지만 다른 사람들의 경험을 간접적으로나마 느껴보고 공부해보면 그나마 괜찮지 않을까 생각이 든다.대규모 데이터를 어떻게 처리해야 될지를 고민하기에 앞서 대규모가 어느 정도인지를 파악해야 한다.조금 부끄러운 얘기지만 이번에 수료한 부트캠프를 다니기 전까지 대규모 데이터라고 하면 수 GB ~ 수십 GB 정도 될 줄 알았다. 물론 잘 모르는 내 입장에서는 저 정도 크기의 데이터도 되게 ..
알고리즘알고리즘을 공부하면 정말 여러 가지 알고리즘이 있다는 것을 느끼게 된다.나 또한 최근에 계속 알고리즘을 공부하며 코테 문제를 풀고 있는데 하면 할수록 알고리즘의 본래 목적과 멀어지고 그냥 문제를 푸는 용도로만 쓰고 있었다.코테 문제를 푸는 것도 중요하지만 그보다 알고리즘을 왜 사용하고, 배워야되는지가 더 중요하다고 생각했다. 알고리즘이란 뭘까?알고리즘의 사전적 정의를 먼저 보면 아래와 같다.알고리즘은 어떤 값 또는 값의 집합을 입력으로 하고 어떤 값 또는 값의 집합을 출력으로 하는 명확하게 정의된 계산 절차사전적 정의를 보면 코딩 테스트에서 사용하는 알고리즘이랑 의미가 같다고 생각할 수 있다.하지만 잘 생각해보면 어떤 웹 서비스를 개발한다고 했을 때 API 호출을 통해서 어떤 요청이 들어오고 DB..
![]()
AVL 트리 AVL 트리는 모든 노드의 왼쪽 및 오른쪽 하위 트리 높이 차이가 1보다 클 수 없는 이진 탐색트리로 자체 균형 이진 탐색 트리라고도 한다. 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이를 노드의 균형 요소(BF, Balance Factor)라고 하는데 이러한 균형 요소를 가지고 트리의 균형을 확인하여 노드를 적절한 곳으로 재배치해준다. 그렇다면 그냥 이진 탐색 트리를 사용하면 되지 굳이 AVL 트리를 사용하는 이유가 뭘까? 일단 이진 탐색 트리는 루트 노드를 중심으로 들어오는 데이터가 큰지, 작은 지를 판별해 데이터를 삽입하게 된다. 이진 탐색 트리의 특징은 효율적으로 탐색, 삽입, 삭제를 할 수 있는데 데이터를 삽입하고 삭제하는 것은 결국 탐색이 먼저 이루어져야 하므로 이진..
![]()
우선순위 큐(Priority Queue) 우선순위 큐는 우선순위에 따라 값을 정렬하는 큐의 유형이다. 우선순위 큐 생성하기 PriorityQueue queue = new PriorityQueue(); PriorityQueue queue = new PriorityQueue(Collections.reverseOrder()); PriorityQueue를 생성하는 것을 살펴보면 두 가지 경우가 있다. 첫 번째로 우선순위 큐를 기본으로 생성하게 되면 우선순위가 낮은 값이 Queue의 맨 앞에 위치하게 된다. 두 번째로 Collections 클래스에 reverseOrder() 메서드를 사용하면 우선순위가 높은 값부터 맨 앞에 위치하게 된다는 차이가 있다. 우선순위 큐에 데이터 삽입하기 queue.add(1); qu..
![]()
싱글톤(Singleton) 먼저 디자인 패턴은 객체를 생성하는데 총 3가지 분류로 나눌 수 있는데 생성, 구조, 행위로 나눌 수 있고 여기서 싱글톤은 객체를 생성하는 디자인 패턴 중 하나이다. 싱글톤 패턴의 주요 특징은 단 하나의 유일한 객체를 만드는 것이다. 이렇게 만들어진 하나의 객체를 다른 모듈들이 공유하며 사용하게 된다. 모듈 A, B, C가 어떤 작업을 하는데 필요한 객체를 생성한다고 생각해 보자. 그렇다면 위의 그림과 같이 각 모듈마다 새로운 객체를 생성하게 된다. 다르게 생각해보면 모듈이 100까지 있고 100개 다 동일한 기능의 객체가 필요하다면 100개의 객체를 새롭게 생성해 줘야 될 것이다. 그렇게 생성된 100개의 객체는 메모리를 차지하게 되므로 메모리 공간 낭비가 발생하게 된다. 여..
![]()
Git과 GitHub 우리가 개발한 서비스의 규모가 커지면 그에 따른 코드의 양도 방대해지고, 추가와 수정 혹은 변경과 같은 작업들이 계속 이루어지게 된다. 이러한 작업들을 형상관리라고 하는데 Git이라는 것은 형상관리를 쉽게 할 수 있게 도와주는 프로그램이다. 우리가 위의 사진과 같이 프로젝트를 진행했다면 어땠을까? 어떤 것이 최종 결과물인지 모르고, 또 내가 필요한 코드가 어디에 있는지 모른다. (실제 경험담이 있음...) 만약 Git을 사용했으면 하나의 폴더 안에서 계속 작업물의 버전을 높여가면서 작업을 할 수 있을 것이다. Git을 사용해서 작업이 끝나면 그것을 GitHub에 공유하여 여러 사람들이 볼 수 있게 할 수 있고, 또한 동료들과의 협업도 가능하다. Git과 GitHub의 특징들 Git은..
CPU 스케줄링 알고리즘CPU 스케줄링 알고리즘은 프로그램이 실행될 때 어떤 프로그램에 CPU 소유권을 줄 것인지 결정한다.CPU가 유후 상태가 될 때마다 운영 체제에서 준비 큐에 있는 프로세스 중 하나를 선택해서 실행하게 되는데 이때 CPU 스케줄러에 의해서 실행된다.CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다. CPU 스케줄링 알고리즘의 목표CPU 활용도를 최대 수준으로 유지한다.모든 프로세스에 CPU를 공정하게 할당한다.단위 시간당 실행을 완료하는 프로세스 수가 최대여야 한다.프로세스가 완료하는 데 걸리는 시간이 최소여야 한다.프로세스가 준비 큐에서 대기하는 시간이 최소여야 한다.프로세스가 응답을 생성하는 시간이 짧아야 한다. CPU..
![]()
프로세스(Process)프로세스(Process)는 컴퓨터에서 실행되고 있는 프로그램을 말하며 CPU 스케줄링의 대상이 되는 작업이라는 용어와 거의 같은 의미로 쓰인다.프로그램프로세스어떤 작업을 하기 위해 실행할 수 있는 파일실행되어 작업중인 컴퓨터 프로그램파일이 저장 장치에 있지만 메모리에 올라가 있지 않은 정적인 상태메모리에 적재되고 CPU 자원을 할당받아서 프로그램이 실행되고 있는 상태컴파일러가 컴파일 과정을 거쳐 컴퓨터가 이해할 수 있는 기계어로 번역되어 실행될 수 있는 파일실행 파일을 실행하여 작업 중인 프로그램 프로세스와 컴파일 과정앞서 설명했던 것과 같이 프로세스는 프로그램을 실행한 것인데, 예를 들어 프로그램은 구글 크롬 프로그램과 같은 실행 파일이며, 이를 두 번 클릭하면 구글 크롬 프로세..
![]()
메모리(Memory)메모리는 일시적 또는 장기간 데이터를 저장하는 디지털 시스템이다.CPU는 그저 메모리에 올라와 있는 프로그램의 명령어들을 실행할 뿐이기 때문에 데이터와 명령어를 저장하기 위해서는 메모리가 가장 중요한 부분이다. 메모리 계층메모리 계층은 레지스터, 캐시, 메모리, 저장장치로 구성되어 있다.메모리 계층 구조는 컴퓨터에서 사용 가능한 메모리를 최적화하는 데 도움이 되므로 컴퓨터 메모리에서 가장 필요한 것 중에 하나이다.메모리에는 여러 수준이 있으며 각 수준은 크기, 비용 등이 다르다. 계층 위로 갈수록 비용이 높고 속도가 빠르며 아래로 갈수록 용량은 커지지만 속도가 낮은 대신 가격이 저렴해진다.간단히 표로 정리하면 아래와 같다.분류휘발성속도용량CPU 레지스터O가장 빠름가장 적은 용량캐시(..
![]()
운영 체제(Operating System)운영 체제는 사용자가 컴퓨터를 쉽게 다루게 해주는 인터페이스로 한정된 메모리나 시스템 자원을 효율적으로 분배해 준다.운영체제는 컴퓨터에서 항상 실행되는 하나의 프로그램이고, 다른 모든 프로그램은 응용 프로그램이라고 한다.우리가 컴퓨터를 직접 사용한다고 하면 상당히 어려운 일이 될 것이다. 또한 컴퓨터를 최대한 잘 활용한다는 것도 어려운 일이 될 것이다.이처럼 직접적으로 사용하기 어려운 컴퓨터를 보다 쉽게 사용할 수 있도록 사용자 친화적으로 제공하는 것이 바로 운영체제이다.그럼 우리가 운영체제를 통해서 컴퓨터를 맘대로 조작할 수 있게 되는데 우리가 원래 해야 했던 어려운 작업들을 운영체제가 대신해주게 된다.운영체제가 없었을 때 사용자가 직접 컴퓨터는 사용해야 하는데..
