Algorithm/알고리즘 이론

파이썬으로 구현하는 세그먼트 트리(Segment Tree)

https://codingsmu.tistory.com/175 파이썬으로 구현하는 구간합과 누적합(Prefix sum)구간합이란?구간합이란, 나열된 숫자에서 특정 구간의 합을 말합니다. 만약 위의 arr에서 1~3번째 구간합을 구하고 싶다면, arr[1]+arr[2]+arr[3] = 4+3+2 = 9 입니다. 가장 기본적인 구간합 알고리즘을codingsmu.tistory.com 이전 글에서 먼저, 배열에서의 특정 구간의 합을 구할 때 O(N) 시간안에 구할 수 있는 누적합(Prefix Sum)알고리즘을 알아보았습니다. 이번 글에서는 더 개선된 시간인 O(logN)으로 구간합을 구할 수 있는 자료구조인 세그먼트 트리(Segment Tree)에 대해 알아보도록 하겠습니다.    세그먼트 트리(Segment T..

파이썬으로 구현하는 구간합과 누적합(Prefix sum)

구간합이란?구간합이란, 나열된 숫자에서 특정 구간의 합을 말합니다. 만약 위의 arr에서 1~3번째 구간합을 구하고 싶다면, arr[1]+arr[2]+arr[3] = 4+3+2 = 9 입니다. 가장 기본적인 구간합 알고리즘을 생각해보면, 단순히  i~j번째까지의 값을 더하면 되고 이때 시간복잡도는 O(N)입니다.하지만, 배열의 크기인 N이 매우 크고 구간합을 물어보는 쿼리가 N번이라면,다음과 같이 O(N)*O(N) ≈  O(N^2)이라는 거듭제곱의 높은 시간복잡도를 가지는 알고리즘이 됩니다.arr = list(map(int, input().split())) # 크기가 n개인 arrfor _ in range(N): # N 번의 쿼리 : O(N) i, j = map(int, input().split()..

[그래프 탐색] 파이썬으로 구현하는 DFS, BFS

그래프 탐색이란?그래프의 각 노드를 방문하는 것으로, 크게 깊이 우선탐색(Depth First Search, DFS)과 너비 우선 탐색(Bredth-First Search, BFS) 알고리즘이 있습니다.  DFS는 주로 재귀 혹은 스택으로 구현하게 되며, 백트래킹 문제에서 주로 사용됩니다. BFS의 경우 주로 큐로 구현하며, 최단 경로를 구하는 문제에서 자주 사용됩니다.  파이썬으로 그래프 입력받기그래프 탐색 방법을 구현하기 전, 파이썬에서 그래프를 입력받는 방법에 대해서 알아보도록 하겠습니다. 파이썬에서 제공하는 List, deque등 다양한 자료형으로 저장할 수 있지만, 개인적으로 파이썬의 Dictionary 자료형으로 입력받는 것을 가장 선호해 이 방법을 소개하고자 합니다. 앞의 그림과 같이 노드 ..

[문자열] 파이썬으로 구현한 유효한 팰린드롬(Palindrome)

팰린드롬(Palindrome)이란? 앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬, 우리말로는 회문이라고 부릅니다. 영어의 회문으로는 "No lemon, no melon"처럼 뒤집어도 같은 알파벳 순서를 가지는 문장을 예시로 들 수 있습니다. 예시와 같이 회문은 보통 대소문자와 공백, 특수문자를 구별하지 않습니다. (단, 문제마다 정의하는 회문이 다를 수 있습니다) 파이썬으로 유효한 팰린드롬 검사하기 자료형에 따른 구현 방법 1. 리스트로 구현 2. 덱(deque)으로 구현 각 방법을 보기 전, 입력으로 들어오는 strs은 다음의 정규식을 통해 대소문자/특수문자/공백 구분 없이 유효성을 검사할 수 있도록 처리되었습니다 strs = strs.lower() strs = ..

이진 탐색(Binary Search)과 매개변수 탐색(Parametric Search)

이진탐색이란? 이진 탐색이란 정렬된 배열에서 타겟의 존재 여부와 존재한다면 해당 위치를 알려주는 알고리즘이다. 중요한 점은 정렬된 배열에서만 사용할 수 있다는 것이다 기존의 단순 비교를 통한 탐색을 한다면 최악의 경우 배열 안에 있는 N개의 데이터 모두와 비교해야하므로 시간복잡도가 O(N)인 반면, 이진탐색은 재귀적으로 탐색범위를 반으로 줄여나가서 시간복잡도가 O(logN)까지 줄일 수 있다 이진탐색과 매개변수 탐색 매개변수 탐색(parametric search)이란? *최적화 문제를 *결정 문제로 풀 수 있는 기술로 다음과 같은 상황에 이용할 수 있다. *최적화 문제(Optimization Problem): 가능한 해들 중 가장 좋은 해를 찾는 것 *결정 문제(Decision Problem): 답이 이..

[그래프 이론] 플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드-워셜(Floyd-Warshall) 알고리즘이란? 모든 두 노드 u,v 사이에서 가장 최단 거리를 찾는 알고리즘 시간복잡도 $O(n^3)$으로 그래프의 크기가 작을 때만 사용 가능 음의 에지(negative edge)가 있어도 계산이 가능한 알고리즘 단, 음의 사이클(negative cycle)이 있을 경우 불가능 기본 개념: $A^k$[i][j] 노드 i에서 j까지의 최단거리 비용에는 $index

네트워크 플로우(Network Flow)

네트워크 플로우(Network Flow)란? 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘으로 네트워크 데이터 전송, 교통 체증 등 다양한 분야에서 활용되고 있음 최대 유량(Maximum Flow)이란? 최대 유량이란 가중치가 있는 방향그래프(Weighted Directed Graph) G와 시작 노드 S, 도착 노드E 가 주어졌을 때, 각 엣지의 용량(Capacity)를 고려하여 S에서 E로 흘려보낼 수 있는 유량의 최대값을 말하는 것이다. 이 때, G의 각 에지 가중치를 용량(capacity)라고 하며 (u,v)의 용량을 c(u,v)라고 쓴다. 예로, 아래와 같은 그래프 G가 있다고 할 때, A에서 D로 최대한 많은 유량을 보내려고 할 때 가장 합리적인 양은 가..

이분 매칭(Bipartite Matching)

이전 게시글인 에 이어지는 알고리즘 개념 글입니다 https://codingsmu.tistory.com/109 이분 매칭(Bipartite Matching)이란? 네트워크 플로우의 개념중에서 이분 그래프(Bipartite Graph)에서의 최대 유량(maximum flow)을 구하는 경우로, 에지의 용량(capacity)이 전부 1인 이분 그래프에서의 최대유량(maximum flow)을 구하는 문제는 이분 그래프에서의 최대 매칭(maximium matching)과 동치이다. 이때 매칭은, 서로 다른 그룹에 놓인 두 정점을 짝지어주는 의미로 이분그래프에서 최대 매칭을 최대 유량 알고리즘인 디닉 혹은 에드몬드 카프 알고리즘을 이용해 구해줄 수 있으나, DFS를 이용하여 O(V*E)시간에 쉽게 구현할 수 있다..