미식가의 개발 일기

최소 신장 트리(MST, Minimum Spanning Tree)란?"그래프의 모든 정점을 최소한의 간선으로 연결하되, 간선들의 가중치 합이 최소가 되는 트리"  구성 요소 1. 무방향 가중치 그래프: 간선이 방향성을 가지지 않고, 가중치가 있는 경우  정점: 연결하려는 대상간선: 두 정점 A --(5)-- B| |(2) (3)| |C --(4)-- D  2. 신장 트리 (Spanning Tree): 그래프의 모든 정점을 포함하면서, 사이클 없이 연결된 부분 그래프                                                  -> N개의 정점을 연결하려면 최소 N-1개의 간선이 필요하다. 3. 최소 신장 트리 (Minimum Spanning..

유니온 파인드(Union-Find) 알고리즘이란?"서로소 집합(Disjoint Set)을 효율적으로 관리하는 자료구조"[서로소 집합: 공통 원소가 없는 집합]"두 원소가 같은 집합에 속해 있는지 확인하고, 두 집합을 합치는 작업을 빠르게 수행한다." 주요 연산 1. Find(찾기)어떤 원소가 속한 집단의 대표 원소(루트)를 찾는다.두 원소가 같은 집단에 속해 있는지 확인할 수 있다. 2. Union(합치기)두 집합의 루트를 찾아 하나의 집합으로 합친다.-> 이 2가지 기법만 가지고 구현하면 트리의 깊이가 깊어질 수 있다. 매번 한 트리의 루트에 다른 트리를 연결하면 트리의 높이가 증가하여 Find 연산이 비효율적으로 수행되므로 최적화 기법이 필요하다.  최적화 기법  1. 경로 압축(Path Compre..

포맷 스트링(f-string)문자열 내에서 변수나 표현식의 값을 포맷idx = 1fruit = "Apple"print('{}: {}'.format(idx + 1, fruit)) print(f'{idx + 1}: {fruit}') -> 2: Applea = 1.234print(f'{a:.2f}'} -> 1.23​조인(join)iterable 객체(리스트, 튜플 등)의 요소들을 하나의 문자열로 연결할 때 사용words = ["Hello", "World", "!"]combined_string = " ".join(words) -> Hello World !words = ["Hello", "World", "!"]combined_string = ".".join(words) -> Hello.World.! 구분자 지정(..

순열from itertools import permutationsvlist = [10, 20, 30] # 2차원 리스트도 가능permut = list(permutations(vlist, len(vlist)))print(permut) -> [(10, 20, 30), (10, 30, 20), (20, 10, 30), (20, 30, 10), (30, 10, 20), (30, 20, 10)]→ permutations를 list()로 감싸줘야 하는 이유는?permutations는 iterable객체로 반복 가능한 객체이다. 즉, 반복문을 사용하여 그 안에 있는 순열들을 하나씩 가져올 수 있으나 명시적으로 iterable한 형태(열거형 자료형)로 변환하지 않으면 순열을 직접적으로 확인할 수는 없다.  중복 순열f..

내장 데이터 타입인 리스트, 튜플, 딕셔너리 등을 확장하여 다양한 데이터 구조를 제공하는 모듈데이터를 효율적으로 저장하고 처리하는 데 사용 deque→ Queue 구현from collections import dequeque = deque([2, 3, 4])# 뒤에 추가que.append(5) -> [2, 3, 4, 5]# 앞에 추가que.appendleft(1) -> [1, 2, 3, 4, 5]# 맨 뒤에 값 꺼내기que.popleft() -> 5# 맨 앞에 값 꺼내기que.pop() -> 1*list에서 사용하는 연산이 가능하다.(append, pop, insert...)→ 리스트처럼 인덱스로 접근 가능Counterfrom collections import Countercounter = Counter..

한 줄로 간단하게 정의되는 익명 함수 람다 함수를 활용한 정렬2차원 리스트 정렬# 첫 번째 요소를 기준으로 정렬vlist = [[80,20],[50,40],[30,10]]sorted_vlist = sorted(vlist, key=lambda x: x[0])# 첫 번째 요소를 기준으로 정렬 후 두 번째 요소를 기준으로 정렬vlist = [[80,20],[50,40],[30,10]]sorted_vlist = sorted(vlist, key=lambda x: (x[0], x[1]))# 첫 번째 요소를 내림차순 정렬 후 두 번째 요소를 오름차순 정렬vlist = [[80,20],[50,40],[30,10]]sorted_vlist = sorted(vlist, key=lambda x: (-x[0], x[1])) 람..

리스트를 생성하기 위한 간결하고 효율적인 방법기존의 반복문을 사용하여 리스트를 생성하는 방법보다 더 간결하게 코드를 작성할 수 있다.기본 구조new_list = [expression for item in iterable if condition] expression: 각 요소에 대해 계산되어 새 리스트에 추가될 값item: iterable 객체(예: 리스트, 튜플 등)에서 가져온 개별 요소iterable: 순회할 수 있는 객체(리스트, 튜플 등)if condition (옵션): 조건식으로, 해당 조건이 참(True)일 때에만 expression이 리스트에 추가 간단한 예시0 부터 9까지의 숫자 중 짝수만 들어있는 리스트numbers = [i for i in range(10) if i % 2 == 0]각 원..

리스트(List) 수정 O, 순서 O, 중복 O선언a = list()a = []추가# 맨 뒤에 아이템 추가list_name.append(a)# 특정 위치에 아이템 추가list_name.insert(3, 5) -> 3번째 인덱스에 5를 삽입# 리스트 안에 리스트를 요소로 풀어서 추가하기l = [1, 2, 3]ans = []ans.append(1)ans.append(*l)print(ans) -> [1, 1, 2, 3]삭제a = [10, 20, 30]#인덱스로 삭제del a[0]#값으로 삭제a.remove(10)#리턴 후 삭제a.pop(0)슬라이싱 -> list[start:stop:step] 형식my_list = [0, 1, 2, 3, 4, 5]# 기본 슬라이싱print(my_list[2:5]) # [2,..