목록 풀이 (2)
반응형

Stargazer

[백준(BOJ)] 10942번 : 팰린드롬? C++ 풀이(DP)

문제: 접근: 그냥 하나씩 접근해서 비교하여 푸는 방식으로 하면, 시간내로 풀지 못한다. 따라서 점화식을 이용해서 풀면 된다. 즉, DP로 풀면 시간내로 풀린다. 전략: 시간을 최소로 사용해야하기 때문에 데이터를 메모라이징하여서 저장한다. 점화식은 구간 [i,j] 가 있을때, i==j(구간길이 1)이면 true, 구간길이가 2일때, 입력데이터 input[i] == input[j] 가 같으면 true 아니면 false로 저장하고, 나머지 구간은 dp[i,j] = dp[i+1, j-1] && input[i] == input[j] 이면 된다. (이전 데이터를 이용해서, 양옆 한번만 비교하면 된다.) 코드: #include #include using namespace std; int n,m; vector su;..
Undergraudate basics(학부생 기초)/자료구조, 알고리즘 2022. 8. 2. 14:35
[백준] 1305번 : 광고 (KMP 알고리즘) c++ 풀이

접근: 전광판이 무한으로 연결되어서 나오는 형태의 광고이기 때문에 적어도 L 만큼은 광고 할 수 있음이 보장이 되어있다. 문제는 주어진 문자열에 대해서 어떤 광고를 말하는 것인지 최소 길이를 구하는 것이다. 문제의 예에서도 말했듯이, aabaaa 가 주어졌다면, aaba 는 광고가 가능한 최소 길이이다 중요한 것은 반복할 문자열이 그 뒤에 얼마나 겹치는 가이다. 그래서, 최소 길이를 구하려면, 길이 L 에서 최대한 겹치는 부분을 제외한 나머지 부분으로 구해야한다. 위 예로 들자면 aabaaa 처럼 뒤에 2개가, 길이 L이 주어졌을 때, 반복하면 최대로 겹치는 부분이다. 그렇기 때문에 저 2개를 제외한 나머지 부분이 반복해야 할 최소 길이가 된다. 전략: KMP 알고리즘을 이용하여, 하나씩 길이를 늘려가면..
Undergraudate basics(학부생 기초)/자료구조, 알고리즘 2022. 5. 29. 11:44
Prev 1 Next