투투

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 접근 이진 검색 트리는 루트 노드를 기준으로 루트 노드보다 작으면 왼쪽 서브트리로 크다면 오른쪽 서브트리에 저장한다. 이때 전위 순회의 결과가 주어진다고할 때 후위 순회의 결과를 출력해야 한다. 전위 순회이기 때문에 루트 노드를 먼저 방문하게 된다. 따라서 맨 처음 나오게 되는 숫자가 루트 노드에 저장된 수이다. 이제 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나누면 될 ..

트리에서 최소 공통 조상이 무엇이며 이를 구하기 위한 기본적인 방법과 메모리를 사용하여 시간 복잡도를 개선한 알고리즘을 알아보자. 최소 공통 조상(Lowest Common Ancestor) 최소 공통 조상은 두 노드의 공통된 조상 중에서 가장 가까운 조상을 의미한다. 아래의 트리를 통해 9번 노드와 11번 노드의 LCA를 알아보자. 9번 노드의 부모 노드는 4 -> 2 -> 1이며 11번 노드의 부모 노드는 5 -> 2 -> 1이다. 이때 2와 1은 두 노드의 공통 조상이된다. 이처럼 두 개의 노드에서 공통 조상이 될 수 있는 노드는 여러 개일 수 있으며 여기서 레벨이 가장 높은(두 개의 노드에서 가장 가까운)노드가 최소 공통 조상이 된다. LCA 알고리즘 Ⅰ 기본적인 LCA 알고리즘의 개념은 다음과 같..

퀵 정렬은 합병 정렬과 같이 분할 정복 알고리즘을 적용한 정렬 기법이며 평균적으로 매우 빠른 속도를 갖고있다. 또한 정렬 대상에 동일한 키 값이 존재할 경우 키 값의 순서가 바뀌는 불안정 정렬이다. 개념 퀵 정렬은 피벗(pivot)을 설정하여 피벗을 기준으로 작은 값은 피벗의 왼쪽으로 큰 값은 피벗의 오른쪽으로 이동시킨다. 아래에 정렬할 대상이 있다. 여기서는 가장 앞에 있는 값을 피벗으로 설정해보자. [3, 1, 10, 6, 4, 7, 8, 2, 5, 9] 그렇다면 3이 피벗이되고 3을 기준으로 작은 값은 왼쪽으로 큰 값으 오른쪽으로 이동시키면 아래와 같은 결과를 갖는다. [1, 2] < [3] < [10, 6, 4, 7, 8, 5, 9] 위와 같이 분리가 되었다면 왼쪽은 왼쪽끼리 오른쪽은 오른쪽끼리 ..

정렬을 위한 알고리즘은 다양하다. 따라서 각각의 상황에 맞는 정렬 알고리즘을 적절히 사용해야 한다. 이번에는 내림차순으로 정렬된 수들을 다시 오름차순으로 정렬하기 위해서는 어떠한 기법이 효율적이며 왜 그런 것인지 알아보려고 한다. 잘못된 내용은 댓글에 적어주시면 감사하겠습니다. 아래처럼 10부터 내림차순으로 정렬되어 있는 것을 오름차순으로 정렬하려고 한다. 어떻게 하는 것이 가장 효율적인 방법일지 생각해보자. [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 빈번한 교환은 비효율적 정렬을 할 때 두 수를 비교하여 두 수의 위치를 변경하는 횟수가 많을수록 비효율적인 알고리즘이 된다. 두 수를 교환하기 위해서는 임시 변수를 생성해야 하고 A를 임시 변수에 저장하고 A에 B를 저장 후에 B에 임시 변수..

국제 표준화 기구(ISO)에서 소프트웨어 품질 평가를 위해 소프트웨어 품질 평가 통합 모델인 ISO25000을 제정하였다. 그렇다면 소프트웨어의 품질이 무엇이고 품질 평가가 왜 필요한지 알아보자. 또한 품질 평가를 하기위한 몇 가지 항목들을 자세히 알아본다. 소프트웨어 품질이란 소프트웨어 품질에 대한 개념은 사람마다 의견이 다르다. 또한 소프트웨어의 품질을 정량적으로 평가하기는 어렵다. 하지만 IEEE(전기 전자 기술자 협회)는 소프트웨어 품질에 대해 다음과 같이 정의하고 있다. 기능명세서의 적절한 구현성 등 주어진 요구사항을 만족시킬 수 있는 SW의 총체적인 특징과 제품의 특성들 SW가 요구하는 특성이나 속성들을 융합할 수 있는 SW 프로세스 정도 SW가 고객의 기대에 만족해야 하며 이를 사용자나 고객..

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 접근 다음 칸으로 이동했을 때 해당 칸의 모래의 양은 없어지고 미리 정해진 위치로 비율만큼 흩어지게 된다. 그리고 방향에 따라 특정 위치의 비율도 달라진다. 따라서 미리 방향에 따라 특정 위치로 이동했을 때의 비율을 저장해둔 후에 사용하도록 하였다. 아래와 같이 현재 위치와 방향을 기준으로 흩어지는 모래의 비율을 저장하였다. 행의 번호는 현재 방향을 가리키고 있는 ..

가중치가 있는 간선으로 연결된 트리에서 지름을 알아보자. 이를 통해 트리의 특징들을 더 깊게 이해할 수 있을 것이다. 트리의 지름을 알아보기 위해 백준 1967 트리의 지름 문제를 참고하였다. 트리의 지름이란 트리는 N개의 노드로 이루어졌을 때 N-1개의 간선으로 연결되기 때문에 순환되지 않는 구조를 갖고있다. 따라서 노드 A에서 노드 B로 이동하는 경로를 하나밖에 없다. 이때 두 개의 노드를 양쪽으로 잡아당겼을 때 가장 길게 늘어나는 경우가 생기며 특정 원 안에 트리가 들어온다. 여기서 생긴 원의 지름을 트리의 지름이라고 한다. 트리의 지름 구하기 그렇다면 트리의 간선들에 가중치가 있을 때 트리의 지름을 어떻게 구할 수 있을까? 아래의 트리를 보면 트리의 지름을 구성하는 두 개의 노드는 9번 노드와 1..

트리의 속성을 완벽히 이해하기 위해 트리와 관련된 여러가지 문제들을 풀어보자. 이번에는 백준 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를 정리해보려고 한다. 토큰 기반 인증 토큰 기반 인증은 로그인을 시도했을 때 서버에서 가입된 사용자인지 확인 후에 이미 가입된 사용자일 경우 사용자에게 토큰을 발급한다. 이때 토큰은 클라이언트측에서 관리를 하며 로그인이 필요한 서비스를 이용할 때 토큰을 함께 보내어 인증을 시도한다. 세션 기반 인증의 문제점 토큰 기반 인증을 사용하게 된 이유를 기존의 세션 기반 인증의 문제점에서 찾아보자. 기본적으로 세션 기반 인증은 서버가 클라이언트에 대한 정보를 메모리/디스크/데이터베이스 등에 저장하여 세션을 유지한..