NEMOSTAR5

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 길이가 최대 50인 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 ..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 www.acmicpc.net 문제 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량..

라빈 카프(Rabin-Karp) 알고리즘은 특이한 문자열 매칭 알고리즘입니다. 항상 빠르지는 않지만 일반적인 경우 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘입니다. 라빈 카프 알고리즘은 해시(Hash) 기법을 사용합니다. ◆ abacaaba의 해시 값 = 97 * 2^7 + 98 * 2^6 + 97 * 2^5 + 99 * 2^4 + 97 * 2^3 + 97 * 2^2 + 98 * 2^1 + 97 * 2^0 + = 24,834 물론 해시 값이 중복되는 경우도 발생할 수 있습니다. 이것을 충돌(Collision)이라고 하는데, 보통 발생률이 높지 않기 때문에 무시하고 넘아가는 것입니다. 실제로는 충돌이 발생하는 경우 포인터(Pointer)를 이용해 연결 자료구조를 이용해 해결합니다.(해쉬 체이닝 기..

KMP 알고리즘으로 대표적인 문자열(String) 매칭 알고리즘입니다. 문자열 매칭 알고리즘이란 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘입니다. KMP 알고리즘은 접두사와 접미사의 개념을 활용하여 '반복되는 연산을 얼마나 줄일 수 있는지'를 판별하여 매칭할 문자열을 빠르게 점프하는 기법입니다. 우리가 구해야 할 것은 위와 같이 접두사와 접미사가 일치하는 최대 길이입니다. 길이 문자열 최대 일치 길이 1 a 0 2 ab 0 3 aba 1 4 abac 0 5 abaca 1 6 abacaa 1 7 abacaab 2 8 abacaaba 3 위와 같이 접두사와 접미사를 구하게 되면 접두사와 접미사가 일치하는 경우에 한해서는 점프(Jump)를 수행할 수 있다는 점에서 몹시 효율적입니다. 이..