백준/문자열16 백준 16120 c++ "PPAP" -PlusUltraCode- https://www.acmicpc.net/problem/16120 [필자 사고]PPAP를 만나면 p로 바뀌는 어쩌면 탐욕적 알고리즘과 유사하다.결과를 이용하여 역추적하는 느낌?? 필자는 해당 문제를 stack 을 이용하여 문제를 해결했다. 특정 idx를 설정하여 해당 문자열이 현재 어느 위치인지 각인 시켜줬다.약간 구현 문제 같은 느낌이 들었다. 아래는 자세한 코드 해설이다.[코드 해설] 데이터 구조stack를 사용하여 문자를 하나씩 처리하며 상태를 저장합니다.Node는 문자와 해당 문자가 PPAP 패턴 중 몇 번째 위치인지를 나타내는 인덱스를 함께 저장합니다.예를 들어 P가 PPAP의 첫 번째 등장이라면 인덱스 1, 그 다음 P는 2, A는 3, 마지막 P는 4.핵심 변수flagIdx: 현재까지 발견.. 2025. 4. 7. 백준 1958 c++ "LCS 3" -PlusUltraCode- https://www.acmicpc.net/problem/1958 [필자 사고]LCS 에서 차원이 늘어난 문제이다.핵심 원리는 동일하다같은 문자열이 있으면 [i-1][k-1] 의 값에 1을 더해주고다른 문자열이면 그동한 만든 갯수의 최대값을 갱신하면서 오면 된다.다만 필자가 이 문제를 풀면서 실수한 점은 string str1 에서 str1.insert(0," "); 으로 앞부분에 빈공간을 넣어준뒤str1.size() 형태로 접근해야되는데 주의하자. 아래는 자세한 코드 해설이다.[코드 해설] DP 테이블 초기화세 개의 문자열이 각각 최대 길이 100이기 때문에, 크기가 101x101x101인 3차원 정수 배열을 만듭니다.이 배열의 각 위치는 dp[i][j][k]라고 했을 때,문자열 1의 i번째 문자까지, .. 2025. 4. 3. 백준 1013 c++ "Contact" -PlusUltraCode- https://www.acmicpc.net/problem/1013[필자 사고]regex 정규식 라이브러리를 이용하면 쉽게 풀 수 있다.필자는 정규식 관련해서 처음 보는 지식이였다.이런 알고리즘도 있구나 정도로만 하고 넘어가야 겠다.[코드 해설]프로그램의 흐름은 다음과 같다:입력으로 테스트 케이스의 개수를 받는다.테스트 케이스 수만큼 반복해서 문자열(0과 1로만 구성)을 입력 받는다.입력받은 문자열이 정규 표현식 (100+1+|01)+의 형태를 정확하게 만족하는지 검사한다.여기서 (100+1+)는 1 다음에 0이 최소 두 개 이상 나오고 다시 1이 최소 하나 이상 나오는 패턴을 말한다.예시: 1001, 1000011, 10001 등|는 또는(OR)의 의미다.(01)은 정확히 0 뒤에 1이 오는 패턴이다.끝.. 2025. 4. 3. 백준 17609 c++ "회문" -PlusUltraCode- https://www.acmicpc.net/problem/17609 [필자 사고]하나하나 브루스알고리즘을 이용하면 시간초과가 난다.팰린드롬 알고리즘 하면 투포인터가 생각이 났다. 그러나 이 문제에서 하나의 문자열을 삭제할시 조건도 있어서 어떻게 이 난관을 돌파할 지가 고민이였다.생각해보니 처음 idx 와 끝idx를 비교해 가면서 만약 서로 다른 글자가 만날시 처음 idx +1 혹은 endIdx -1 둘중 하나의 인덱스를 옮긴 뒤 회문 함수를 실행시켜서 성공하면 회문 아니면 종료 형태로 문제를 해결했다. 아래는 자세한 코드해설이다.[코드 해설]입력받은 문자열이 완벽한 회문인지(앞뒤로 읽었을 때 같은지), 아니면 한 글자만 삭제하면 회문이 되는지 판단하는 코드입니다.먼저 입력받은 문자열을 양 끝에서부터 가.. 2025. 4. 3. 이전 1 2 3 4 다음
