꾸준함

문제 링크입니다: 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://www.acmicpc.net/problem/3653 난이도가 높은 세그먼트 트리 응용 문제였습니다.많은 사람들이 펜윅 트리로 풀었지만 세그먼트 트리 알고리즘으로는 풀리지만 펜윅 트리 알고리즘으로는 풀리지 않는 문제들이 존재하기 때문에 세그먼트 트리 알고리즘을 이용하여 풀었습니다. 알고리즘과 코드는 lyzqm(https://lyzqm.blogspot.com/2017/07/segment-tree-3653.html?showComment=1531981580261#c7391195554365601508)님의 블로그를 참고하여 풀었습니다.기본적인 알고리즘은 아래와 같습니다.1. 배열을 M + N 크기로 설정하고 (M ~ N - 1)까지 1로 표시하고 (0 ~ M - 1)까지는 0으로 ..

문제 링크입니다: https://www.acmicpc.net/problem/10266 백준 11585번 속타는 저녁 메뉴(http://jaimemin.tistory.com/633)처럼 환형문자열에서 부분 문자열이 일치하는 경우가 있는지 확인하는 문제였습니다.숫자가 360,000까지 등장할 수 있기 때문에 길이가 360,000인 배열처럼 문자열(모두 0으로)을 생성하고 입력받는 숫자의 인덱스에 해당하는 부분만 1로 바꿔서 KMP 알고리즘을 적용하면 되는 문제였습니다! #include #include #include using namespace std; const int MAX = 360000 + 1; //N에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용해 pi[]를 계산 //pi[i] = N[..i]..

문제 링크입니다: https://www.acmicpc.net/problem/2357 백준 10868번 최소값(http://jaimemin.tistory.com/698)에서 maxTree만 추가로 정의해주면 되는 문제였습니다.많은 데이터를 입력 받기 때문에 개행할 때 endl 대신 "\n"을 이용해야합니다! #include #include #include using namespace std; const int INF = 1000000000 + 1; int N, M; struct minimumTree { //배열의 길이 int n; //각 구간의 최소치 vector minTree; minimumTree(const vector &array) { n = array.size(); minTree.resize(n *..

문제 링크입니다: https://www.acmicpc.net/problem/2042 새그먼트 트리를 이용하여 푸는 문제였습니다.종만북 코드에서는 LCA(Longest Common Ancestor)를 구하는 코드이기 때문에 http://jaimemin.tistory.com/662 코드에서 조금 수정을 해야했습니다.주의할 점은, 반환형을 int가 아닌 long long으로 해야 AC를 받을 수 있다는 점입니다. #include #include #include using namespace std; int N, M, K; struct segmentTree { //배열의 길이 int n; //각 구간의 최소치 vector pSum; segmentTree(const vector &array) { n = array...

문제 링크입니다: 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 벡터에 높이의 부호를..