Fly me to the Alpha Centauri 문제 링크 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 이 문제는 1년전에 풀어봤던 문제인데 이 때도 정말 고민하고 생각하면서 겨우 풀었던 것으로 기억한다. 근데 이번에는 풀다가 도저히 생각이 안나서 작년에 내가 푼 문제를 보았다. 쓰레기 짜식..... 할튼 알고보니? 쉬운 문제였다. 이 문제의 경우의 수를 잘 생각해보면 아래와 같이 나올 수 있다. 거리 방법 3 1 1 1 4 1 2 1 5 1 2 1 1 8 ..

소수의 값으로만 부분 집합을 구해서 연속합을 구하는 문제이다. 부분 집합의 연속합을 구하는 부분에서 당연히 투포인터가 쓰일 것이고 어떻게 소수 모음을 만들어 내는지가 중요한 포인트이다. 필자는 두달전에 한번 풀었고 다시 복습을 통해 풀었는데 소수를 구하는 방법히 전혀 달랐다. 그래서 안좋은 예와 좋은 예 두 코드를 작성해보겠습니다. 안좋은 예 에스트라네스의 체를 활용했는데 상당히 비효율적으로 코드가 작성되었다. 2부터 400000만까지 소수인지 확인하며 하나씩 추가해줬습니다. 더보기 #include #include int arr[4000002]; int setPrimeNumber(int num); int discoverCount(int N); int main(){ int index = 0, N; for(..

사실 이문제는 다른 사람들의 풀이를 봤다. 답을 보고 어떻게 이런생각을 하지...... 라며 감탄을한 기억이 난다. 여러 개의 추의 합 중 만들 수 없는 가장 작은 합을 구하는 문제이다. 추들을 정렬 후 더하면서 처음으로 합보다 큰 수가 나오면 다음 값을 만들 수 없게된다. 그간 합 + 1이 답이된다. #include #include #include using namespace std; int N; vector input(); int main(){ vector scale = input(); int base = 1; for(auto sc : scale){ if(base < sc) break; else base+=sc; } printf("%d", base); } vector input(){ scanf("%d..

백준 1786-찾기는 문자열 모음에서 하나의 문자열이 몇번 등장하는지 찾는 문제이다. KMP 기본문제라서 KMP를 공부하고나서 쉽게 풀었다. 사실 KMP만 알면 누구나 풀 수 있는 문제이다. 찾았을 때 begin+1을 한 이유는 문자열을 탐색할 때 index는 0부터 시작하지만 문제입장에서는 1번째 문자 부터 검사하기 때문이다. #include #include #include #include using namespace std; vector getPi(string hook); vector KMPSEARCH(string base, string hook); int main(){ string base, hook; getline(cin, base); getline(cin, hook); vector result ..

트라이는 문자열의 집합을 표현하는 트리 자료 구조로, 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있습니다. 문자열 집합 S={"BE", "BET", "BUS", "TEA", "TEN" }를 저장하는 트리의 예는 아래와 같습니다. 여기서 진한 노드들은 종료 노드들로 해당 위치에 대응되는 문자열이 트라이가 집합에 표현되어 있다는 것을 의미합니다. BE, BET 등을 나타내는 노드들은 종료 노드지만 TE의 경우에는 그렇지 않습니다. 트라이에서 중요한 점은 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사를 얻을 수 있습니다. 즉 각 노드별로 대응되는 문자열을 저장할 필요가 없습니다. 트라이의 한 노드는 자손 노드들을 가리키는 포인터 목록과 이 노드..

KMP 알고리즘을 배우기전 엄청 큰 문자열 더미에서 특정 문자열을 찾기 위해서는 아래와 같이 O(N*H)의 시간복잡도를 사용하여 찾았을 것이다. N은 찾을려는 문자열 H는 문자열 더미이다. for(int begin = 0; begin + N.size()