티스토리

Seungkwan's Lab.

검색하기

블로그 홈

Seungkwan's Lab.

seungkwan.tistory.com/m

deneb2016@gmail.com

구독자: 2

방명록 방문하기

주요 글 목록

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence) 어떠한 수열에서 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)를 찾는 문제는 꽤나 유명한 문제입니다. 다이나믹 프로그래밍을 공부할 때 예시로 자주 나오는 문제이고, 프로그래밍 대회에도 종종 출제됩니다. 비교적 쉬운 O(N^2) 알고리즘과 좀 더 어렵지만 효율적인 O(N log N) 알고리즘이 있습니다. 두 알고리즘을 소개하겠습니다. 또한 이 글에서 배열의 인덱스는 편의상 0이 아닌 1부터 시작하는걸로 하겠습니다. 3 2 5 2 3 1 4 부분 수열어떠한 수열에서 일부 숫자를 지워서 만들 수 있는 새로운 수열을 그 수열의 부분 수열이라 합니다. 가령 위의 수열에서 부분 수열은 [3], [5], [2,5], [3, 5, 3, 1], [2, 3, 4] 등이 있습니다.. .. 공감수 24 댓글수 14 2017. 3. 1.
강결합 컴포넌트 (Strongly Connected Component) 방향성 그래프에서 다음 조건을 만족하는 정점들의 집합을 강결합 컴포넌트 (SCC)라고 합니다.1. SCC내의 임의의 두 정점 u, v사이의 u → v 경로와, v → u 경로가 항상 존재한다.2. SCC내의 임의의 정점 u와, 외부의 임의의 정점 v 사이에, u → v 경로와, v → u 경로가 동시에 존재하는 경우는 없다.즉, SCC는 내부의 모든 정점에서 내부의 다른 모든 정점으로 갈 수 있는 최대 그룹이라고 할 수 있습니다.또한 모든 방향성 그래프는 한개 이상의 SCC들로 분리될 수 있습니다. 예를들어 이 그래프는 {1, 2, 4} , {3} , {5, 6} 이렇게 3개의 SCC들로 분리됩니다. DFS를 사용해서 어떠한 그래프를 강결합 컴포넌트들로 분리할 수 있습니다. DFS를 사용해서 강결합 컴포.. 공감수 2 댓글수 9 2017. 2. 13.
P-NP 문제 밀레니엄 문제중 하나인 P-NP 문제는 컴퓨터 전공자가 아닌 사람들에게도 꽤나 잘 알려진 문제입니다. P가 NP의 진부분집합인지 아닌지를 증명하는 100만 달러가 걸린 문제인데, 수십년동안 아무도 풀지 못했습니다. 이 문제는 컴퓨터 과학의 한 갈래인 계산 이론(Theory of computation)과 관련이 있는 문제인데, 계산 이론은 어떤 문제를 컴퓨터(알고리즘)로 풀 수 있는지 없는지, 풀 수 있다면 쉬운 문제인지 어려운 문제인지를 탐구하는 분야입니다. 아래의 내용은 계산 이론과 P-NP 문제에 대해 제가 공부한 내용을 정리한 것입니다. 저도 공부하는 입장이기 때문에 잘못된 내용이 있을수도 있습니다. 혹시 오류가 있다면 지적해주시면 감사하겠습니다. 1. 결정 문제 (Decision problem) .. 공감수 10 댓글수 2 2017. 2. 13.
이분 그래프와 홀수 사이클 어떠한 그래프 G가 이분 그래프이면 길이가 홀수인 사이클이 존재하지 않습니다. 반대로 어떠한 그래프에 길이가 홀수인 사이클이 존재하지 않는다면 그 그래프는 이분 그래프입니다. 이에 대한 증명을 해보겠습니다. 용어 설명 이분 그래프 (Bipartite Graph): 그래프의 모든 정점을 그룹 A, B로 나눌수 있고, 같은 그룹내에서의 간선이 없는 그래프 이 그래프의 정점들을 {1, 3, 5, 7}, {2, 4, 6} 으로 나누면, 같은 그룹내에서의 간선이 없으므로 이분그래프입니다. 예시는 방향성 그래프이지만, 비방향성 그래프에서도 정의는 같습니다. 강결합 컴포넌트 (Strongly Connected Component): 방향성 그래프에서 다음 조건을 만족하는 정점들의 집합을 강결합 컴포넌트(SCC)라고 합.. 공감수 1 댓글수 0 2017. 2. 12.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.