목록알고리즘 문제풀이/백준 (178)

홍시홍의 프로그래밍

[백준 1305] 광고

분류 : kmp 요구사항 kmp를 사용하여 접두사 접미사가 같은 길이 구하기 풀이 백준 찾기 문제를 풀때 pi배열을 구하는 거랑 동일하게 풀이한다 pi는 !현재 i 길이! 에서 접두사와 접미사가 몇개가 같은지 비교하는것이다 #include #include #include #include #include using namespace std; int pi[10001000]; string n; string m; int cnt=0; void GetPi(){ int nsize = n.size(); for(int i=1 ,j=0; i0 && n[i] !=n[j]) j= pi[j-1]; if(n[i] == n[j]){ pi[i]=++j; } } } int main(){ in..
알고리즘 문제풀이/백준 2020. 3. 28. 01:10
[백준 1786] 찾기

분류 : KMP 요구사항 Kmp를 사용하여 T문자열에 P가 몇번 나타나는지 출력 풀이 단순히 n*m으로 풀면 시간초과가 난다 kmp라는 O(n+m)이라는 시간복잡도를 가진 알고리즘 풀이한다 pi는 p배열이 현재 길이에서 몇개까지의 접두사와 접미사 같은지 저장해놓은 함수이다 while(j>0 && n[i] != m[j]) j=pi[j-1]; while(j>0 && m[i] !=m[j]) j= pi[j-1]; 이 두 부분은 같은 문자열을 찾았으면 똑같은거를 반복해서 찾지 않기위해 현재 i에서 부터 j를 변화시켜 몇개까지가 맞는가 확인하는것이다. 처음 접하는 문제라서 어렵다 #include #include #include #include #include using namespace std; int ans[10..
알고리즘 문제풀이/백준 2020. 3. 28. 01:09
[백준 1149] R, G, B거리

분류 : DP 요구사항 이웃해 있는 집이 같은 색깔으로 중복되지 않게 최소비용으로 집 색깔 선택하기 풀이 n번째 집을 선택했을때 가격이 최소이려면 6가지 경우는 고려하여야 한다 현재 집 + 이웃집까지의 최소(같은 색상X) if(color==1) ref = min(map[num][color] + func(num-1,color+2),map[num][color] + func(num-1,color+1)); else if(color==2) ref = min(map[num][color] + func(num-1,color-1),map[num][color] + func(num-1,color+1)); else if(color==3) ref = min(map[num][color] + func(num-1,color-1),m..
알고리즘 문제풀이/백준 2020. 3. 26. 21:36
[백준 11726] 2n 타일링

분류 : dp 요구사항 2*1, 1*2의 타일으로 n열의 타일을 구할 수 있는 경우의 수 구하기 풀이 1열은 세로 하나로 가능하다 2열은 세로 2개 혹은 가로 2개로 가능하다 3열은 1열에다가 2열을 붙이거나 2열에다가 1열을 붙였을 경우 가능하다 일반화 시켜보면 피보나치 수열처럼된다. d[n] = d[n-1] +d[n-2]가 된다 #include #include #include //#include "windows.h" #include #include using namespace std; int d[1014]; int main(){ int n; scanf("%d",&n); d[1]=1; d[2]=2; if(n>=3){ for(int i=3 ; i
알고리즘 문제풀이/백준 2020. 3. 26. 21:33
Prev 1 ··· 7 8 9 10 11 12 13 ··· 45 Next