728x90
반응형

자료구조 31

Red Black Tree의 개념과 삽입/삭제, C언어 구현

RB Tree(Red Black Tree) - 이진 탐색 트리(BST) 기반의 self balanced tree - 삽입/삭제는 BST와 동일하지만, 삽입/삭제 후 RB Tree의 5가지 속성을 만족하기 위한 재조정 작업이 필요하다. - 스스로 좌/우 서브트리의 균형을 맞춘다 - 서브트리 간 height 차이는 최대 2이다. RB Tree의 속성 5가지 1. 모든 노드는 red 혹은 black 2. 루트 노드는 black 3. 모든 nil 노드는 black nil 노드 - 존재하지 않음을 의미하는 노드 - 자녀가 없을 때 자녀를 nil 노드로 표기함 - nil노드는 값이 있는 노드와 동등하게 취급 - RB트리에서 leaf노드는 nil노드이다. 4. red의 자녀는 모두 black이다 = red는 연속적으..

[크래프톤 정글 5기] week04 C언어 주차 두번째 날, C언어 문법, 포인터

선언(declaration)과 정의(definition) 선언(declaration) - 컴파일러가 참조할 식별자(identifier)의 이름을 알린다. - 식별자란 변수의 타입, 함수의 인자목록을 뜻하며 이름은 변수, 함수, 클래스의 이름 등을 뜻한다. - 선언은 메모리 영역 상에 올리지 않기 때문에 중복되어도 문제가 되지 않는다. extern int a; // 전역변수 선언 int add(int a, int b); // 함수 선언 class ClassId; // 클래스의 선언 정의(definition) - 식별자와 이름으로부터 코드를 생성한 것 - 정의는 고유해야 한다. 같은 식별자와 이름의 정의가 2개 이상이면 컴파일 에러 발생 int add(int a, int b) { // 함수의 정의 (함수 본..

[크래프톤 정글 5기] week02 알고리즘 주차 열네번째 날, 최소 스패닝 트리, 프림 알고리즘, 이분 그래프

신장 트리(Spanning Tree) - 그래프 내의 모든 정점을 포함하면서 사이클이 없는 부분 트리 최소 스패닝(신장) 트리(Minimum Spanning Tree, MST) - 가중치가 있는 양방향 그래프에서 싸이클 없이 모든 정점을 포함하며 가중치의 합이 최소인 트리 - 모든 정점을 연결하는 트리를 형성하면서, 가중치 합이 최소화되도록 하는 것 프림(Prim) 알고리즘 - 크루스칼 알고리즘과 더불어 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 대표적인 알고리즘 - 가중치가 작은 순으로 노드를 그래프에 포함시켜야 하기 때문에 우선순위 큐를 사용한다. - 이미 그래프에 속한 노드엔 적용시키지 않기 위해 visited를 사용한다. 프림 알고리즘 동작원리 1. 임의의 시작 노드를 설정하고 T(트리)..

[Baekjoon 3055 / python / 골드4] 탈출

# 도치가 사방으로 가는 것과, 물이 도치의 방문목록에 영향을 받는 것(도치가 지나간 길 안가는것)은 결과에 영향을 미치지 않는다. import sys from collections import deque input = sys.stdin.readline R, C = map(int, input().split()) # 행, 열 forest = [list(input().strip()) for _ in range(R)] visited = [[-1] * C for _ in range(R)] # -1로 설정해두고 도치의 이동 과정을 입력할것이다 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] queue = deque() for x in range(R): for y in range(C): if f..

Algorithm/BFS 2024.04.03

[Baekjoon 1707 / python / 골드4] 이분 그래프

import sys sys.setrecursionlimit(10 ** 9) input = sys.stdin.readline # 이분 그래프 판별 DFS 함수 def DFS(graph, start, visited, group): visited[start] = group for i in graph[start]: if visited[i] == 0: # 방문 안 한 곳이라면 result = DFS(graph, i, visited, -group) if not result: return False # 하위에서 이분 그래프 아니라고 판단했다면 함수 종료 elif visited[i] == group: # 인접노드인데 그룹이 같을경우 이분그래프 아님 return False return True # 입력받은 갯수만큼 그래..

Algorithm/Graph 2024.04.03

[Baekjoon 1197 / python / 골드4] 최소 스패닝 트리

import heapq import sys input = sys.stdin.readline N, E = map(int, input().split()) # 노드, 간선 graph = [[] for _ in range(N + 1)] # 그래프 입력받기 for _ in range(E): a, b, c = map(int, input().split()) graph[a].append((c, b)) graph[b].append((c, a)) visited = [False] * (N + 1) # 방문체크 리스트 def prim(graph, start): # 그래프, 시작노드 입력받는다, 프림 알고리즘 사용 visited[start] = True # 시작노드 방문체크 distance = 0 # 거리(가중치)를 계산할 변..

Algorithm/Graph 2024.04.03

[Baekjoon 1916 / python / 골드5] 최소비용 구하기

import heapq import sys INF = int(1e9) input = sys.stdin.readline N = int(input()) # 도시 개수 ( 노드 개수 ) E = int(input()) # 버스 개수 ( 간선 개수 ) graph = [[] for _ in range(N + 1)] for _ in range(E): a, b, c = map(int, input().split()) # 출발노드, 도착노드, 거리 입력받기 graph[a].append([c, b]) # (거리, 도착노드) start, end = map(int, input().split()) # 계산해야 할 출발지, 도착지 distance = [INF] * (N + 1) # 최단 경로 리스트 def dijkstra(star..

[Baekjoon 18352 / python / 실버2] 특정 거리의 도시 찾기

import heapq import sys INF = int(1e9) input = sys.stdin.readline N, E, K, start = map(int, input().split()) # 노드, 간선, 찾을거리, 출발노드 graph = [[] for _ in range(N + 1)] for _ in range(E): a, b = map(int, input().split()) # 출발노드, 도착노드 graph[a].append([1, b]) # 거리(1), 도착노드 distance = [INF] * (N + 1) def dijkstra(start): queue = [] heapq.heappush(queue, (0, start)) # 시작노드거리, 시작노드 큐에 삽입 distance[start] ..

728x90
반응형