풀스택챌린지

이번에는 트리를 Python으로 표현하는 것과 순회하는 방법에 대해 알아보도록 한다. 트리의 표현 Python 리스트를 통해 아래의 트리를 표현해보려고 한다. 아래의 코드를 보면 2차원 리스트를 생성한 것을 알 수 있는데 -1은 비어있음을 의미하고 각각 왼쪽 자식 노드와 오른쪽 자식 노드를 의미한다. N = 6 tree = [[-1, -1] for _ in range(N)] 이제 각각의 노드에 왼쪽 자식 노드와 오른쪽 자식 노드를 입력받는다. 비어있을 때는 -1을 입력하도록 하였다. 각각 입력받은 것을 해당 노드의 0번 인덱스(왼쪽 자식 노드)와 1번 인덱스(오른쪽 자식 노드)에 저장한다. for i in range(N): left, right = map(int, input().split()) tree[..

트리는 계층적 구조를 표현하는데 적합한 자료구조이다. 또한 트리로 표현한 후에 데이터들을 탐색했을 때 효율적인 문제들이 존재한다. 따라서 이번에는 트리의 기본적인 구조를 알아보도록 한다. 트리의 기본 [그림 1]은 트리를 나타낸 것이다. 트리는 노드들이 간선으로 연결되어 있으며 마치 나무를 뒤집어 놓은 듯한 느낌을 받을 수 있다. 트리는 그래프의 한 종류라고 할 수 있다. 하지만 그래프와 달리 순환되는 구조를 갖고있지 않다. 왜냐하면 트리는 N개의 노드와 N-1개의 간선으로 이루어져 있기 때문에 하나의 노드를 시작으로 탐색을 진행했을 때 다시 처음 위치로 돌아오지 못한다. 트리를 구성하는 용어들 트리의 구조를 파악하는 사용되는 용어들이 존재한다. 루트 노드 : 노드 A처럼 트리에서 최상위에 존재하는 노드..

스택 스택은 후입선출(Last In First Out)의 구조를 갖고있다. 따라서 가장 늦게 들어온 데이터가 가장 먼저 반출된다. 이는 상자를 아래에서 위로 하나씩 쌓아올리는 것으로 생각할 수 있다. 상자를 쌓아올린 뒤에 상자를 다른 곳에 옮길 때 중간이나 처음이 아닌 가장 위에있는 상자를 먼저 들어서 옮기는 것이 효율적이다. 큐 큐는 선입선출(First In First Out)의 구조를 갖고있다. 따라서 가장 먼저 들어온 데이터가 가장 먼저 반출된다. 이것은 식당에 손님들이 줄을 서는 것을 생각해보면 알 수 있다. 손님들이 식당 앞에 줄을 선 후에 입장할 때는 가장 먼저 온 손님 즉, 가장 앞에 있는 손님들이 먼저 식당에 입장한다. 스택과 큐는 어려운 개념이 아니다. 하지만 이러한 성질을 이해했을 때 ..

우리는 PC를 이용해 웹 서핑을 하고 동시에 음악을 들으며 친구한테 메시지를 보낸다. 우리는 이러한 일들이 동시에 일어나고 있다고 느낀다. 하지만 실제로 굉장히 빠른 시간에 프로세스들이 교체되어 실행되는 것이다. 이때 운영체제가 현재 실행되고 있는 프로세스들을 관리하여 실행을 유지할 수 있는 정보들이 저장된 자료구조를 PCB(Process Control Block)이라고 한다. PCB의 구성요소 프로세스를 할당하거나 프로세스가 교체되었을 때 지금까지 수행된 내용을 기록하기 위해서는 PCB 내의 여러가지 요소들이 사용된다. PCB의 구성요소를 파악한다면 하나의 CPU에서 어떻게 여러 개의 프로세스가 실행될 수 있는지 파악할 수 있을 것이다. 프로세스 상태 : CPU를 할당해도 되는지 결정하기 위해 필요하며..

먼저 프로세스에 대해서 공부를 했었다. 프로그램은 파일이 메모리에 올라가 있지 않고 디스크에 저장되어 있는 상태이며 프로그램을 실행시켰을 때 메모리에 올라가서 프로세스가 생성이 된다. 그렇다면 스레드는 무엇이고 어떻게 동작을 하는 것일까? 스레드가 생겨난 이유 스레드라는 개념이 생기기 전에는 프로그램이 시작되고 끝나기 전까지 하나의 프로세스를 사용하였다. 하지만 점점 프로세스가 복잡해졌고 하나의 프로세스로 프로그램을 실행시킬 수 없었다. 그렇다고 프로세스를 여러 개 사용할 수도 없다. 왜냐하면 운영체제는 안정적인 운영을 위해 프로세스에게 할당한 메모리 내에서만 활동할 수 있도록 하였기 때문이다. 즉 하나의 프로그램에 여러 개의 프로세스를 사용하더라도 프로세스끼리 정보가 공유되지 않기 때문에 오류가 발생한..

※ 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.  Array와 Linked List가 무엇인지 안다면 그 차이는 쉽게 알 수 있을 것이다. Array배열은 특정 크기만큼 연속된 메모리 공간에 데이터를 저장하는 자료구조이다. 만약 int형 데이터 3개를 저장할 수 있는 배열을 생각해보자. 그렇다면 아래의 그림처럼 연속된 공간에 메모리를 확보하여 데이터를 이곳에 저장할 수 있게 된다.위의 그림에서 볼 수 있듯이 연속된 공간에 데이터들이 나열되어 있기 때문에 처음 주소만 알면 다른 위치도 쉽게 알 수 있을 것이다. 따라서 배열은 랜덤으로 접근하는 것이 가능하다. 그렇다면 어떻게 랜덤으로 접근하는 것이 가능할까? C언어로 예를 들어보면 배열을 선언했을 때 배열의 주소는..

오늘은 Hash Table라는 자료구조에서 충돌이 발생하는 이유와 충돌이 발생하지 않도록 하기 위해서는 어떻게 해야 하는지 알아본다. 먼저 Hash Table은 저장되는 데이터가 (key, value)처럼 하나의 쌍을 이루는 자료구조를 말한다. 이때 key가 존재하지 않는 value는 저장할 수 없으며 key가 중복되어서는 안 된다. 해쉬 함수 학생들의 정보를 Hash Table에 저장하려고 한다. 이때 학생들의 학번을 key로 하는데, 학번이 2020103과 같은 형태로 되어있어서 배열의 크기를 이에 맞춰서 선언해야하며 배열을 생성하더라도 쓰지 않는 공간이 많기 때문에 효율적이지 못하다. 따라서 학번을 해쉬 함수로 전달하여 반환된 값을 key로 설정하려고 한다. 해쉬 함수는 다음과 같다. 학번을 입력하..

프로세스의 개념 프로세스는 실행 중인 프로그램을 뜻한다. 그렇다면 프로그램은 무엇일까? 프로그램은 아직 실행하기 전 상태의 실행 파일들을 의미한다. 바탕 화면에 있는 각각의 파일들이 프로그램이 되며 더블 클릭을 했을 때 프로그램이 실행 된다. 이때 프로그램이 실행 되면 CPU 메모리를 점유하게 되고 프로세스가 진행되는 것이다. 그렇다면 프로세스를 구성하는 것이 무엇인지 알아보자. Code 영역 : 프로그램의 코드가 올라가고 프로그램을 실행 시켰을 때 실행 파일 내에 존재하는 명령어들이 올라가는 메모리 영역이다. Data 영역 : 전역 변수와 static 변수에 할당을 위한 메모리 영역이다. Heap 영역 : 개발자가 동적 할당할 때 필요한 메모리 영역이다. Stack 영역 : 함수 호출 및 함수의 인자와..

프록시 서버가 무엇일까? 프록시 서버는 클라이언트와 서버 사이의 중계역할을 한다. 클라이언트가 서버에 직접적으로 데이터를 요청하지않고 프록시 서버에 요청을 한다. 프록시 서버는 클라이언트의 요청을 서버에 전달한 후에 받은 데이터를 클라이언트에 전달한다. 프록시는 포워드 프록시, 리버스 프록시가 존재한다. 이는 프록시 서버를 어디에 위치시키느냐에 따라 달라지는데 클라이언트 측에 위치시키는 것을 포워드 프록시, 서버 측에 위치시키는 것을 리버스 프록시라고 한다. 포워드 프록시는 아래의 그림처럼 표현할 수 있으며 일반적으로 포워드 프록시를 프록시라고 한다. 브라우저에서 구글검색을 하면 프록시 서버에서 데이터를 받아 서버에 요청 후에 값을 돌려준다. 이러한 방식은 대역폭을 감소시키고 서버가 어떤 클라이언트가 요..

클라이언트의 요청이 많을수록 웹 서버의 부하가 높아지게된다. 이때 웹 서버가 어떻게 부하를 분산하는지 알아보자. 서버의 부하 분산 서버의 부하를 분산하기 위해 3대의 웹 서버를 사용한다고 해보자. 그렇다면 각각의 서버가 담당하는 패킷의 수가 감소할 것이다. 하지만 1대의 웹 서버가 동작하지 못하는 상황이 온다면 클라이언트들은 이러한 상황을 모르고 계속해서 액세스할 것이기 때문에 비효율적이다. 로드 밸런서 이때 웹 서버와 클라이언트 사이에 로드 밸런서를 둘 수 있다. 로드 밸런서는 클라이언트의 요청을 대신 받아 서버에 전달하는 역할을 하는데 DNS 서버에 로드 밸런서의 주소를 등록하여 사용한다. 따라서 클라이언트는 웹 서버가 아닌 로드 밸런서에 요청을 하고 로드 밸런서는 웹 서버에서 받은 요청을 클라이언트..