꾸준함

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

문제 링크입니다: https://www.acmicpc.net/problem/15881 겉보기에는 쉬운 문제 같지만 사실은 주어진 문자열에서 "pPAp" 형태를 띄는 부분 문자열을 찾는 KMP 알고리즘 문제였습니다.함정이 있기 때문에 문제의 주의사항을 주목해야합니다!단, 펜, 파인애플, 사과, 펜 순서로 연결된 네 개의 물건만을 펜-파인애플-애플-펜으로 인정하며, 하나의 펜이 두 개의 펜-파인애플-애플-펜에 포함될 수 없다. 또한 펜, 사과, 파인애플, 펜 순서로 연결된 네 개의 물건은 펜-파인애플-애플-펜이 아니다.즉, 기존에 풀던 KMP 알고리즘 문제와 달리 부분 문자열("pPAp")를 찾으면 마지막 p를 재활용하지 못하기 때문에 matched=pi[matched-1]로 초기화하지 않고 matched=..

문제 링크입니다: https://www.acmicpc.net/problem/11585 환형문자열에서 부분문자열이 몇 번 일치하는지 구하는 문제이므로 Algospot JAEHASAFE(http://jaimemin.tistory.com/599)의 문제와 상당히 유사한 문제였습니다.환형문자열 유형의 문제들은 주어진 문자열을 2배 즉, 한번 더 이어붙인 상태로 KMP 알고리즘을 수행하는 것이 핵심이였습니다.JAEHASAFE 문제와 달리 몇 번 일치하는지가 중요하므로 return kmpSearch2(doubleOriginal, target)[0]; 대신 return kmpSearch2(doubleOriginal, target).size();를 하여 일치한 횟수를 반환해주는 것이 중요했고 또 분수를 약분해야했기 때..

문제 링크입니다: https://www.acmicpc.net/problem/4354 백준 1701번 Cubeditor(http://jaimemin.tistory.com/629) 문제 처럼 접미사 배열(Suffix Array)를 사용하여 푸는 문제였습니다.문자열의 n 제곱이란 부분문자열을 n번 이어붙였을 때 해당 문자열이 나와야하기 때문에 접두사이면서 접미사인 부분문자열의 길이를 저장하는 벡터 pi를 구합니다.문자열이 S일 때 인덱스가 S.length() - 1 일 때 접두사이면서 접미사인 부분문자열의 길이는 이미 문자열 a를 n번 제곱했을 떄의 부분문자열의 길이일 수 있습니다.즉, S의 길이에서 인덱스가 S.length() - 1 일 때 부분문자열의 길이를 뺀 길이를 n번 제곱했을 때 S의 길이가 되게 ..

문제 링크입니다: 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가 아니라는 것을 확신할 수 있습니다!또한, 지배당하지 않는 점들은 좌상단부터 우하단까지 계단식 모양을 형성하고, 이러한 특성을 갖기 떄문에 점이 추가되었을 떄 지배당하는지 여부를 쉽게 파악할 수 있습니다! 좌표평면의 ..

문제 링크입니다: 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[..