꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/WORDCHAIN DFS(Depth First Search) 알고리즘을 이용하여 오일러 서킷 혹은 오일러 트레일을 이용하여 풀어야하는 문제였습니다.오일러 서킷은 그래프의 모든 간선을 정확히 한 번씩 지나면서 시작점과 끝점이 같습니다.반면, 오일러 트레일은 오일러 서킷과 마찬가지로 그래프의 모든 간선을 정확히 한 번씩 지나지만 시작점과 끝점이 다릅니다.추가적으로 헤밀토니안 경로는 그래프의 모든 정점을 정확히 한 번씩 지나는 경로입니다. 알고리즘은 아래와 같습니다.1. 그래프를 생성할 때 핵심은 각 단어의 첫 글자와 마지막 글자를 정점으로 갖고 첫 글자에서 마지막 글자로 가는 간선을 단어로 잡는 것입니다.->checkE..

문제 링크입니다: https://algospot.com/judge/problem/read/DICTIONARY DFS(Depth First Search)를 이용한 위상정렬 문제였습니다. 알고리즘은 아래와 같습니다.1. 사전 순서대로 단어들을 받기 때문에 makeGraph 함수에서 알파벳의 우위를 가립니다.2. 위상정렬을 구하기 위해 모든 알파벳에 대해 DFS 함수를 호출합니다.3. DFS를 수행하면 알파벳의 우위가 역순으로 저장됩니다. 따라서 algorithm 헤더의 reverse 함수를 통해 뒤집어준 다음 순서대로 출력해줍니다.4. 만약 사이클이 존재한다면 위상정렬이 될 수가 없으므로 "INVALID HYPOTHESIS"를 출력해줍니다. 아래의 코드의 결과는 algospot 예제 출력과는 다른 형태입니다..

문제 링크입니다: https://algospot.com/judge/problem/read/SOLONG 트라이(Trie) 자료구조(=접두사 트리(prefix tree))를 사용하는 문제였습니다. 트라이를 간단하게 설명하자면 아래와 같습니다.정수나 실수 혹은 문자에 대해서는 BST(이진 탐색 트리)가 시간복잡도 O(logN)으로 훌륭하게 동작합니다.하지만 문자열에 대해서 BST를 사용한다면 문자열의 최대길이가 M일 경우 시간복잡도가 O(MlogN)이 되기 때문에 생각만큼 효율적이지 않습니다.트라이는 위와 같은 문제를 메모리를 희생하면서 시간복잡도를 O(M)으로 단축시켜줍니다.트라이의 중요한 속성은 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사(prefix)를 얻을..

문제 링크입니다: https://algospot.com/judge/problem/read/EDITORWARS 상호 배타적 집합(Union FInd)을 이용하여 푸는 문제였습니다. 알고리즘은 아래와 같습니다.1. 전형적인 Union Find 자료구조처럼 해당 노드의 루트를 찾는 find 함수와 집합들을 합치는 merge 함수를 정의해줍니다.2. 두 노드 사이가 적인지 판별하는 dis 함수와 아군인지 판별하는 ack 함수를 정의하는데 모순 발생 시 false를 반환하도록 반환형을 boolean으로 선언합니다.i) dis 함수에서 같은 집합에 속해 있으면 false를 반환하고, 적의 적은 아군이기 때문에 u와 enemy[v]를 합치고 v와 enemy[u]를 합친 뒤 서로를 적이라고 표시해줍니다.ii) ack ..

문제 링크입니다: https://algospot.com/judge/problem/read/MEASURETIME 입력하는 숫자의 수가 많기 때문에 삽입정렬을 이용해서 풀 경우 TLE가 발생하지만, 구간합을 간단하게 구할 수 있는 펜윅 트리를 이용해 문제를 해결합니다.각 원소 A[i]에 대해 A[0..i - 1] 구간에 A[i]보다 큰 숫자가 몇 개 있는지 알게 된다면 옆으로 몇 칸 움직일지 계산할 수 있습니다.따라서, 각 숫자의 출현 횟수를 저장하는 펜윅 트리를 만들면 AC를 받을 수 있습니다! #include #include using namespace std; //펜윅 트리의 구현, 가상의 배열 A[]의 부분 합을 //빠르게 구현할 수 있도록 한다. 초기화시에는 A[]의 //원소가 전부 0이라고 생각한..

문제 링크입니다: https://algospot.com/judge/problem/read/FAMILYTREE 구간 트리(Segment Tree) 문제이기 때문에 Algospot MORDOR(http://jaimemin.tistory.com/662) 문제처럼 RMQ(Range Minimum Query) 구조체를 이용해서 푸는 문제였습니다.두 노드의 촌수 계산을 위해서는 공통 조상 LCA(Least Common Ancestor)를 찾는 것이 핵심입니다.예를 들어 u와 v의 촌 수를 계산하기 위해서는 (u의 깊이와 + v의 깊이 - 2 * LCA(u, v)의 깊이)를 구하면 됩니다! 새그먼트 트리는 일렬로 늘어선 배열을 처리하는 자료구조이기 때문에 해당 알고리즘을 사용하기 위해서는 트리를 펴서 일렬로 만들어야..

문제 링크입니다: https://algospot.com/judge/problem/read/MORDOR 문제를 보면 간단히 시간 복잡도가 O(N)인 탐색 기법으로 최대 높이와 최소 높이의 차를 구하는 문제처럼 보이지만 요구하는 알고리즘의 시간복잡도가 O(logN)이기 때문에 구간 트리(Segment Tree)에 대한 개념을 모르면 풀 수 없는 문제였습니다.RMQ(Range Minimum Query) 클래스의 query 함수는 node가 표현하는 범위 array[nodeLeft..nodeRight]가 주어질 때 이 범위와 array[left..right]의 교집합의 최소치를 구해주기 때문에 최소 높이를 쉽게 구할 수 있습니다.이제 최대 높이를 구하는 것이 문제인데, minusHeight 벡터에 높이의 부호를..

문제 링크입니다: https://algospot.com/judge/problem/read/RUNNINGMEDIAN 수열의 크기가 정해져있지 않고 초기값과 다음 값의 공식만 주어졌기 때문에 ITES 문제(http://jaimemin.tistory.com/569)처럼 난수 생성기를 통해 숫자를 생성해야하는 문제였습니다.이후에는 숫자들을 정렬한 뒤 앞의 절반을 최대 힙에, 뒤의 절반을 최소 힙에 넣으면 최대 힙의 root에 중간값이 위치하게 됩니다. 따라서 아래와 같이 불변식을 세웁니다.1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.(수열의 길이가 홀수일 경우 하나 더 큽니다.)2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다. runningMedian 함수가 위 두 조건을 ..

문제 링크입니다: https://algospot.com/judge/problem/read/INSERTION 뒤에서부터 문제를 풀면 쉽게 접근할 수 있는 문제였습니다.마지막 숫자 A[N-1]이 왼쪽으로 몇 칸 움직였는지를 보면 A[N-1]에 어떤 숫자가 들어가야 하는지 알 수 있기 때문입니다.A[i]에 들어갈 수 있는 숫자들의 집합을 저장하기 위해 자료구조로 이진 탐색 트리를 사용할 수 있는데 알고리즘 문제를 풀 때는 직접 구현하는 것보다 보통 STL set나 map을 사용하지만 이들은 k번째 원소를 찾는 기능을 제공하지 않기 때문에 직접 구현한 자료구조 트립을 사용했습니다. 그냥 이진 탐색 트리를 구현했을 경우에는 오름차순이나 내림차순으로 자료가 제공이 된다면 linked list 형태를 띄기 때문에 탐..

문제 링크입니다: https://algospot.com/judge/problem/read/NERD2 문제 수를 x축, 라면 그릇 수를 y축으로 지정하여 좌표평면상의 점들로 사람들을 표현하면 이해하기 쉬운 문제였습니다.A라는 사람이 B라는 사람보다 푼 문제 수도 적고, 라면 그릇 수도 적다면 NERD가 아니므로 좌표평면에서 직사각형 내부에 점이 있으면 NERD가 아닙니다.그림으로 설명하자면,예제에서 주어진 참가자 4명에 대해 좌표평면 위의 점으로 표현했을 떄 노란색 안에 점이 있다면 NERD가 아니라는 것을 확신할 수 있습니다!또한, 지배당하지 않는 점들은 좌상단부터 우하단까지 계단식 모양을 형성하고, 이러한 특성을 갖기 떄문에 점이 추가되었을 떄 지배당하는지 여부를 쉽게 파악할 수 있습니다! 좌표평면의 ..