투투

중위 순회와 후위 순회의 결과를 알 때 전위 순회의 결과를 구해보려고 한다. 이는 백준 2263 트리의 순회 문제이다. 해당 문제는 트리 순회의 특징을 정확히 이해하고 있는지 판단하기 좋은 문제라고 생각한다. 이와 비슷하게 전위 순회와 중위 순회를 알 때 후위 순회를 구할 수 있지만 전위 순회와 후위 순회를 알 때 중위 순회는 구할 수 없다. 접근 아래와 같은 트리가 있다고 해보자. 이 트리를 중위 순회, 후위 순회로 탐색하면 다음과 같은 순서일 것이다. 중위 순회 : 4 -> 2 -> 5 -> 1 -> 3 -> 6 후위 순회 : 4 -> 5 -> 2 -> 6 -> 3 -> 1 후위 순회는 루트 노드를 가장 마지막에 방문하기 때문에 후위 순회 결과 중 가장 마지막 노드인 1이 루트 노드라는 것을 확인할 ..

삽입정렬은 원소가 자신의 자리를 찾고 해당 자리에 삽입되면서 정렬하는 기법이다. 숫자 카드를 손에 들고 있을 때 숫자들을 오름차순으로 정렬한다고 생각해보면 쉽게 연상할 수 있다. 개념 오름차순 기준으로 설명한다. N개의 원소가 있을 때 1번 인덱스의 원소부터 N-1번 인덱스의 원소까지 탐색을 진행한다. 현재 인덱스를 기준으로 이전 인덱스와 비교를 한다. 만약 이전 인덱스가 더 크다면 현재 인덱스의 원소가 있어야하는 자리는 이전 인덱스이기 때문에 자리를 스왑한다. 스왑 후에도 이전 인덱스가 더 크다면 계속해서 자리를 스왑한다. 이 과정에서 이전 인덱스가 더 작거나 더 이상 비교할 원소가 없을 때는 비교를 종료한다. 위의 과정을 반복하면 정렬이 된다. 구현 10개의 숫자가 랜덤하게 나열되어 있다. for문을..

선택 정렬은 오름차순 기준일 때 범위 내에서 최솟값을 찾아 앞자리의 숫자와 자리를 변경해 나간다. 최솟값 또는 최댓값을 선택한다는 의미로 선택 정렬이라는 이름이 붙었다. 개념 오름차순 기준으로 설명한다. N개의 원소가 있을 때 0~N-1까지 탐색을 진행하여 최솟값을 찾는다. 찾은 최솟값과 0번째 인덱스에 있는 숫자와 스왑을 한다. 위의 과정을 통해 첫 번째 자리는 정렬이 된 것이다. 이후 1~N-1까지 탐색을 진행하여 최솟값을 찾고 1번째 인덱스에 있는 숫자와 스왑을 한다. 위의 과정을 반복하여 정렬을 한다. 구현 10개의 숫자가 랜덤하게 나열되어 있다. 첫 번째 for문의 i인덱스는 최솟값을 찾아서 해당 인덱스와 i 인덱스와 자리를 변경할 때 사용된다. 두 번째 for문은 i인덱스부터 탐색을 진행한다...

HTTPS는 HTTP에 보안이 강화된 프로토콜이라는 것을 알고있다. 프로젝트를 진행하면서 SSL 인증서를 발급받아 HTTPS로 요청할 수 있도록 했던 경험도 있다. 하지만 정확히 HTTPS가 어떻게 동작하는지 알지 못했기 때문에 이번 기회에 HTTPS의 개념과 동작원리를 이해하려고 한다. HTTPS의 개념 HTTP는 TCP/IP 위의 애플리케이션 계층에서 사용되는 프로토콜이다. 여기서 HTTPS는 TCP/IP위에 SSL 또는 TLS를 통해 보안을 강화한 프로토콜이다. 이를 통해 모든 HTTP의 요청과 응답은 암호화된다. HTTPS 동작을 알아보기 전에 알아두어야 할 개념 HTTPS의 동작 원리를 알아보기 전에 대칭키, 공개키, CA(Certificate Authority)를 이해해야한다. 1. 대칭키 암..

이전에 HTTP의 기본 동작을 정리하였다. 이후에 프로젝트를 진행하면서 HTTP의 특성들을 알게 되었고 따로 정리를 해야 할 필요가 있다고 생각하였다. HTTP는 클라이언트-서버 구조를 갖고, Stateless, Connnectionless, 대부분의 파일 형식을 전송할 수 있다는 4가지의 특성이 있다. 클라이언트 - 서버 구조 HTTP는 클라이언트가 서버에 요청하는 단방향 통신이며 서버는 요청이 있을 때에만 응답하는 구조를 갖고 있다. 이때 서버는 요청한 것을 처리한 결과에 따라서 다른 응답을 보낸다. 예를 들어 특정 URL로 이동했을 때 해당 URL이 존재하지 않을 때는 404 응답을 보낸다. 또한 정상적으로 이동했을 때는 200 계열의 응답을 보내게 된다. Stateless HTTP는 상태를 저장하..

버블 정렬은 오름차순 기준일 때 인접한 두 개의 인접한 원소를 비교하여 더 큰 원소를 뒤로 보내는 방식을 취하고 있다. 두 개의 인접한 원소를 비교해 나가는 모습이 버블 같기 때문에 버블 정렬이라는 이름이 붙었다. 개념 오름차순 기준으로 설명한다. 첫 번째 원소와 두 번째 원소를 비교했을 때 첫 번째 원소가 크다면 두 번째 원소와 자리를 바꾼다. 이어서 두 번째 원소와 세 번째 원소를 비교한다. 위와 같은 과정을 거치면 마지막부터 가장 큰 원소들이 정렬될 것이다. 즉, N개의 원소가 있다고 가정했을 때 한 번의 순환을 통해 N번째 자리에 가장 큰 숫자가 저장되고 이제 첫 번째 원소부터 N-1까지의 수들을 비교하여 N-1번째 자리를 채운다. 구현 10개의 숫자가 나열되어 있다고 가정한다. 2중 for문을 ..

어떠한 알고리즘을 작성했을 때 알고리즘의 성능은 어떻게 측정할 수 있을까? Big-O 표기법은 알고리즘의 수행 시간을 측정하여 성능을 표기하는 것이다. 그렇다면 Big-O 표기법을 사용하는 이유와 대략적으로 본인이 설계한 알고리즘의 시간 복잡도를 어떻게 구하는지 알아보자. Big-O를 사용하는 이유 알고리즘의 성능을 측정하기 위해서 Big-O, Big-Ω, Big-θ 를 사용할 수 있다. Big-Ω : 빅 오메가는 어떠한 알고리즘이 최적의 조건에서 실행될 때 사용할 수 있는 표기법이다. 예를 들어 이미 정렬되어 있는 숫자들에 퀵 정렬을 진행하면 N만큼의 시간 복잡도를 갖게되며 더 이상 빠르게 할 수 없을 것이다. 이처럼 알고리즘이 최선의 경우 수행되는 시간을 측정할 때 사용할 수 있다. Big-θ : 빅..

이번에는 트리를 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)의 구조를 갖고있다. 따라서 가장 먼저 들어온 데이터가 가장 먼저 반출된다. 이것은 식당에 손님들이 줄을 서는 것을 생각해보면 알 수 있다. 손님들이 식당 앞에 줄을 선 후에 입장할 때는 가장 먼저 온 손님 즉, 가장 앞에 있는 손님들이 먼저 식당에 입장한다. 스택과 큐는 어려운 개념이 아니다. 하지만 이러한 성질을 이해했을 때 ..