본문 바로가기

알고리즘4

[알고리즘] Big O #1 Big O Big O는 코드가 얼마나 효율적으로 실행되는지 수학적으로 비교하는 방법. 동일한 작동을 하는 코드 A와 코드 B가 있다고 생각해 보자. 코드 A는 15초 동안 실행되고, 코드 B는 1분 동안 실행 된다면, 우리는 코드 A가 더 낫다고 생각할 것이다. 이것이 시간 복잡도이다. 하지만, 시간 복잡도는 시간으로 측정하지 않는다. 무슨 소리예요, 방금 15초와 1분을 비교했잖아요? 하실 것이다. 왜냐면 방금 시간을 측정한 컴퓨터보다 성능이 더 좋은 컴퓨터로 B코드를 실행하면 15초보다 빠르게 실행될 수도 있기 때문이다. 따라서, 무언가를 완료하는 데 걸리는 작업 수로 측정하는 것이 더욱 정확하다. 시간 복잡도 외에도 공간 복잡도를 측정해야 한다. 코드 A는 매우 빠르게 실행되지만 상대적으로 실.. 2023. 3. 16.
[WEEK 05] 크래프톤 정글 1기 WIL - Weekly I Learned 크래프톤 정글에서의 일주일간 성장일지입니다. 매주 주말 업데이트 예정이며, 앞으로도 잘 부탁드립니다. WIL은 에세이 형태로 진행되며 기술적인 내용이 전무합니다. 결국 나중에는 아무것도 아닙니다, [WEEK01~04] 컴퓨팅 사고로의 전환 과정이 끝났다. 각 주차별 '키워드'는 다음과 같다. WEEK01 : 정수론, 배열, 문자열, 재귀 함수, 정렬, 완전 탐색, 시간 복잡도 WEEK02 : 이분 탐색, 분할 정복, 스택, 큐, 우선순위 큐 WEEK03 : 그래프(vertex, edge, node, arc), BFS, DFS, 위상 정렬 WEEK04 : 동적 프로그래밍, 그리디 알고리즘 매주마다, 매일같이 벽을 만났다. 가끔 그 벽을 깨기도 했지만 , 대부분의 벽.. 2022. 11. 29.
[알고리즘] RB Tree삭제 동작 원리 #2 한국외대 '신찬수' 교수님과 '쉬운 코드'님의 강의 자료를 참고하였습니다. 개념을 공부하고, 시뮬레이터를 활용하여 노드의 동작 원리를 이해한다. 하단의 링크는 rbtree visualization을 확인할 수 있는 링크이다. 참고하여 학습을 진행한다. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html Red/Black Tree Visualization www.cs.usfca.edu #1 레드 블랙 트리 삭제 방식 0. 삭제 전 RB 트리 속성 만족한 상태 1. 삭제 방식은 일반적인 BST와 동일 2. 삭제 후 RB 트리 속성 위반 여부 확인 - 어떻게 확인할 수 있는가 3. RB트리 속성을 위반했다면 재조정 4. RB 트리 속성을 다시 만족 RB.. 2022. 11. 26.
[알고리즘] RB Tree개념과 삽입 동작 원리 #1 한국외대 '신찬수' 교수님과 '쉬운 코드'님의 강의 자료를 참고하였습니다. 개념을 공부하고, 시뮬레이터를 활용하여 노드의 동작 원리를 이해한다. 하단의 링크는 rbtree visualization을 확인할 수 있는 링크이다. 참고하여 학습을 진행한다. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html Red/Black Tree Visualization www.cs.usfca.edu #1 레드블랙 트리 기본 개념과 특징 1. 레드블랙 트리 개념 1. 이진 탐색 트리(BST)의 한 종류 2. 스스로 균형 잡는 트리 3. BST의 worst case의 단점을 개선 : worst case = 한 방향으로 편향된 이진탐색 트리 > O(N) 4. 모든 노드.. 2022. 11. 26.