백준/문자열16 백준 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. 백준 12904 c++ "A와 B" -PlusUltraCode- https://www.acmicpc.net/problem/12904 [필자 사고] bfs 탐색을 하게 되면 말도 안되는 시간초과가 난다. 당여한 결과이다. 2^1000승은 말도 안되기 때문이다. 자세히 문제를 관찰하면 해당 문제는 그리디 탐색 즉 탐욕적 알고리즘을 통해 해결 된다는걸 알게 된다. 결국 정해진 결과는 하나이다. S에서 T로 가지말고 T에서 S로 가는 생각을 하게 되면 해결할 수 있다.이미 만들어진 T의 마지막 문자열은 결정되어 있는거다. 그래서 A라는 문자열이 있으면 해당 A를 지우고 B라는 문자열이 있으면 B를 지우고 뒤집으면 된다. 아래는 자세한 코드해설이다.[코드 해설]1. 프로그램 개요이 프로그램은 문자열 변환 문제를 해결한다. 주어진 두 문자열 str1과 str2에 대해, str.. 2025. 4. 1. 백준 4889 c++ "안정적인 문자열" -PlusUltraCode- https://www.acmicpc.net/problem/4889 [필자 사고]가로 문제 중괄호를 보고 스택 자료구조가 생각이 났다. 그래서 스택을 이용하여 풀 수 있을까 생각 하다가 다음과 같은 결론에 도달했다.짝이 있는 괄호들은 제외한다.짝이 없는 괄호중 열린 괄호의 갯수와 닫힌 괄호의 갯수를 구한다음괄호의 갯수에 2를 나눠주고 나머지를 더하는 형태로 해당 문제를 풀었다. 스택 자료구조와 그리디 알고리즘을 이용하여 쉽게 풀 수 있엇다.아래는 자세한 코드해설이다.[코드 해설]2. 게임 시작 함수 (Game_Start 함수)Game_Start() 함수는 문자열과 테스트 케이스 번호를 매개변수로 받아 처리한다. 문자열을 처음부터 끝까지 순회하며 {는 스택에 넣고, }를 만났을 때는 endGaro() 함수를.. 2025. 4. 1. 백준 2002 c++ "추월" -PlusUltraCode- https://www.acmicpc.net/problem/2002 [필자 사고]와 2시간 만에 해결한 문제이다.답을 볼 수도있었지만 몰입이라는 책에서 말해주듯이 계속 생각했다.그러다가 과부화가와서 밥을 먹고 릴렉스 된 상태에서 문제를 다시보니 해결할 수 있었다. 핵심은 간단하다. 이전 순서를 저장하는 vector 배열이 있고이후 변경된 myMap형태로 순서를 넣었다. 그리고 브루스트알고리즘을 이용하여 for문 전체탐색으 진행했고만약 탐색한 지역이 있따면 visited를 통해 방문 처리를 했다.갱신작업은 현재 문자열의 미래 인덱스와 다음 문자열의 미래인덱스의 순서가 바껴져 있으면 갱신하는 법으로 문제를 해결했다. 아래는 자세한 코드 해설이다.[코드 해설]1. 입력 처리 (Input 함수)Input() 함.. 2025. 3. 31. 이전 1 2 3 4 다음
