전체 글341 백준 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. 백준 5582 c++ "공통 부분 문자열" -PlusUltraCode- https://www.acmicpc.net/problem/5582 [필자 사고]LCS 즉 최장 공통 부분수열과 최장 공통 부분 문자열 차이를 알아야 풀 수 있다.전자는 문자열이 붙어있지 않아도 된다. 그냥 존재하기만 하면된다.그래서 문자열이 같으면 dp[i][k] = dp[i-1][k-1] +1 을하고같지 않다면 max(dp[i-1][k], dp[i][k-1]) 형태로 업데이트하면 된다. 근데 최장공통 부분 문자열은 순서가 중요하므로같으면 전자와 같은 형태로 식을 만들고\같지 않다면 이전 기록들은 필요없으므로 dp[i][k] =0 으로 해놔야된다. 아래는 자세한 코드해설이다.[코드 해설]2. 입력 처리 (Input 함수)Input() 함수는 사용자로부터 두 문자열을 입력받고, 이를 각각 str1과 str.. 2025. 4. 2. 이전 1 2 3 4 ··· 86 다음
