# Algorithm_Theory

me4n

모든 정점의 쌍 u와 v간의 최단경로를 구하는 알고리즘Aki0부터 k까지의 정점만을 이용한 정점 i에서 정점 j까지의 최단 경로정점 0부터 정점 k-1까지의 정점을 고려한 최단 거리 Ak-1을 구한 상태에서 다음 정점k를 고려할 때, 중간에 정점 k를 통과하지 않는 경

me4n

무방향 가중치 그래프에서 최저의 비용을 갖는 신장 트리간선들의 가중치 합이 최소인 신장 트리를 의미한다.최소 비용 신장 트리를 만드는 알고리즘KRUSKALPRIM신장 트리를 만드는 제한 조건그래프 내에 있는 간선들만 사용해야한다.총 n-1개의 간선만을 사용해야 한다.사

me4n

최단 경로 알고리즘 중 가장 많이 사용된다.무방향 그래프, 방향 그래프 모두 적용 가능하다.모든 간선은 음이 아닌 비용을 가져야 한다.시작 정점부터 모든 다른 정점까지의 최단 경로를 구하는 알고리즘시작 정점(v) 에서, 정점(u)까지의 최단경로 distu를 구해, 정점

me4n

전산학에서의 트리 순회는 에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다. 이는 노드를 방문하는 순서에 따라 분류된다. 여기서 설명하는 알고리즘들은 이진트리에 대해서 작성되었지만, 다른 모든 트리에서도 일반화될 수 있다.분할정복 탐색 알고

me4n

탐욕법 이라고 불린다.현재 상황에서 지금 당장 좋은것만을 고르는 방법매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음보통 코딩테스트에 출제되는 그리디 알고리즘의 문제는, 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있

me4n

다이나믹 프로그래밍, DP, 동적 계획법 모두 같은걸 의미함최적해를 구하기위한 시간, 또는 메모리공간이 많이 필요한 경우 사용하게 된다.컴퓨터는 연산속도에 한계가 있고, 메모리 공간도 한정적이기 때문연산속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘이

me4n

하나의 정점에서 시작하여 모든 정점을 한 번씩 방문하여 처리하는 연산많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결된다.예 : 도로망에서 특정 도시에서 다른 도시로 갈 수 있는지 여부갈 수 있는곳 까지 계속 진행, 더 진행할 수 없으면 돌아온뒤 다시 탐색qu

me4n

하나의 정점에서 시작하여 모든 정점을 한 번씩 방문하여 처리하는 연산많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결된다.예 : 도로망에서 특정 도시에서 다른 도시로 갈 수 있는지 여부갈 수 있는곳 까지 계속 진행, 더 진행할 수 없으면 돌아온뒤 다시 탐색st

me4n

접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조선입선출(First-In First-Out, FIFO) 리스트가장 먼저 들어온 데이터가 가장 먼저 나감한쪽 끝(rear)에서 삽입이 일어남반대쪽 끝(front)에서 삭제가 일어남큐를 사용하면 데이터를 추가한 순서대

me4n

접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조후입선출(Last-In, First-Out, LIFO) 리스트가장 최근에 들어온 데이터가 가장 먼저 나감top(peek) 이라고 하는 한쪽 끝에서 모든 삽입, 삭제 연산이 일어나는 순서 리스트파이썬에서 스택을 이용

me4n

정렬된 데이터 집합이여야 함start = 집합의 시작 원소 위치end = 집합의 마지막 원소 위치mid = 집합의 중간 원소 위치데이터 개수가 n인 정렬집합 arr에서 target을 찾는것!strart ≤ end 일 동안 아래 3. ~ 5. 을 반복if arrmid =

roo333

Trie는 문자열을 빠르게 탐색할 수 있게해주는 트리형 자료구조이다.루트 노드가 되는 가장 최상위 노드에는 어떠한 단어도 들어가지 않고, 루트 아래 노드부터 문자열들의 접두사가 하나씩 나타나게 된다. 이러한 특징 때문에 트라이는 접두사 트리(Prefix Tree) 라고

roo333

Binary lifting이란 Binary Search와 Divded & Conquer와 비슷하게 O(logN)에 특정 값을 찾는 것이다. 주로 트리에서 사용된다.예를들어 현재 노드 V에서 K번째 조상 노드를 찾고 싶다하면 그냥 연산을 통하면 O(n)의 연산, 정확하게

roo333

이분 그래프에서 A 그룹의 정점에서 B 그룹의 정점으로 간선을 연결 할 때,A그래프의 하나의 정점이 B그래프 하나의 정점만 가지도록 구성된 것이 이분 매칭이다.이분 그래프 :: 정점을 두개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에

roo333

Strongly Connected Component

roo333

Number of Submatrices That Sum to Target해당글은 discuss에 있는 설명 글을 번역했음을 알립니다.다음 코드를 보고 한 번에 이해를 안되는 사람들을 위해 설명을 하려한다.이 삼중 반복문에서 무슨일이 일어 나는지 알아보기 위해 i=1,j

roo333

1. 플로이드-워셜(Floyd-Warshall) 알고리즘이란?

roo333

LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말하지만 최장 공통 문자열(Longest Common Substring)을 말하기도 한다.Subsequence와 Substring의 차이는 ABCD,ABED라는 두 문자열이 있을때 S

roo333

1. LIS란? 가장 긴 증가하는 부분 수열 구하기이다. 기본적으로는 다이나믹 프로그래밍을 이용하여 각각의 수를 모두 훑어 비교해가며 한 배열에다가 최장길이의 숫자를 저장하지만 이런 방식을 사용할 경우 시간 복잡도가 O(N^2) 나오므로 배열의 크기가 클 경우 사용

roo333

출처:https://www.youtube.com/watch?v=pSqmAO-m7Lk하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(single source and single destination shortest path problem)하나의