KRAFTON JUNGLE/JUNGLE TIL

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..

BST(Binary Search Tree) 이진 탐색 트리1. 모든 노드의 왼쪽 서브트리 = 해당 노드의 값보다 작은 값을 가짐    모든 노드의 오른쪽 서브트리 = 해당 노드의 값보다 큰 값들만 가짐2. 자녀 노드는 최대 2개까지 가질 수 있다. 만약 자녀 노드를 3개 갖고 싶다면! B트리트리를 가지는 형식이 BST와 유사하면서 최대로 가질 수 있는 자녀 개수를 결정할 수 있다. → BST를 일반화한 Tree 라고도 함. ✨ 자녀 노드의 수 늘리기      1️⃣ 부모 노드에 하나 이상 저장      2️⃣ 부모 노드의 key들을 오름차순으로 정렬      3️⃣ 정렬된 순서에 따라 자녀 노드들의 키 값의 범위가 결정됨. B-Tree 주요 Parameter▶️ internal 노드의 key 수가 x 개..

포인터 산술포인터는 배열의 원소를 가리킬 수 있다.int a[10];int* p; p가 a[0]를 가리키게 만들어 줄 수 있다.p = &a[0]; a[0]에 5라는 값을 저장하고 싶으면 다음과 같이 해주면 된다.*p = 5; p에 포인터 산술(pointer arithmetic) 혹은 주소 산술(address arithmetic)을 사용하게 되면 a의 다른 원소들에 접근 할 수 있게 된다! C는 세 가지의 포인터 산술을 지원한다.* 포인터에 정수 더하기* 포인터에 정수 빼기* 포인터에 다른 포인터 빼기 포인터에 정수 더하기int a[10];int* p;int* q;int i;  포인터에서 정수 빼기 포인터끼리 빼기포인터끼리의 뺄셈의 결과는 포인터간의(배열 원소끼리의) 거리이다. 그러므로 p는 a[i]를 가..

⚠️원서 내용을 한국어로 정리 해본거라, 약간의 직역이 있을 수 있습니다ㅠㅠ ⚠️ 포인터 변수(Pointer Variable)주 메모리는 바이트 단위로 구성되어 있다.각각의 bytes들은 8개의 bits(비트)로 이루어져 있다. 실행 가능한 프로그램(executable program)은 code(코드)와 data(변수들)로 이루어져있다.code : 기계 단위 명령data: 변수프로그램의 모든 변수들은 메모리에서 한 개 이상의 바이트를 차지한다.포인터 변수의 정의주소를 숫자로 표현해주기는 하지만 그 값은 정수와는 다르다! 일반적인 정수형 변수에 저장할 수 없다.따라서 특수한 포인터 변수 pointer variable에는 저장해줄 수 있다. 포인터 변수 선언int *p;int* p; /* 역자: 포인터..

Knapsack Problem배낭의 최대 용량이 W일 떄, 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법. - i 번째 보석이 배낭의 한도보다 무거우면 안되므로, i번째 보석을 뺀 i-1개의 보석들을 가지고 구한 전단계의 최적값을 그대로 가지고 온다.- 그렇지 않은 경우 , i번째 보석을 위해 i번째 보석 만큼의 무게를 비웠을 때, 최적 값에 i번째 보석의 가격을 더한 값 or i-1개의 보석들을 가지고 구한 전단계의 최적값 중 큰걸 선택한다.  12865. 평범한 배낭https://www.acmicpc.net/problem/12865import sysinput = sys.stdin.readline# 물품의 수, 배낭의 최대 무게N, K = map(int, input().spli..

Dynamic Programming(DP)동적 프로그래밍정의 : 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘. ex) 피보나치 수열1️⃣ 재귀로 풀 때💡 재귀로 푼 다면 메모리 사용이 많이 커지고 같은 값을 중복으로 구하는 연산이 포함되어 있을 수 있어서 비효율적이다.def fibo(n): if n 2️⃣ DP를 사용했을 때    -1- Top Down 방식( Memorization) : 재귀재귀를 사용하지만 배열에 값을 저장해두기때문에 한번 구한 값은 다시 구하지 않아도 된다.def fibo(n, memo): if n     -2- Bottom Up  방식: for문O(1) 의 시간복잡도로 최종 값을 구할 수 있다.def fibo(N): if n  이 처..

다익스트라다익스트라 알고리즘: 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘* 음수인 가중치를 가진 간선이 있다면 사용할 수 없다. 구현1. 자기 자신과의 거리는 0이므로 ① 번 인덱스의 값은 0으로 둔다.2. ①번 정점에서는 ②, ③ ,④ 번 정점으로만 갈 수 있는데, 최단거리 테이블에 3,2,5를 일단 써놓는다. (확정은 아님!)최단 거리 테이블을 d라고 했을 때, d[2]~d[6] 까지 최솟값을 찾아서 최단거리를 확정한다. 3. ③ 번 정점의 거리를 확정한 후 , 최단거리 테이블을 갱신한다.① 번 정점에서의 간선은 이미 확인 했기 때문에 ③ 번 정점에서 뻗어나가는 간선만 본다.①②③ 4. 가장 가까운 정점을 찾기 위해 d[2],d[4],~d[6] 확인. 5. 확정된 ④에서의 ..

신장 트리1. 모든 정점을 포함한 서브 그래프2. 트리의 성질 : 무방향이면서 사이틀이 없는 그래프3. 주어진 그래프의 정점이 V개일 때, 신장 트리는 V-1개4. 주어진 그래프가 연결 그래프일때만 신장 트리가 존재 최소 신장 트리주어진 방향성이 없는 그래프의 부분 그래프(Subgraph) 들 중에서 모든 정점을 포함하는 트리 부분 그래프 : 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 그래프① 가운데 정점이 연결 되지 않음②,③ 사이클 존재 → 신장 트리가 아님④ 원래 그래프에 없던 간선 증가 → 부분 그래프 X 크루스칼 알고리즘1. 간선을 크기의 오름차순으로 정렬. 제일 낮은 비용의 간선을 선택한다.2. 현재 선택한 간선이 정점 u,v 를 연결하는 간선이라 할 때 만약 u와 v가 같은..

위상 정렬Topological Sort 정의 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬✨ 사이클이 존재하지 않는 방향 그래프에서만 잘 정의된다.           DAG(Directed Acyclic Graph) 구현 1. 제일 앞에 오려면 자신보다 앞에 있는 정점이 하나도 없어야 한다.= 자신에게 들어오는 정점이 없어야 한다.( indegree = 0 )  2. A를 위상정렬에 추가한 이후로는 A에서 다른 정점으로 나가는 간선이 의미가 없다.→ A와 A에서 뻗어 나가는 간선을 모두 지운다.  3. 그래프에서 제일 앞에 위치 할 수 있는 정점. → 자신에게 들어오는 간선이 없는 정점 = C, G 4. 정점 C에서 뻗어나가는 간선 삭제. 제일 앞에 위치할 수 있는 ..

드디어!!! 1주차가 끝났다아아~먼가 빨리 지나간 것 같은데, 1주일동안 한 공부양을 보면 빨리 지나간건 또 아닌듯.아침에 시험봐서 그런가 걍 개개ㅐㄱ 오늘 개개개 무기력했음. 집이었다면 게임하다 잤겟지..하지만??여기서는 그럴수가 없다~ 해야지 뭐 어떡해~해시 정의와 성질해시 자료구조 : 키에 대응되는 값을 저장하는 자료구조insert, erase, find, update → O(N) 해시 함수: 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수* 이상적인 상황 → O(1), 충돌이 빈번한 경우 성능 저하, 최악의 상황 → O(N)각 키의 해시 값이 최대한 균등하게 퍼져야 성능이 좋아지기 때문에 좋은 해시 함수를 정해야 함! 충돌서로 다른 키가 같은 해시 값을 가진 경우 충돌이 일어난다. 충..

장마철이라 매일 같이 비오다가 오랜만에 정말 맑은 하늘이 떴다. 오랜만에 광합성이라 매우 좋았다. 그거와 별개로 오늘 Week 1 마지막 날이었는데. 정말 많은 일이 있었던 것 같다. 이렇게 집중해서 많은 양의 코딩 테스트를 한적이 거의 없었는데, 짧은 일주일동안 몰입해서 열심히 공부한 것 같다. 비록 모든 과제를 완료하진 못했지만, 80퍼 이상 한 것에 의의를 두고 있다~이분 탐색정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법 주의 사항1. 이분 탐색을 하려고 한다면 주어진 배열이 정렬되어 있어야 한다.2. 무한 루프에 빠지지 않게 mid 값을 정해야 한다.

오늘은 일기를 생략하겠다 너무 졸립다..안뇽Quick Sort 퀵 솔트는 매 단계마다 Pivot이라는 이름이 붙은 원소 하나를 차례로 보내는 정렬법이다.  장점1. 추가적인 공간이 필요하지 않다.2. 배열 안에서의 자리 바꿈으로 처리한다. → Cache Hit 비율이 높다! (속도가 빠르다)In Place Sort원소위치를 잘 바꿔주면 되기 떄문에 추가적인 공간이 필요 없다.  정렬 과정 시간 복잡도 평균 : O(N LgN)최악: O(N^2) Quick Sort VS Merge Sort Merge SortQuick Sort시간복잡도O(NlgN)평균 O(NlogN)최악 O(N^2)평균적으로 Merge Sort 보다 빠르다.추가적으로 필요한 공간(overhead)O(N)O(1)Stable Sort 여부OX