5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 예제 ABRACADABRA ECADADABRBCRDARA ans : 5 ------------------------------ UPWJCIRUCAXIIRGL SBQNYBSBZDFNEV ans : 0 LCS와 유사하지만 이 문제는 공통부분 문자열이 연속되어야 한다는 점이 다르다. 예를 들어 ABCD와 ABDC의 공통부분 문자열 중 BD는 존재하지 않는다. 풀이는 처음부터 LCS를 고려하고 생각했다. 그 외의 방법은 떠오르지도 않아서 일단 LCS처럼 2차..

5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 예제 2 3 911 97625999 91125426 5 113 12340 123440 12345 98346 ans : NO YES 한 번호가 다른 번호의 접두어인 경우가 있는지 체크하는 문제이다. 예를 들어 911과 9112314에서 911은 9112314의 접두어이므로 일관성이 없다고 판단한다. 1. 가장 간단하게 생각할 수 있는 방법으로 첫 문자열부터 끝까지 다 비교하는 방법을 생각했다. 시간제한은 1초이고 전화번호가 최대 10000개..

9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 예제 mirkovC4nizCC44 C4 ans : mirkovniz --------------------------- 12ab112ab2ab 12ab ans : FRULA 문자열에서 특정 문자열을 찾아 계속 삭제하는 문제이다. 삭제를 계속 반복하면서 삭제할 문자열이 남아있지 않을 때까지 완전탐색으로 풀면 시간초과가 뜬다. 따라서 처음 생각한 방법은 실제로 삭제를 하지는 않고 index만 다루어서 삭제했다 치고 푸는 것이었다. 이 방법은 삭제하는 시..

5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 예제 4 RDD 4 [1,2,3,4] DD 1 [42] RRD 6 [1,1,2,3,5,8] D 0 [] ans : [2,1] error [1,2,3,5,8] error 문제의 포인트는 생각보다 여러 가지가 있었다. 1. [1,2,3] 형태의 데이터를 가공하여 배열에 넣어야 한다. 처음부터 빈 배열이 들어오는 경우 예외 처리를 잘해줘야 한다. 2. 배열의 앞과 뒤에서 삭제가 빈번히 일어나므로 deque 자료형을 쓰는 편이 유리하다. 3. 빈 배열에 대해 D 연산을 수행하면 error를 출력하지만 R 연산은 수행해도 er..

코테를 준비하거나 대회를 준비하면 문자열에 절대 겁먹어선 안된다. 기초부터 꼭 알아야 할 메서드들까지 공부해 보자! C++에서의 문자열 관리법 1. string 클래스 string은 C++ 표준 라이브러리 클래스로 문자열을 동적으로 할당하고 관리한다. 내부적으로 동적 할당된 배열을 사용하여 문자열 데이터를 저장하며, 문자열의 길이도 함께 저장한다. 2. 동적 할당 문자열 길이에 따라 필요한 만큼의 메모리를 동적으로 할당한다. 이로 인해 문자열의 크기를 런타임에 조절한다. 3. 메모리 구조 Null-Terminated Strings 문자열을 null-terminated 형식으로 표현하는데, 문자열의 끝에 자동으로 null문자를 추가하여 문자열의 끝을 표시한다. 5. 메모리 관리 문자열 객체가 생성될 때 관..