KRAFTON JUNGLE

유튭 강의를 하나 슥 볼랬는데 바킹독님 마지막 강의가 트라이였다.내 최애 남잔데, 그의 최애 알고리즘이 트라이라 그래서 호감도 급 상승..렛츠 기릿.. 진심으로 바킹독님..넘 멋지다..트라이( Trie )문자를 효율적으로 처리하기 위한 트리 자료구조 ✅ 장점 : 단어의 저장 개수와 무관하게 삽입,탐색, 삭제가 O(|S|)의 시간 복잡도를 가진다.✅ 단점 : 메모리를 많이 차지한다. 트리의 정점의 index를 기록해야해서 int의 4바이트* |S| 만큼 메모리를 더 사용한다.다른 자료구조와 비교!이진 검색 트리 : 삽입, 탐색, 삭제가 O(logN) 이지만, 문자열을 검색할 경우 단어의 길이 S 만큼 대조를 해야하기 때문에,최악의 경우 O( S *  logN ) 이 걸린다.해시 : 삽입, 탐색, 삭제가 O..

정글 중반기에 들어가면서,, 할게 너무 많고 블로그에 "정리"를 하는거 자체도 힘들어서.. 공부하면서 노션에다 기록했더니 TIL을 안쓰는 사람처럼 보여버렸다..수료를 하고나서~ 좀 쉬다가!!정글 콤파스 보면서 놓쳤던 부분들 복습하는 중인데, 여기다가 정리를 해보려구 한다.나름 복습할 때 도움이 많이 되었다! 키키✅ 보이어 - 무어를 공부하기 전에....1. 부르투 포스 알고리즘2. KMP 알고리즘 에 대해 먼저 공부하는 것을 추천 ! Boyer - Moore algorithm( 보이어 무어 알고리즘 )문자열 검색에 사용되는 알고리즘이다.불필요한 것을 건너뛰고. 검색을 빠르게 하는 것이 주 목표.워드 검색 기능에서 사용된다. 보이어-무어 알고리즘은 보통 상황에서 문자열은 앞부분보다는뒷부분에서 불일치가 일어..

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; /* 역자: 포인터..

지금까지는 인스트럭션들이 하나씩 순차적으로 실행되는 직선적인 코드 동작만을 다루어왔다. C의 일부 구문인 반복문, 스위치문들은 데이터에 적용된 실험 결과에 따라 일련의 연산이 실행되는 조건부 실행이 요구된다. 기계어 코드에서는 조건부 동작을 구현하기 위해 두 개의 기본적인 낮은 수준의 방법을 제공한다. 데이터 값을 실험해서 이 시험 결과에 따라 데이터흐름이나 제어흐름을 변경한다. C와 기계여 코드의 인스트럭션들은 모두 프로그램에 나타나는 순서대로 순차적으로 실행된다.하지만 기계어 인스트럭션들의 실행 순서는 점프Jump 인스트럭션으로 변경할 수 있다. 조건형 연산을 구현하는 두가지 방법3.6.1 조건 코드CPU = 정수 레지스터 + 단일비트 조건 코드로 구성된 레지스터 운영 조건부 분기를 수행하기 위해서 ..

1.5 캐시가 중요하다시스템은 정보를 한 곳에서 다른 한 곳으로 이동시키는 일에 많은 시간을 보낸다.1. hello 프로그램의 기계어 인스트럭션들( 하드디스크 저장 ) → 로딩 시 메인 메모리로 복사2. 프로세스가 프로그램을 실행할 때 인스트럭션들: 메인 메모리 →  프로세서로 복사여러 복사과정들이 프로그램의  "실제 작업"을 느리게 하는 Over Head   - 시스템의 디스크 드라이브는 메인 메모리보다 1000배 더 크기가 크지만, 프로세서가 디스크에서 1워드의 데이터를 읽을 때 걸리는 시간은 메모리에서보다 천만 배 더 오래 걸릴 수 있다.- 레지스터 파일은 수백 바이트의 정보를 저장하는 반면, 메인 메모리는 십억 개의 바이트를 저장한다.- 그러나 프로세서는 레지스터 파일의 데이터를 읽는데 메모리보다..

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가 같은..