투투

프로세스가 실행되기 위해서는 CPU, 메모리, 파일 등과 같은 여러가지 자원이 필요하다. 이 중 하나의 자원만 부족해도 프로세스가 실행되지 못한다. 따라서 운영체제는 이러한 자원을 관리하여 프로세스에게 적절히 배분해줘야 한다. 이때 교착상태가 일어나는데 교착상태의 개념과 교착상태의 원인, 해결법을 알아보자. 교착상태란? 입구가 두 개이고 한 명만 지나갈 수 있는 골목이 있다. 이 때 양쪽의 입구에서 사람들이 골목을 지나가려고 한다. 하지만 서로 반대편 사람이 먼저 지나가는 것을 기다리고 있어 아무도 골목을 들어서지 못하고 있다. 이처럼 두 개 이상의 서로 다른 프로세스가 다른 프로세스의 작업이 끝나기만을 기다리고 있어 어떠한 프로세스도 완료되지 못하는 것을 교착상태라 한다. 프로세스 A와 B가 있을 때 ..

이진 트리는 루트 노드를 기준으로 두 개의 서브트리로 나뉘어 진다. 또한 서브트리도 최대 두 개의 서브트리로 나뉘어지는 것을 이진 트리라 한다. 이진 탐색 트리는 정해진 규칙에 의해 이진 트리의 노드에 데이터를 저장하는 기법이다. 이진 탐색 트리를 통해 데이터를 저장하면 원하는 데이터를 찾을 때 효율적으로 찾을 수 있다. 이진 탐색 트리의 원리 이진 탐색 트리는 정해진 규칙에 따라 이진 트리에 데이터를 저장한 트리이다. 아래는 이진 탐색 트리를 가장 잘 표현한 것 같아서 첨부한다. 루트 노드를 기준으로 큰 값이 들어오면 오른쪽으로, 작은 값이 들어온다면 왼쪽으로 보내진다. 이를 통해 루트 노드를 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값이 저장된다. 이제 데이터를 찾아야 한다면 아래와 같은 과정을 거치게..

프림과 크루스칼 알고리즘은 최소 신장 트리를 구하는 대표적인 알고리즘이다. 먼저 최소 신장 트리가 무엇인지 알아본 후에 유니온 파인드를 적용시킨 크루스칼 알고리즘을 알아본다. 최소 신장 트리 N개의 노드로 이루어진 그래프가 있다. 이 그래프에는 다양한 부분 그래프가 존재할 수 있다. 이때 부분 그래프를 신장 트리라하며 N개의 노드글 N-1개의 간선으로 연결하고 순환되지 않는 구조를 가져야만 신장 트리라 할 수 있다. 이러한 신장 트리 중에서 연결하는데 가장 적은 비용이 드는 신장 트리를 최소 신장 트리라 한다. 개념 크루스칼 알고리즘은 유니온 파인드와 그리디 알고리즘의 개념을 활용하였다. 먼저 신장 트리가 되기 위해서는 N-1개의 간선으로 N개의 노드를 연결해야 하며 순환되지 않는 구조를 가져야 한다. ..

React에는 useState, useEffect와 같은 Hook이 존재한다. Hook은 기존 클래스형 컴포넌트에서의 상태관리와 Life Cycle Method를 가볍게 사용할 수 있게 도와주며 로직의 재사용이 가능하도록 하였다. 또한 반복되는 로직을 자신만의 Hook을 만들어 구현하면 복잡함을 줄일 수 있다. Custom Hook의 장점 자신만의 Hook을 만드는 것이 어떠한 장점이 있는지 알면 알맞게 사용할 수 있을 것이다. 먼저 Custom Hook을 사용한 사례를 통해 필요성과 장점을 알아본 후에 특징을 살펴보자. 아래는 React로 간단한 로그인 폼을 작성한 것이다. 이제 아이디와 비밀번호에 대한 유효성 검사를 위한 로직을 구성해보자. function Login() { return ( 아이디: ..

운영체제는 커널 모드와 사용자 모드로 나뉘어 운영된다. 프로그램에서 파일 읽기, 파일 쓰기 등은 커널 모드를 통해 동작한다. 이때 시스템 콜은 커널 영역의 기능을 사용자 모드에서 사용할 수 있도록 한다. 시스템 콜의 개념과 동작 과정을 알아보자. 개념 시스템 콜은 응용 프로그램에서 커널이 제공하는 기능을 사용하기 위한 인터페이스다. 이를 통해 프로세스가 하드웨어에 직접 접근하여 디스크에 저장되어 있는 파일을 읽는 등의 기능을 수행할 수 있다. 프로그램은 고유의 주소를 갖고 있으며 함수 호출이 발생하면 해당 주소 내에서 접근하여 함수를 실행할 수 있다. 하지만 프로그램의 주소를 벗어난 공간에 접근하기 위해서는(커널 영역) 시스템 콜을 사용할 수 있다. 시스템 콜의 동작 과정 프로그램에서 디스크에 저장되어 ..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 접근 사이클이 완성되기 위해서는 최소 세 개의 점이 연결되어야 한다. 이를 유니온 파인드 알고리즘을 활용하여 해결할 수 있다. 입력되는 두 개의 점이 있을 때 한 쪽 점을 다른 쪽에 속한 집합으로 합친다. 이후에 두 개의 점을 입력받았을 때 루트 노드가 같다면 사이클이 완성되었다고 판단할 수 있다. 구현 - 아래와 같이 union와 find 연산을 함수로 만든다. def find(a): if..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 접근 이번 문제에는 상어들의 step 크기가 최대 1000이다. 따라서 최대 RxC 마리의 상어들의 모두 1000의 크기만큼 이동할 때 한 칸씩 이동하도록 구현하면 시간초과가 발생한다. 따라서 상어들의 step 크기를 줄여야했다. 이를 위해 규칙을 찾아보면 상하로 움직이는 상어들은 (R-1) x 2배, 좌우로 움직이는 상어들은 (C - 1) x 2배일 때 같은 자리로 돌아오게 ..

서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 즉 {1, 2}와 {3, 4}는 서로소 집합이지만 {1, 2}와 {2, 4}는 서로소 집합이 아니다. 이러한 서로소 집합을 구할 때 유니온 파인드 알고리즘을 사용할 수 있다. 유니온 파인드의 개념을 알아보고 코드를 통해 구현해보자. 또한 유니온 파인드 알고리즘을 활용한 또 다른 알고리즘을 소개한다. 개념 유니온 파인드 알고리즘은 서로소 집합을 찾기위해 사용되는 알고리즘이다. 유니온 파인드는 Find과 Union라고 불리는 두 가지 연산으로 이루어져 있다. Find: 원소 x가 어느 집합에 포함되어 있는지 찾는다. Union: 원소 x가 포함된 집합과 원소 y가 포함된 집합을 합친다. 위의 연산을 통해 그래프 내에서 부분집합을 쉽게 구할 수 있다. 이제..

스택을 활용하여 후위표기법을 구현할 수 있다. 후위표기법의 개념과 스택으로 후위표기법을 구현해보자. 후위표기법이란? 우리가 일반적으로 알고있는 5+3x2와 같은 수식은 중위 표기법으로 작성된 것이다. 이를 후위표기법으로 변환하면 532x+가 된다. 먼저 중위 표기법으로 작성된 수식을 후위 표기법으로 변환하는 방법과 후위 표기법으로 표현된 수식을 계산하는 방법을 알아보자. 후위 표기법으로 변환 5+3x2라는 수식을 보자. 숫자가 나오면 바로 옮겨 적는다. "x" 또는 "÷"가 나오면 나온 순서대로 다른 곳에 기록해둔다. "+" 또는 "-"가 나오면 다른 곳에 기록해둔 "x"와 "÷"를 늦게 적은 순서대로 후위 표기식에 옮겨 적는다. 모두 옮겨 적었다면 "+" 또는 "-"를 다른 곳에 기록해둔다. 모두 적었..

합병 정렬은 분할 정복 알고리즘을 활용한 정렬 방법이다. 먼저 원소들을 반으로 나누고 두 개의 부분 배열을 비교하여 정렬된 상태로 만들어 가는 것이다. 개념 오름차순 기준으로 설명한다. N개의 원소가 있을 때 N//2를 기준으로 원소들을 반으로 나눈 값을 인덱스로 하고 위에서 구한 인덱스를 기준으로 리스트를 반으로 나눈다. 반으로 나눈 리스트를 또 다시 반으로 나누고 리스트 원소의 개수가 1일 때 해당 원소를 반환한다. 이렇게 반으로 나눈 원소들을 합쳐 나간다. 초기에 1개의 원소들로 이루어진 리스트를 비교하여 정렬 후에 2개의 원소를 갖는 리스트로 만든다. 이후에는 2개의 원소를 갖는 리스트끼리 비교하여 정렬하여 4개의 원소를 갖는 리스트로 만든다. 위의 과정을 반복하는 것이 합병 정렬이다. 구현 me..