풀스택챌린지

트리의 속성을 완벽히 이해하기 위해 트리와 관련된 여러가지 문제들을 풀어보자. 이번에는 백준 11725 트리의 부모 찾기 문제를 통해 트리에서 루트 노드를 제외한 다른 노드의 부모 노드를 찾아보자. 접근 트리는 순환되지 않는 구조를 갖고있다. 그렇기 때문에 N개의 노드는 N-1개의 간선을 통해 트리를 구성할 수 있다. 만약 N-1개 보다 많은 간선을 갖는다면 순환되는 구조를 갖게된다. 이때 N-1개의 간선에 대한 정보(간선에 의해 연결된 두 개의 노드)가 입력으로 주어질 때 어떻게 저장하여 트리를 구현할 수 있을까? 이번에는 2차원 리스트를 활용하였다. a, b 노드를 입력받았을 때는 어떤 노드가 부모 노드이고 어떤 노드가 자식노드인지 알 수 없다. 따라서 a행의 리스트에 b를 추가하고 b행의 리스트에도..

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 접근 4개의 말로 10개의 턴이 진행된다. 주사위에 나오는 숫자는 미리 알고있다. 그렇다면 매 턴마다 어떤 말을 이동할지 선택해야 한다. 이를 비트시프트를 활용하여 모든 경우의 수를 구하여 말을 선택한다. 0부터 1

프로젝트에서 로그인을 구현할 때 JWT를 많이 사용했다. 시간이 지날수록 JWT를 사용했던 이유와 동작 원리를 잊게되었다. 따라서 이번에는 토큰 기반 인증의 원리와 이러한 인증의 방법 중의 하나인 JWT를 정리해보려고 한다. 토큰 기반 인증 토큰 기반 인증은 로그인을 시도했을 때 서버에서 가입된 사용자인지 확인 후에 이미 가입된 사용자일 경우 사용자에게 토큰을 발급한다. 이때 토큰은 클라이언트측에서 관리를 하며 로그인이 필요한 서비스를 이용할 때 토큰을 함께 보내어 인증을 시도한다. 세션 기반 인증의 문제점 토큰 기반 인증을 사용하게 된 이유를 기존의 세션 기반 인증의 문제점에서 찾아보자. 기본적으로 세션 기반 인증은 서버가 클라이언트에 대한 정보를 메모리/디스크/데이터베이스 등에 저장하여 세션을 유지한..

프로세스가 실행되기 위해서는 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로 간단한 로그인 폼을 작성한 것이다. 이제 아이디와 비밀번호에 대한 유효성 검..

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

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배일 때 같은 자리로 돌아오게 ..