[자료구조] 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.

[CS] C : Malloc과 동적 메모리

메모리 구조프로그램이 실행되기 위해서는 먼저 프로그램이 메모리에 로드(Load)되어야 한다.또한 프로그램이 사용하는 변수들을 저장할 메모리도 필요하다. 따라서 운영체제는 프로그램의 실행을 위해 다양한 메모리 공간을 제공한다.코드 영역메모리의 코드 영역은 실행할 프로그램의 코드, 상수, 리터럴 등이 저장되는 영역이다텍스트 영역이라고도 부른다.CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리한다읽기 전용으로, 코드가 메모리에 로드되는 시점에 할당된다데이터 영역프로그램의 전역 변수와 정적(static) 변수가 저장되는 영역이다프로그램의 시작과 함께 할당되고, 프로그램이 종료되면 소멸된다힙 영역메모리의 힙 영역은 사용자가 직접 관리할 수 있는 그리고 관리해야만 하는 메모리 영역이다사용자에 의해 동적으로..

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

[CS] 가상화

가상화✔️ 가상화란 ?하나의 컴퓨터 자원을 여러개 처럼 나눠서 사용하는 기술가상화의 유형 : 무엇을 가상화 하는가?종류설명예시CPU 가상화가상 머신에 가상 CPU를 제공하여 물리 CPU를 효율적으로 나눠 사용하이퍼바이저 (VMware ESXi, KVM)메모리 가상화VM마다 독립된 메모리 공간을 제공, 메모리 자원 효율 관리메모리 페이징, NUMA, Ballooning스토리지 가상화물리적 저장장치를 가상으로 묶어 VM에 할당NAS, SAN, vSAN네트워크 가상화가상 NIC, 가상 스위치 등을 통해 네트워크를 가상화SDN, VLAN, 가상 스위치 (vSwitch)물리 서버 vs 가상 서버물리 서버의 한계하나의 물리 서버에는 보통 하나의 OS와 애플리케이션이 설치된다서버를 더 활용하고 싶어도, OS 충돌 위..

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

백준 : 1379 강의실2

백준 : 1379 강의실2문제 요약총 N개의 강의가 있다.각 강의는 세 가지 정보:강의 번호시작 시간종료 시간겹치는 강의들은 서로 다른 강의실이 필요하다.목표:최소 강의실 개수 출력각 강의마다 배정된 강의실 번호 출력 (강의 번호 순)문제 분석이 문제는 전형적인 그리디 + 우선순위 큐 (heapq) 문제입니다.📌 강의실 배정의 본질겹치지 않는 강의들은 같은 강의실을 사용할 수 있다.가장 먼저 끝나는 강의실부터 체크하면서 빈 방이 있으면 재사용.없다면 새로 방을 배정한다.📌 주의강의 번호와 강의 순서는 다르다!출력은 강의 번호 순처리 순서는 시작 시간 순따라서 입력을 받아서 → 시작 시간 기준으로 정렬 → 결과는 별도 배열에 저장최종 코드import sys, heapqinput = sys.stdin.r..

• format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
• · 2025. 4. 10.

백준 : 2098 외판원 순회

백준 : 2098 외판원 순회문제 분석비트마스크와 DP를 이용해 모든 도시를 한 번씩 방문하고 다시 출발지로 돌아오는 최소 비용을 구하는 문제로, 방문 상태를 비트마스크로 관리하면서 현재 도시와 방문 경로를 기반으로 dp 테이블을 갱신해 최적 경로를 찾는다.비트마스크 활용n = 도시 개수비트마스크를 사용하여 0과 1로 도시 n개의 방문 여부를 관리한다.비트마스크는 도시 개수 n만큼의 자리수를 가지는 이진수로 표현된다.예시: 0111비트마스크를 읽는 방법은 오른쪽 → 왼쪽 이다.(오른쪽이 출발 도시, 왼쪽으로 갈수록 번호가 높은 도시)0 : 도시 3 방문 안 함1 : 도시 2 방문함1 : 도시 1 방문함1 : 도시 0 (출발지) 방문함 (시작 시 초기 세팅)tsp(visited, current) 에서 초기..

• format_list_bulleted IT 성장기 (교육이수)/알고리즘 문제풀이
• · 2025. 4. 9.

[알고리즘] 위상정렬

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

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