원당컴퓨터학원

동적계획법 알고리즘이란 동적계획법은 문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용하는 알고리즘 설계기법 - 전체 문제를 작은 문제로 단순화 한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식 동적계획법 알고리즘 설계 방법 1. 전체 문제를 작은 문제로 단순화한다. -> 부분문제를 정의 2. 재귀적인 구조를 활용할 수 있는 점화식을 만든다. 3. 작은 문제를 해결한 방법으로 전체 문제를 해결한다. 메모이제이션 기법 메모이제이션(Memoization)은 동적계획법에서 아주 중요한 개념이다. 함수의 값을 계산한 뒤 계산된 값을 배열에 저장하는 방식이다. 이러한 메모이제이션은 필요한 때마다 함수를 다시 호출하지 않고 값을 빠르게 가져 올 수 있다. 동적알고리즘 예시문제 www..

분할정복 알고리즘이란? 분할정복(Divide and conquer algorithm)은 그대로 해결 할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 대표적인 예로 퀵정렬 또는 합병정렬과 같은 알고리즘이 있다. 알고리즘을 설계하는 요령 - Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다. - Conquer : 나누어진 문제가 여전히 분할이 가능하면 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 정복한다. - Combine : : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다. ※ 문제를 제대로 나누면 conquer 하는 것이 쉽기 때문에 Divide 를 제대로 하는것이 가장 중요하다. 분할정복 알고리즘 예 function F(x): if F(..

컴퓨터 과학에서 접미사 배열(Suffix Array)란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. S = S[0]S[1]...S[n-1] 이라는 문자열이 있다고 하자. 이때 S[i,j] 는 i번째 문자부터 j번째 문자 까지 S의 부분 문자열이라고 하자. 문자열 S에 대한 접미사 배열 A는 S의 접미사들을 사전식 순서로 정렬 했을 때 접미사의 시작 위치를 저장한 정수 배열이다. 즉 A[i] 에 저장 된 내용은 사전순으로 i 번째인 S의 접미사의 시작 위치이다. 다시 말하면 문자열 S의 길이를 n이라고 할 때 , 0

Persistent 의 의미는 보존 된다는 의미인데 이 알고리즘의 핵심은 서로 다른 세그먼트 끼리 값을 보존 하며 공유하는 것이 핵심입니다. 예제 문제로 다음의 문제를 예로 들어 봅시다. https://www.acmicpc.net/problem/11012 11012번: Egg You are a president deeply loved by many folks in your country. Every time you go on a parade (which is your main job, what else should a president do), the folks would throw eggs at you — because you love eggs! The folks passionately send the..

Dynamic Segment Tree 는 다음과 같은 경우에 사용됩니다. 0으로 초기화 된 10억개의 수열이 있을 때 Q(10만)개의 질의에 대해 실시간으로 업데이트와 그에 대한 답을 구하는 경우 일반적인 세그먼트 트리로는 10억개의 공간을 모두 할당 할 수 없기 때문에 불가능 합니다. 하지만 이때 잘 생각해 보면 1번의 쿼리에 변경되는 노드의 갯수는 log2(10억) =(약)21의 갯수만 변경 되는 것을 알 수 있습니다. 따라서 최대 21 * Q(10만) 개의 공간만 있으면 가능하겠다는 아이디어에서 Dynamic Segment Tree 는 출발 합니다. 즉 다음과 같은 트리에서 2번 위치의 값이 변경이 된다면 노드의 갯수를 회색으로 색칠 된 3개만 만들어 놓겠다는 것이 Dynamic Segment Tr..

A* 알고리즘이란 A* 알고리즘은 주로 게임에서 플레이어를 목표 지점으로 이동 시킬때 사용하는 알고리즘이다. 클릭시 해당 객체가 클릭한 위치로 이동한다. 위의 데모는 클릭한 위치로 오크가 이동하는 것인데 데모에서는 A* 알고리즘이 사용되지는 않았습니다. 오크가 있는 위치에서 클릭한 위치까지 장애물이 없기 때문에 그냥 클릭한 위치를 바라보고 직진으로 이동하기만 하면 되거든요. 하지만 대부분의 게임에서는 장애물이 있고 장애물을 만나면 피해서 가야 되고 또한 목표물까지 최단거리로 찾아 가야 합니다. 이러한 최단거리 알고리즘은 BFS 와 다익스트라 알고리즘과 같은 그래프 알고리즘이 존재 합니다. BFS는 길을 가는 경로에 가중치가 없는 경로를 찾아 갈 때 유용하지만 즉 A 도시에서 B와 C가 연결 되었는데 B와..

유니온파인드(Union Find)란 - 대표적인 그래프 알고리즘으로 합집합 찾기 라는 의미를 가지고 있다. - 상호배타적집합(Disjoint-set) 이라고도 한다. - 여러개의 노드가 있을때 두개의 노드가 같은 그래프에 속하는지 판별하는 알고리즘 - 2가지 연산으로 이루어져 있다. 단계 1. 주어진 원소들이 서로 같은 집합에 속하는가를 알아내고(Find) 단계 2. 만약에 그렇지 않으면 같은 집합에 속하도록 추가하라(Union) 유니온파인드 구현방법 예) 위와 같은 경우 union(1,5),union(4,5),union(2,3),union(2,7),union(3,7),union(6,7) 을 표현한 그래프 이러한 그래프에 connected component 는 {0},{1,4,5},{2,3,6,7} 이렇..

정의 스택은 top 이라고 하는 한쪽 위치에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트 입니다. 후입선출(Last In First Out : LIFO) 의 특징을 가지고 있습니다. 스택에 원소 삽입 및 삭제 top 위치는 다음 데이터를 넣을 수 있는 위치를 가르킨다. push() 에서 top의 위치에 데이터를 입력 후 다음 데이터를 넣을 수 있는 위치로 이동한다. pop() 에서는 top의 위치를 이전의 위치로 먼저 이동 후에 그 위치의 값을 반환한다. 스택의 ADT(추상데이터타입) structure Stack objects: 0개 이상의 원소를 가진 유한 순서 리스트 functions: 모든 stack∈ Stack, item∈ element, max_stack_size∈ positi..

SCC(Strongly Connected Components) 란 SCC 알고리즘은 방향 그래프에서 그래프의 모든 정점들 간에 양방향으로 경로가 존재하면 강하게 연결 되었다고 하는데 이렇게 연결된 부분그래프를 찾는 알고리즘이다. 위의 그래프에서 a,b,e / f,g / c,d,h 와 같이 3개의 그룹을 찾는 알고리즘 SCC가 되기 위한 조건 1. 같은 SCC 내의 임의의 두정점 A,B 사이의 경로가 항상 존재한다. 2. 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이의 경로 A->B로 가는 경로와 B->A로 가는 경로는 동시에 존재할 수 없다.(SCC끼리는 사이클이 존재하지 않는다.) SCC 알고리즘 - 코세라주 알고리즘 1978년 코사라주가ㅏ 설명하고 1981년 미샤 샤리르가 출판. 두번의 깊이 ..

LCA(Lowest Common Ancestor) 란? LCA 란 최소 공통 조상을 찾는 알고리즘 - 두 정점 u,v 에서 가장 가까운 공통조상을 찾는 과정을 말한다. LCA(Lowest Common Ancestor) 구현 방법 위의 그래프에서 LCA((4,8)=1 이 됩니다. 가장 단순한 방법은 한번에 하나씩 자신의 조상을 찾아 올라가는 방법입니다. 4의 조상은 2,8의 조상은 7,2의 조상은 1,7의 조상은 3,1의 조상은 루트이므로 대기,3의 조상은 1 에서 순차적으로 하나씩 찾아가다가 누군가가 먼저 지나간 자리에 도착하면 그곳이 공통조상이 됩니다. 하지만 이 알고리즘은 최대 O(N) 의 시간이 걸립니다. https://www.acmicpc.net/problem/11438 11438번: LCA 2 ..