2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

반응형

정보/알고리즘 52

기하알고리즘] 회전하는 캘리퍼스(백준 10254)

캘리퍼스란? 캘리퍼스는 작은 물건의 지름,너비 등을 측정할 때 쓰는 도구로 두개의 평형한 변 사이의 길이를 측정하는 도구이다. 회전하는 캘리퍼스(Rotating Calipers) 알고리즘이란? 회전하는 캘리퍼스 알고리즘은 실제 볼록 다각형의 지름을 재는데 사용된다. 다각형을 따라 두 직선을 한바퀴 돌리면서 두 직선에 닿는 꼭지점들 간의 거리를 구하는 알고리즘이다. 백준 10254번 고속도로 문제를 기준으로 살펴 보자 https://www.acmicpc.net/problem/10254 10254번: 고속도로 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 www...

정보/알고리즘 2023.10.22

Persistent Segment Tree (PST)

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..

정보/알고리즘 2022.09.13

Dynamic Segment Tree

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

정보/알고리즘 2022.09.13

Meet in the middle (MITM)

Meet in the middle Meet in the middle 은 브루트포스 알고리즘을 사용해야 하지만 경우의 수가 브루트포스 알고리즘을 사용하기에 조금 클 때 사용 된다. 즉 브루트포스 알고리즘을 사용하되 이를 분할 해서 연산의 수를 최소화 하는 것이다. 예를 들면 N크기 배열 원소의 모든 조합을 고려해야 하는 문제가 있다고 하자. 이때 N이 20이라면 2^20(약 100만)개의 연산을 하면 된다. 하지만 만약 N이 40이라면 2^40 개의 연산을 수행하므로 초당 연산 수 1억번 이내에서 해결이 어렵다. 이때 MITM 알고리즘을 사용하게 되는데~ MITM 은 분할 정복과 비슷한 형태를 취하지만 분할정복은 작은 문제 해결을 통해 커다란 하나의 문제를 해결하는 반면~ MITM은 작은 문제 해결 + 알..

정보/알고리즘 2022.07.26

Suffix Array(접미사 배열)

컴퓨터 과학에서 접미사 배열(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

정보/알고리즘 2022.07.04

최소공통조상(LCA-Lowest Common Ancestor)

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 ..

정보/알고리즘 2022.01.22

문자열알고리즘-트라이(TRIE)

트라이의 정의를 위키백과의 내용을 인용하면 다음과 같습니다. 트라이(trie)는 컴퓨터 과학에서 탐색트리의 일종이다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 트라이 알고리즘이란? 문자열 변수를 비교하는데는 최악의 경우 문자열의 길이에 비례하는 시간이 걸릴 수 있습니다. N개의 원소를 갖는 이진검색 트리에서 원하는 원소를 찾으려면 O(lgN)번의 비교만으로 찾을 수 있습니다. 이러한 이진 검색 트리에서 착안을 하여 고안된 문자열 특화 자료구조가 바로 트라이(trie) 로 집합 내에서 원소를 찾는 작업을 O(M) 시간만에 할 수 있습니다. 그렇다면 어떻게 가능한지 다음을 살펴 보시죠~ 출처:위키백과 그림은 문자열집합 S={"A","to","tea","ted","ten","inn"..

정보/알고리즘 2022.01.02
반응형