개발개발

힙은 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리 기반의 자료구조이다. 힙은 부모노드와 자식노드의 관계로 최대 힙, 최소 힙으로 나뉜다. 키 값의 대소관계는 부모노드와 자식노드 간에만 성립하며 형제 사이에는 성립하지 않을 수 있다. 최대 힙 : 부모노드 키 값 >= 자식노드 키 값. 뿌리노드가 항상 제일 큼 최소 힙 : 부모노드 키 값

다익스트라 알고리즘은 그래프에서 정점 간의 최단 경로를 찾는 알고리즘이다. 그래프에서 주어진 시작 노드에 대해서 다른 정점 간의 가장 짧은 경로를 찾는다. 즉, u에서 v로 갈 때 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 것이다. 이 알고리즘은 어떤 한 정점에서 다른 정점까지 가는 경로를 찾을 때 가장 짧은 경로가 결정되면 멈추는 식으로 사용한다. 파이썬으로 구현하기 위와 같은 그래프이고 시작노드가 1일 때, 시작노드 : [(도착노드, 가중치)] 형식으로 딕셔너리를 만들면 아래와 같다 n = 1 graph = { 1: [(2,2), (3,3)], 2: [(3,4), (4,5)], 3: [(4,6)], 5: [(1,1)] } 각 정점에 대한 시작노드부터 해당 정점까지의 가중치 합을 저장할 p..

DFS def dfs(graph, v, visited): #현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visitied[i]: dfs(graph, i, visited) graph = [ [], [2, 3], [1], [1, 4], [3] ] # 각 노드가 방문된 정보를 표현 visited = [False] * 9 # 정의된 DFS 함수 호출 dfs(graph, 1, visitied) BFS from collections import deque def bfs(graph, start, visited): # 큐 구현을 위해 deque 라이브러리 사용 queue = deq..

집합은 set을 사용해 만들 수 있다. 집합은 중복을 허용하지 않고 순서가 없다. 그렇기 때문에 인덱스가 없어 인덱싱을 통해 값을 얻기 위해서는 리스트나 튜플로 변환해야 한다. s = set() >>> {} s = set([1,2,3]) >>> {1, 2, 3} s = set("hello") >>> {'e', 'h', 'l', 'o'} 집합에 값 1개 추가, 여러개 추가, 제거 등은 다음과 같이 구현할 수 있다. s = set([1, 2, 3]) # 값 하나 추가 s.add(4) >>> {1, 2, 3, 4} # 값 여러개 추가 s.update([4, 5]) >>> {1, 2, 3, 4, 5} # 특정 값 제거 s.remove(3) >>> {1, 2} set 자료형을 유용하게 사용하는 경우는 교집합, 합..

깊이 우선 탐색 DFS와 너비 우선 탐색 BFS는 그래프를 탐색하는 대표적인 방법이다. 그래프란 정점 node와 정점을 연결하는 간선 edge로 이루어져 있는 자료구조이다. 깊이 우선 탐색 DFS DFS는 Depth First Search의 약자로, 루트 노드에서 시작하여 아래 방향으로 탐색한다. 최대한 깊이 내려간 뒤 더이상 갈 곳이 없을 경우 옆으로 이동하여 탐색하는 방법이기 때문에 루트노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다. 모든 노드를 방문하고자 하는 경우 유용하며, BFS보다 좀 더 간단하지만 검색속도는 느리다. 자기 자신을 호출하는 재귀적 알고리즘의 형태로 구현하며 스택을 이용한다. 너비 우선 탐색 BFS BFS는 Breadth First Search의 약자로, 루트..

브루트포스란 짐승(Brute), 힘(Force)이라는 의미처럼 무식하게 모든 경우의 수를 다 해보는 알고리즘을 뜻하며 완전 탐색이라고도 한다. 거의 모든 문제에 사용할 수 있지만 주로 모든 경우의 수를 요구하는 문제에서 사용된다. 브루트포스는 시간 측면에서 매우 비효율적이지만 만들기 쉽고 100%의 확률로 정답을 도출한다는 장점이 있다. 또한, 브루트포스에서 시작해 좀 더 발전된 알고리즘을 생각하는 출발점이 되기도 한다. 아래는 브루트포스를 구현하기 위한 기본적인 도구의 예이다. 순차 탐색 : 선형 구조를 전체적으로 탐색한다. 깊이 우선 탐색 (DFS, Depth First Search) : 수직 방향으로 탐색하는 기법으로 백트래킹과 관련이 깊다. 너비 우선 탐색 (BFS, Breadth First Se..

itertools를 이용하여 순열과 조합을 구현하면 더욱 빠르게 처리할 수 있다. 1. 순열 : permutations(N, r) N에서 중복을 허용하지 않고, r개를 뽑아 순서대로 나열한다. 중복을 허용하지 않기 때문에, 뽑은 것 중 같은 값이 나올 수 없다. 뽑힌 순서대로 나열하기 때문에 순서가 중요하다. 같은 값들이 뽑히더라도 순서가 다르면 다른 경우이다. from itertools import permutations # for 문을 이용하지않고 구현하기 print(list(map(''.join, permutations(['A', 'B', 'C'])))) >>> ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'] # for 문을 이용하여 구현하기 for i in permut..

동적계획법, Dynamic Programming은 아래 두 조건을 만족할 때 사용한다. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결 중복 부분 구조 : 동일한 작은 문제를 반복적으로 해결 다이나믹 프로그래밍은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘으로 상향식 접근이며 메모이제이션을 핵심 기술로 사용한다. 메모이제이션(Memoization)이란, 동일한 계산을 반복해야 할 때 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산을 반복하지 않도록하여 실행속도를 빠르게 하는 기술이다. 피보나치 수열이나 재귀함수에서 유용하게 쓰이며 점화식을 찾는게 중요하다. 문제의 순환적인 성질을 이용하기 때문에 점화식을 이용하여 재귀적으로 정의해야 한다...

큐(Queue)는 스택(Stack)과 유사하지만 반대의 성격을 지닌다. 스택은 LIFO(Last In First Out)의 형태로 마지막에 들어간 데이터가 첫 번째로 나오는 구조이고 큐는 FIFO(First In First Out)의 형태로 첫 번째 들어간 데이터가 첫 번째로 나오는 구조이다. 일차원의 선형 자료구조인 큐는 값을 저장하는 연산 enqueue와 값을 꺼내는 연산 dequeue가 있어야한다. 큐의 종류로는 선형 큐(Queue), 원형 큐(Circular Queue), 우선순위 큐(Priority Queue)가 있다. 선형 큐는 막대모양의 큐로 크기가 제한되어 있다. 그렇기 때문에 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한칸씩 앞으로 옮겨야한다는 단점이 있다. 선형 큐의 단점을 보완..