꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/FORTRESS 언뜻 보기에는 트리 문제로 보이지 않지만, 성벽끼리의 접촉이 없다는 조건에 주목하면 성이 계층적 구조로 구성되어 있음을 알 수 있습니다.이 문제에서 핵심은 트리 내에서 가장 긴 경로를 찾는 것이였습니다. 트리 내에서 가장 긴 경로는 다음과 두 가지 경로 중 최대인 경로입니다.1. 가장 긴 root ~ leaf 경로의 길이2. 가장 긴 leaf ~ leaf 경로의 길이 소스코드에서 //root를 최상위 노드로 하는 경로를 고려하자 if (heights.size() >= 2) longest = max(longest, 2 + heights[heights.size() - 2] + heights[heights..

문제 링크입니다: https://algospot.com/judge/problem/read/TRAVERSAL 소스코드에 앞서서 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)의 Pseudo Code를 간단히 소개하겠습니다. 전위 순회if (currentNode){ Visit(currentNode); Preorder(currentNode->leftChild); Preorder(currentNode->rightChild); }중위 순회if (currentNode){ Inorder(currentNode->leftChild); Visit(currentNode); Inorder(currentNode->rightChild)..

문제 링크입니다: https://algospot.com/judge/problem/read/HABIT 접미사 배열(Suffix Array)를 이용하여 푸는 문제였습니다.부분 문자열이 여러 번 출현할 경우 항상 인접한 접미사들의 접두사로 출현합니다. 즉, 배열에서 인접한 모든 접미사 쌍에 대해 최장 공통 접두사를 계산하면 두 번 이상 출현하는 부분 문자열의 최대 길이를 알 수 있습니다.주어진 문자열에서 부분 문자열 S가 출현하는 위치가 A 군데 있다면 S는 A개의 접미사의 접두사가 됩니다.(prefix of suffix)따라서 첫 번째 접미사와 마지막 접미사의 공통 접두사는 항상 S를 포함합니다. 종만북을 보면서 문자열 파트가 제일 어렵게 느껴졌던 것 같습니다.생소한 개념도 많이 나왔고 대부분의 사람들이 어..

문제 링크입니다: https://algospot.com/judge/problem/read/JAEHASAFE KMP 알고리즘을 이용해 푸는 문제였습니다.(종만북을 아무리 봐도 아직은 이해가 완벽히 되지 않습니다 ㅠ)금고 다이얼은 환형 문자열이기 때문에 해당 비교를 시작하는 인덱스를 idx라고 할 때 [..idx] 접두사와 [idx..] 접미사 모두 비교를 해야합니다.이럴 경우 답을 구하기 매우 어렵기 때문에 다이얼 문자열을 두배로 늘려서 KMP 알고리즘을 통해 반시계 방향으로 몇번 시프트해야하는지 찾아내는 것이 문제의 핵심이였습니다!시계 방향으로 시프트하는 함수는 따로 구현해도 좋지만 앞서 언급한 기능을 하는 함수에 매개변수만 뒤바꿔어 넘겨주면 쉽게 구할 수 있는 것을 알 수 있습니다.왜냐하면, dial[..

문제 링크입니다: https://algospot.com/judge/problem/read/PALINDROMIZE KMP 알고리즘을 통해 팰린드롬을 구성하는 가장 짧은 문자열의 길이를 구하는 문제였습니다. 알고리즘은 아래와 같습니다.1. 주어진 문자열을 입력 받은 다음 뒤집은 문자열을 만듭니다.2. 두 문자열을 합쳤을 때 접두사와 접미사가 최대로 겹치는 길이를 KMP 알고리즘을 통해 구합니다.3. "주어진 문자열의 길이(문자열 + 뒤집은 문자열) * 2 - 2번에서 구한 길이" 가 정답입니다. #include #include #include #include using namespace std; //N에서 자기 자신을 찾으면서 나타나는 부분일치를 이용해 pi[]를 계산 //pi[i] = N[,,i]의 접미사..

문제 링크입니다: https://algospot.com/judge/problem/read/NAMING 많은 사람들이 기피하는 문자열 알고리즘 KMP 알고리즘 문제였습니다.KMP 알고리즘의 자세한 설명은 종만북도 좋지만 http://blog.naver.com/kks227/220917078260에서도 상세하게 설명해주시기 때문에 참고하는 것을 추천합니다. 브루트 포스 기법을 통해 문자열을 찾을 경우 시간복잡도가 O(N*M)이지만, KMP 알고리즘을 사용할 경우 시간복잡도가 O(N+M)으로 향상되기 때문에 어렵더라도 많이 보면서 코드를 익히는 것이 좋을 것 같습니다!(문자열의 길이:M, 부분문자열의 길이: N) #include #include #include using namespace std; //N에서 자..

문제 링크입니다: https://algospot.com/judge/problem/read/ITES 문제에서 주어진 공식으로 배열을 미리 만든 다음에 결과를 구하면 쉽겠지만 입력값이 너무 많은 관계로 온라인 알고리즘(online algorithm)을 통해 문제를 풀어야합니다.온라인 알고리즘은 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘입니다.난수 생성기 RNG를 만든 다음에 큐를 통해 여태까지 주어진 숫자들의 합을 구합니다.반복문을 통해 난수를 큐에 입력하고 합을 구하는데 값이 초과하면 rear는 고정시키고 front를 한칸씩 앞으로 옮기면서 합을 다시 구하는 형식으로 결과를 구할 수 있습니다! #include #include using namespace std; const int..

문제 링크입니다: https://algospot.com/judge/problem/read/BRACKETS2 괄호의 순서가 올바르게 작성되었는지 확인하는 문제였습니다.스택을 이용하면 간단하게 풀 수 있는 문제이기 때문에 어렵지 않게 풀 수 있는 문제입니다. #include #include #include using namespace std; bool wellMatched(const string &formula) { //여는 괄호 문자들 const string opening("({["); //닫는 괄호 문자들 const string closing(")}]"); stack stk; for (int i = 0; i < formula.size(); i++) { //여는 괄호이면 무조건 스택에 push if (op..

문제 링크입니다: https://algospot.com/judge/problem/read/FENCE http://jaimemin.tistory.com/310와 동일하지만 스택을 이용하여 시간 복잡도를 O(NlogN)->O(N)으로 단축시킨 코드입니다. 판자의 높이를 벡터에 저장한 다음에 마지막에 0을 넣어줍니다.(이렇게 하는 이유는 판자의 높이가 오름차순으로 저장되어있을 경우 width의 오른쪽 끝을 못 찾기 때문입니다.)가장 왼쪽에 있는 울타리를 스택에 삽입하며 문제를 해결해가는데, 스택이 비어있거나 혹은 다음에 삽입하려는 울타리가 현재 스택 top에 있는 울타리보다 클 때는 넓이 비교를 하지 않고 바로 스택에 울타리를 push합니다.다음에 삽입하려는 울타리가 현재 스택 top에 있는 울타리보다 작으면..

문제 링크입니다: https://algospot.com/judge/problem/read/JOSEPHUS 직접 Circular Linked List를 구현해서 하는 방법도 있지만 간편하게 list 헤더파일에서 지원하는 list를 이용하고 list.end()에 도달시 list.begin()으로 옮겨주어 원형 리스트처럼 동작하게 구현했습니다. #include #include using namespace std; void josephus(int N, int K) { //리스트 list survivors; for (int i = 1; i 2) { //첫 번째 사람이 자살, erase()는 지운 원소의 다음 원소 반환 kill = survivors.erase(kill); //원형 연결리스트 흉내 if (kill ..