하얀이 코딩 블로그

- 플로이드 워셜 알고리즘 1. 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 2. 플로이드 워셜 알고리즘은 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. * 다만, 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다. 3. 2차원 테이블에 최단 거리 정보를 저장한다. 4. 다이나믹 프로그래밍 유형이다. 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. 예를 들어, a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다. 점화식은 다음과 같다. a→b로 가는 거리 = (a→b로 가는 거리의 값)과, (a→k 값에 k→b를 더한 값) 중 작은 값이 된다. 만약 a→b로 가는 간선이 없다면, 그건 무한으..

- 분할 정복 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말한다. 분할 정복은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어낸다. - 대표적인 분할 정복 알고리즘으로는 병합 정렬을 들 수 있다. 아래 그림은 병합 정렬을 이용한 분할 정복의 원리를 잘 보여준다. * 정리 1. 숫자가 담긴 배열이 있을 때 동일한 유형의 여러 하위 문제로 나눈다. 2. 가장 작은 단위가 될 때까지 하위 문제를 해결한다. 3. 그 하위 문제에 대한 결과로 원래 문제의 결과를 조합한다. - 분할 정복 의사코드 function F(x): if F(x)가 간단 then: return F(x)를 계산한 값 else: ..

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}