하얀이 코딩 블로그

1) 힙(Heap)의 특징 완전 이진 트리 자료구조의 일종이다. 힙에서는 항상 루트 노드를 제거한다. * 최소 힙 (1) 루트 노드가 가장 작은 값을 가진다. (2) 따라서 값이 작은 데이터가 우선적으로 제거된다. * 최대 힙 (1) 루트 노드가 가장 큰 값을 가진다. (2) 따라서 값이 큰 데이터가 우선적으로 제거된다. 2) 최소 힙 구성 함수: Min-Heapify() 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다. 상향식의 예를 보면, 왼쪽 자식 트리를 보면 최소 힙을 만족하지 않는다. 이럴 때 Min-Heapify를 수행하면 다음과 같이 노드의 위치가 변경된다. 이후에 3, 4 노드의 위치로 바꿔주면 최소힙이 완성된다. import sys import heap..

- BFS Breadth-First Search의 약자로 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 큐를 이용하며, 구체적인 동작은 다음과 같다. 1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2) 큐에서 노드를 꺼낸 뒤, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다. 3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. from collections import deque def bfs(graph, start, visited): q = deque([start])# deque로 리스트 생성 visited[start] = True# 현재 노드, 즉 시작 노드를 방문처리함 while q:# q가 빌 때까지 반복 v = q.poplef..

- DFS Depth-First Search의 약자로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 혹은 재귀 함수를 이용하며, 구체적인 동작은 다음과 같다. 1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. def dfs(graph, v, visited): # (그래프 리스트, 현재 노드, 노드의 방문여부 리스트) visited[v] = True# 처음 노드인 v의 방문을 True 처리 print(v, end=' ') for i in graph[v]..

from collections import deque q= deque() q.append(1) q.append(2) q.append(3) q.append(4) q.popleft() q.append(5) q.popleft() deque 라이브러리를 사용하면 popleft(), popright()가 사용 가능하다. 각각 제일 왼쪽, 제일 오른쪽 원소를 삭제한다. 큐는 선입선출을 하는 구조인데, 일반 pop()을 사용하면 제일 나중에 들어온 원소가 삭제되므로 popleft를 사용해야한다.

- 이진 탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 리스트 안의 특정 데이터를 찾기 위해 처음부터 데이터를 하나씩 확인하는 순차 탐색보다 효율적으로 데이터를 탐색할 수 있다. 즉, 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(log N)이다. 만약 [0, 2, 4, 6, 8, 10, 12, 14, 16, 18] 라는 리스트가 있다면 시작점은 [0], 끝점은 [9], 중간점은 [4] 다. 짝수개가 들어있는 리스트에서는 소수점 이하를 제거하여 중간값을 구하기 때문에 [5]가 아닌 [4]가 된다. 1) 숫자 4가 있는지 확인하고 싶다. 그런데 4는 중간점 값인 '8'보다 작으니까 중간점을 포함한 오른쪽 값은..

animal = {'dog':5, 'cat':6, 'rabbit':10, 'tiger':9, 'lion':8} sorted1 = sorted(animal.items(), key=lambda x: x[0]) # animal의 key값에 따라 정렬 sorted2 = sorted(animal.items(), key=lambda x: x[1]) # animal의 value값에 따라 정렬 sorted() 함수는 key값에 따라 정렬한다. lambda를 사용하면 x[0]은 animal 딕셔너리의 key에 해당하고, x[1]은 animal 딕셔너리의 value에 해당한다. print(sorted1) >>> [('cat', 6), ('dog', 5), ('lion', 8), ('rabbit', 10), ('tiger'..

math 라이브러리의 gcd()와 lcm() 함수 사용 가능 import math a = 21 b = 14 print(math.gcd(21, 14)) # 7 print(math.lcm(21, 14)) # 42 파이썬이 3.9버전 미만이면 lcm()함수가 에러뜬다 ㄷ ㄷ 뭐가 문젠지 엄청 찾음 참고: 이코테 2021 강의

collections 라이브러리의 Counter는 리스트와 같은 객체에서 내부에 원소가 몇 번 등장하는지 알려준다. from collections import Counter counter = Counter(['dog', 'cat', 'dog', 'dog', 'cat']) print(counter['dog']) print(counter['cat']) print(dict(counter)) 실행결과 3 2 {'dog': 3, 'cat': 2}

1) 중복 순열 - product from itertools import product data = ['a', 'b', 'c'] result = list(product(data, repeat=2)) # 중복을 허용하여 2개를 뽑는 모든 순열 print(result) 2) 중복 조합 - combinations_with_replacement from itertools import combinations_with_replacement data = ['a', 'b', 'c'] result = list(combinations_with_replacement(data, 2)) # 중복을 허용하여 2개를 뽑는 모든 조합 print(result) 참고: 이코테 2021 강의 동영상

1) 순열 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것 {'a', 'b', 'c'}에서 세 개를 선택하여 나열하는 경우, permutations 사용 from itertools import permutations data = ['a', 'b', 'c'] result = list(permutations(data, 3)) print(result) 실행결과 [('a','b','c'), ('a','c','b'), ('b','a','c'), ('b','c','a'), ('c','a','b'), ('c','b','a')] 2) 조합 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것 {'a', 'b', 'c'}에서 순서를 고려않고 두 개를 뽑는 경우, combinations 사용..