농담곰담곰이의곰담농
공지사항
-
크래프톤 정글 6기 교육생이 되었슴다.
Today I Learn
-
크래프톤 정글 6기 TIL - Day 20| RB Tree 크래프톤 정글 6기 TIL - Day 20| RB Tree
Red-Black Tree- 이진 탐색 트리(BST)의 한 종류- 스스로 균형(balancing) 잡는 트리- BST의 Worst Case의 단점을 개선- 모든 노드는 Red or Black Red Black tree의 속성1. 모든 노드는 red 또는 black이다.2. 루트 노드는 black이다3 모든 nil 노드는 black이다.4. 노드가 red인 자녀들은 black이다.5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black의 수는 같다.( 자기 자신은 카운트에서 제외 )💡nill 노드란? - 존재하지 않음을 의미하는 노드 - 자녀가 없을 때 자녀를 nil 노드로 표기 - 값이 있는 노드와 동등하게 취급 - RB 트리에서 leaf 노드는 nil 노드 노드 X의 blac.. -
크래프톤 정글 6기 TIL - Day 19 | B 트리 크래프톤 정글 6기 TIL - Day 19 | B 트리
BST(Binary Search Tree) 이진 탐색 트리1. 모든 노드의 왼쪽 서브트리 = 해당 노드의 값보다 작은 값을 가짐 모든 노드의 오른쪽 서브트리 = 해당 노드의 값보다 큰 값들만 가짐2. 자녀 노드는 최대 2개까지 가질 수 있다. 만약 자녀 노드를 3개 갖고 싶다면! B트리트리를 가지는 형식이 BST와 유사하면서 최대로 가질 수 있는 자녀 개수를 결정할 수 있다. → BST를 일반화한 Tree 라고도 함. ✨ 자녀 노드의 수 늘리기 1️⃣ 부모 노드에 하나 이상 저장 2️⃣ 부모 노드의 key들을 오름차순으로 정렬 3️⃣ 정렬된 순서에 따라 자녀 노드들의 키 값의 범위가 결정됨. B-Tree 주요 Parameter▶️ internal 노드의 key 수가 x 개..
Coding Test
-
10844 쉬운 계단 수 10844 쉬운 계단 수
https://www.acmicpc.net/status?user_id=yuu_ta&problem_id=10844&from_mine=1 ✔ 유형 : DP✔ 문제 풀이: 일의 자리 수에 어떤 수가 오느냐에 따라 경우의 수가 달라짐을 알고, 점화식을 세워 배열을 채워나간다. 코드import sysinput = sys.stdin.readlineMOD = 1000000000N = int(input())# 1 = 2: for i in range(2, N+1): DP[i][0] = DP[i-1][1] % MOD for j in range(1, 9): DP[i][j] = (DP[i-1][j-1] + DP[i-1][j+1]) % MOD .. -
11053 가장 긴 증가하는 부분의 수열 11053 가장 긴 증가하는 부분의 수열
https://www.acmicpc.net/problem/11053✔ 유형 : DP(LIS)✔ 문제 풀이: LIS(Longest Increase Sequence) 의 로직과 비슷하다. DP[i] 를 i 번째 까지 가장 긴 증가하는 부분 수열의 개수라고 정의했을 때. i보다 앞쪽에 있는 원소들과 비교해서 i번째의 수보다 작을 때 개수를 업데이트 한다. 정리하자면,DP[i] : 현재까지 계산된 i위치에서의 LIS의 길이DP[j] + 1 : j위치까지 LIS에 현재 원소를 추가한 길이 그리고 D[i] 는 위의 두 경우의 수 중 최대값으로 업데이트 해주어야한다. 따라서, "현재 원소를 이전 LIS 에 추가했을 때 더 긴 LIS가 되는가?"를 조건을 생각해주면 되는것이다. 코드import sysinput = s.. -
2156 포도주 시식 2156 포도주 시식
https://www.acmicpc.net/problem/2156✔ 유형 : DP✔ 문제 풀이: 점화식을 세우는 접근방식은 다음과 같다 1. 맨 마지막 포도주를 무조건 선택한다 했을 때, 연속 두개를 선택하고 싶다면, arr[i] ( 마지막 포도주 ) , arr[i-1]( 마지막에서 두번째 포도주), 그리고 3개를 연속해서 선택할 수 없으므로arr[i-2]는 선택하지 않는다. 2. 맨 마지막 포도주를 무조건 선택하고, 그 전 포도주는 선택하지 않을 때,arr[i] ( 마지막 포도주 )를 선택하고, arr[i-1]는 선택하지 않는다. 3. 맨 마지막 포도주를 절대 선택하지 않을 때DP[i-1] 포도주의 개수가 N-1때의 최대값을 반영하면 된다. 이를 일반화 하면DP[i]는 세가지의 경우의 수로 일반화 하.. -
1464 1로 만들기 1464 1로 만들기
https://www.acmicpc.net/problem/1463 ✔ 유형 : DP✔ 문제 풀이: 정수에 사용할 수 있는 연산은 총 3가지인데, 빠르게 1을 만들려면 세가지 연산을 시행했을 때 값이 가장 작아야 한다.X라는 수를 1로 만들으려 했을 때,위 세가지 연산을 시행하면 우선 1번의 연산을 한 것이 된다. DP[X] = 정수 X에 연산을 시행했을 때 1이 되는 최소 연산 수행 횟수라고 정의할 때 다음과 같이 문제를 작게 나눌 수 있다.DP[X] = 1 + DP[X에 세가지 연산중 하나로 실행한 결과]와 같게 된다. 따라서 X에 세 가지 연산을 실행한 결과 값 중 가장 작은 값을 반영해서최소 연산 횟수를 저장해 나갈 수 있다. 다시 정리해보면 아래 점화식을 세울 수 있다. 코드import sysN .. -
1923 연속합 1923 연속합
✔ 유형 : DP✔ 문제 풀이: 코드import sysimport copyinput = sys.stdin.readlineN = int(input())arr = list(map(int, input().split()))DP = copy.deepcopy(arr)for i in range(1, N): DP[i] = max(DP[i]+DP[i-1], arr[i]) #resultprint(max(DP))