[백준/Python] 15681. 트리와 쿼리

15681. 트리와 쿼리 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리 DFS DP 힌트에서 제공하는 트리의 특성 "트리는 단 하나의 사이클도 존재하지 않는 그래프" 따라서 루트가 정해지면, 특정 노드에 도달하는 최단 경로는 한 가지 뿐이다. "한 노드와만 연결되어 있는 모든 노드가 루트가 될 수 있다" 또한 루트가 정해지면 노드 간에 부모 자식 관계를 정의할 수 있다. "아무 정점이든 root로 잡아 subtree를 구성할 수 있다" 따라서..

• format_list_bulleted 개발 일지/알고리즘 문제풀이
• · 2021. 4. 25.
• textsms

[백준/Python] 4256. 트리

4256. 트리 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 트리 분할 정복 트리는 분할 가능한(큰 것을 작은 것으로 쪼갤 수 있는) 자료구조에 해당 따라서 트리의 탐색은 재귀+분할정복으로 이루어질 수 있다. 전체 트리의 루트는 3이지만, 루트 3을 기준으로 왼쪽/오른쪽으로 트리를 나누면 루트가 6, 7인 두 개의 subtree가 생긴다. 트리의 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)가 갖는 의미 전위 순회는 root, left child, ri..

• format_list_bulleted 개발 일지/알고리즘 문제풀이
• · 2021. 4. 24.
• textsms

[백준/Python] 1068. 트리

1068. 트리 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 그래프 탐색 트리 프로그래머스 코드 챌린지를 하다가 느낀 거지만 트리 유형에 약한 것 같아서 트리 문제들만 골라 풀어보기로 했다 😢 트리는 모든 노드가 한 개 이하의 출발점, 한 개 이하의 도착점만 갖는 단방향 그래프이다. 따라서 노드의 방문 여부(visited)를 체크하지 않아도 된다는 특이점이 있다. 아이디어 Python에서는 포인터를 이용한 linked list 구조로 tree를 구현하지 않기 때문에, 실제로 node(와의 연결)을 제..

• format_list_bulleted 개발 일지/알고리즘 문제풀이
• · 2021. 4. 22.
• textsms

[Algorithm] 백트래킹(Backtracking)

재귀 + 브루트포스 + "후보에서 탈락 시 해당 파트의 탐색 종료" 재귀 + 브루트포스가 DFS라면 (모든 조건을 다 탐색) 백트래킹은 모든 경우를 탐색하되 불가능한 후보임을 발견하면 해당 경우는 탐색을 종료한다. 시간 복잡도는 브루트포스와 동일하나 대부분의 경우에서 브루트포스보다 빠르게 동작한다. 후보에서 탈락 방문 중인 노드가 유망한지 체크하고, 유망하지 않다면 하위 트리를 가지치기한다. 종료 조건에 도달한 경우(마지막까지 유망한 경우의 수), 전역으로 선언된 결과값에 이를 반영한다. 구현 def check_node(node, target): global answer # 정답을 담을 변수는 함수 밖에서 관리 if not promising(node): # 방문 중인 노드가 유망하지 않다면 return ..

• format_list_bulleted 학습/Algorithm
• · 2021. 4. 6.
• textsms

[Algorithm] 에라토스테네스의 체

소수가 아닌 수를 모두 걸러내 소수 여부를 판별하는 알고리즘 소수 여부를 판별할 숫자만큼의 배열을 생성한다. number = 100 # 100까지의 숫자에 대한 소수 여부 판별 prime = [True] * (number+1) 0과 1은 소수가 아니므로 False 처리한다. prime[0] = prime[1] = False 2부터 시작해 해당 숫자가 소수인지 판별하고 소수라면 해당 숫자의 배수는 모두 소수가 아님(False) 처리한다. 소수가 아니라면 넘어간다(continue). for i in range(2, number+1): if not prime[i]: continue for j in range(i*2, number+1, i): prime[j] = False 이 과정을 거치고 나면 각 숫자에 대해..

• format_list_bulleted 학습/Algorithm
• · 2021. 4. 6.
• textsms

[passport] 1. passport-local

Passport란 무엇인가? Simple, unobtrusive authentication for Node.js 즉, node로 개발된 서버를 위한 인증 라이브러리이다. Passport는 다양한 인증 방식을 전략(Strategy)이라는 이름으로 제공한다. Passport는 말그대로 복잡한 인증 과정에서 복잡한 부분은 라이브러리에게 맡기고 개발자는 핵심 로직에 집중할 수 있도록 하기 위해 사용한다. 그러나 개발자는 이 복잡한 부분이 어떻게 수행되는지 정도는 알고 있어야 한다. 이 포스팅에서는 서버에서 직접 아이디와 비밀번호를 받아 처리하는 passport-local 방식을 이용해본다. passport-local passport-local은 사용자가 직접 입력한 아이디와 비밀번호로 인증을 수행한다. pass..

• format_list_bulleted 개발 일지/Server
• · 2021. 3. 16.
• textsms

[node.js] Bcrypt 모듈을 이용한 패스워드 암호화

암호화가 필요한 이유? 만약 암호화를 하지 않고 사용자의 입력을 그대로(이를 평문이라고 한다) 저장하게 되면, 데이터베이스가 유출되었을 때 사용자의 비밀번호가 제3자에게 노출되게 되며, 이는 심각한 피해를 가져올 수 있다. 따라서 이러한 피해를 방지하기 위하여, 사용자의 비밀번호는 암호화를 거쳐 저장되어야 한다. 이번 포스팅에서는 그 중에서도 강력한 해시 알고리즘으로 유명한 bcrypt 를 이용해본다. 암호화된 패스워드의 생성 우선 bcrypt 모듈을 설치한다. npm i bcrypt 프로젝트에 적용하기 위해, 암호화된 비밀번호를 생성하는 간단한 함수를 구현해보았다. import { genSalt, hash } from 'bcrypt'; const saltRound = 10; const createHas..

• format_list_bulleted 개발 일지/Server
• · 2021. 3. 16.
• textsms

[Algorithm] 다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍 (동적 계획법) 최적해를 구하기 위해 매우 많은 시공간이 필요한 경우 연산 결과를 저장하여 중복 연산을 방지함으로써 시공간 효율성을 높임 간단히 말하자면 한 문제를 무조건 한 번만 풀도록 결과를 저장해 사용한다는 것 언제 사용하는가 큰 문제를 작은 문제(큰 문제의 분할)로 나눌 수 있는 경우 작은 문제와 큰 문제의 해결 로직이 같아야 함 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일 해결 로직이 순수함수(동일 입력에 반드시 동일 출력이 보장)에 해당해야 함 어떻게 저장하는가 위 조건을 만족하는 문제들의 연산 결과들은 수열에 해당한다고 볼 수 있다. 수열은 규칙적으로 배열된 숫자들의 모임이기 때문에 배열(리스트)에 저장한다. 분할 정복 알고리즘과의 차이 분할 정복 알고리..

• format_list_bulleted 학습/Algorithm
• · 2021. 2. 23.
• textsms