본문 바로가기

Coding

 (195)
15482번 한글 LCS 9251번과 같은 LCS 문제. UTF-8로 인코딩되어있으므로 한글은 3바이트를 차지하고 있다. 즉, 한 글자당 크기 3의 사이즈를 차지하고 있기 때문에 9251번에서 1바이트씩 비교한 것과 달리 이번에는 3바이트씩 비교하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include #include #define MAX 3003 using namespace std; string str1; string str2; int dp[MAX][MAX]; int cnt; void LCS(){ size_t n=str1.size(); size_t m=str2.size()..
2661번 좋은수열 백트래킹 문제. 재귀 + 조건을 통해 문제를 해결 -> 좋은수열인지 나쁜수열인지 확인하면서 숫자를 하나씩 늘려나간다. ex) N=3 1 -> 11 -> 나쁜수열 -> 12 -> 좋은 수열 -> 121 -> 좋은수열 -> 이제 그만! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include #include #define MAX 81 using namespace std; int N; string str; char num[3]={'1','2','3'}; bool Check(string s, int cnt){ for(int i=1;i
11051번 이항 계수 2 이항 계수에 대해 알고 있다면 간단한 DP문제. 파스칼의 법칙을 이용했다. 이 법칙에 의해 dp(n,k) + dp(n,k+1) = dp(n+1,k+1) 라는 점화식을 구할 수 있다. -> n-1,k-1을 대입하면 dp(n-1,k-1) + dp(n-1,k) = dp(n,k) 라는 점화식 또한 구할 수 있다. 구한 점화식을 이용해 풀면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #define MAX 1001 #define mod 10007 using namespace std; int dp[MAX][MAX]; int N,K; void DP(){ for(int i=0;i
11722번 가장 긴 감소하는 부분 수열 간단한 DP 문제 11053번과 거의 같은 문제 123456789101112131415161718192021222324252627282930313233343536#include #include #define MAX 1001 using namespace std; int dp[MAX];int A[MAX];int N; void DP(){ int ans=0; for(int i=0;i
1759번 암호 만들기 백트래킹 기본 문제. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include #include #define visited true #define Non_visited false #define MAX 16 using namespace std; char graph[MAX]; int L,C; void dfs(int i, int consonants, int vowels, string str){ if(str.size()==L){ if(consonants
2959번 거북이 정렬만 하면 끝나는 문제. 정렬하고 1번째 숫자와 3번째 숫자를 곱한 값이 최대값이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #define MAX 4 using namespace std; int num[MAX]; void QuickSort(int start, int end){ if(start-end>=0){ return; } int pivot=start; int i=start+1; int j=end; while(istart && num[pivot]j){ int temp=num[j]; num[j]=num[pivot]; num[pivot]=temp; }else{ int..
11048번 이동하기 DP문제. 1. 1행과 1열의 값을 구해주고 DP 해결 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include #include #define MAX 1001 using namespace std; int N,M; int dp[MAX][MAX]; int sum[MAX][MAX]; void DP(){ for(int i=1;i
2146번 다리 만들기 간단한 BFS 문제. 1. 첫번째 섬을 방문 2. 방문한 섬을 체크 3. 방문한 섬에서부터 카운트하여 다른 섬에 도착하게 되면 종료 4. 방문한 섬을 제외하고 1~3번 반복 ps. 다른 섬을 방문하여 종료가 되었을때 아직 큐 안에 좌표값들이 남아있을 수 있다. 따라서 큐 또한 초기화해야한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114..

티스토리툴바