[자료구조] Red-Black Tree

Red-Black Tree정의Self-balanced Binary Search Tree의 종류로 모든 노드가 빨간색과 검정색으로 표현 된다.노드에 대한 정의G : 조상 노드P : 부모 노드U : 삼촌 노드 (부모 노드의 형제)N : 새로 삽입한 노드 (자식)균형 유지의 조건모든 노드는 빨간색 또는 검은색이어야 한다루트 노드는 검은색이다모든 NIL은 검은색이다 (NIL: Null Leaf, 자료를 갖지 않고 트리의 끝을 나타내는 리프 노드)NIL 노드는 값이 있는 노드와 동등하게 취급한다빨간색 노드의 자식은 반드시 검은색이다임의의 노드에서 자손 NIL 노드까지 가는 경로의 black 수는 같다 (단, 자기 자신은 카운트 제외)노드 x의 Black height : x에서 임의의 자손 nil노드까지 내려가는 ..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 4. 24.

[알고리즘] 위상정렬

위상 정렬방향 그래프의 정점들을 "선후 관계(의존 관계)"에 따라 나열하는 정렬 방법이다.단, 위상 정렬은 비순환 방향 그래프(DAG : Directed Acyclic Graph)에서만 가능하다 만약 순환이 있다면, 어떤 노드도 “처리 순서를 앞에 둘 수 없기 때문에” 선형 정렬 자체가 불가하다.(진입 차수가 0이 될수 없는 구간이 존재하고, 그러면 각 정점은 우선순위가 없으며 위상 정렬을 통해 탐색 순서를 정의할 수 없다) 위상 정렬 예시 : 라면 끓이기DFS 기반 위상 정렬깊이 먼저 따라가서, 끝에서 역순으로 쌓는다사리 부수기 → 사리 넣기 → 물넣기스프넣기 → 물넣기끓이기 → 물넣기밥 준비하기 (독립)✔️ 결과 예시 (역후위 순회) :밥 준비하기 → 사리 넣기 → 사리 부수기 → 스프 넣기 → 끓이..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 4. 3.

[알고리즘] 그래프

파이썬의 그래프그래프 관계(relationship)을 표현하는 자료 구조로, 파이썬에서는 어떤 관계를 표현할때 적합한 것은 사전(dictionary)이다. 그래프는 인접 행렬, 인접 리스트로도 나타낼 수 있다.  키(key) : 노드값(value) : 키와 연결된 노드 리스트#무방향 그래프graph1 = {1:[2, 3, 5], 2:[1, 3], 3:[1, 2, 4], 4:[3, 5], 5:[1, 4]}#방향 그래프graph2 = {1:[2, 3], 2:[3], 3:[4], 4:[], 5:[1, 4]}리스트를 이용하여 그래프를 나타내 보자. 리스트의 인덱스가 사전의 key에 해당하고, 인덱스의 값은 사전의 값과 똑같다.#무방향 그래프graph1 = [[], [2, 3, 5], [1, 3], [1, 2, ..

• format_list_bulleted 카테고리 없음
• · 2025. 4. 3.

[알고리즘] 트리 구조

트리 구조루트 : 트리의 가장 위쪽에 있는 노드. 루트는 트리에 1개만 존재리프 : 가장 아래쪽에 있는 노드. aka 단말 노드 (terminal node), 외부 노드 (external node). 가지를 더 이상 뻗을 수 없다비단말 노드 (non-terminal node) : 리프를 제외한 노드. aka 내부 노드자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드를 자식이라 한다.부모 : 어떤 노드와 가지가 연결되었을 때 위쪽 노드를 부모라 한다형제 : 부모가 같은 노드를 형제라 한다조상 : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드를 조상이라 한다자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드를 자손이라 한다레벨 : 루트에서 얼마나 멀리 떨어져 있는지. 루트의 ..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 4. 3.

[크래프톤정글] 정글에서의 생활

정글에 입소하기 전에 가장 걱정했던 부분 중 하나는 기숙사의 환경과 밥을 어떻게 해야하는지였다. 추후 정글을 지원하려는 분들을 위한 기록용으로 간단하게만 소개한다.기숙사 입소입소 당일에 짐이 너무 많아서 택시를 타고 왔다. 다행히 집이랑 그리 멀지 않기도 하고, 늦게 출발하니 막히는 시간에서 벗어나서 거의 하이패스로 도착할 수 있었고 택시비도 예상보다 훨씬 덜나왔다. (네이버 지도보다 약 1만원 정도 덜나와서 기분 좋았다) 그리고 기사님이 짐 많은 중생을 많이 도와주셔서 덕분에 잘 도착할 수 있었다.기숙사는 안내되는 바와 같이 2인 1실이다. 지금은 짐이 다 차있어서 그나마 입소하자 마자 찍어둔 사진으로나마 공유한다.참조로 기숙사에는 책상이 없다. 공부는 무조건 강의실에 와서 하거나 캠퍼스 곳곳에 놓여있..

• format_list_bulleted IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)
• · 2025. 3. 23.