본문 바로가기
  • Eigenspace of Knowledge

전체 글54

[백준/12015/C] 가장 긴 증가하는 부분 수열 2 필독 : https://eigenarea.tistory.com/52 [백준/11053/C] 가장 긴 증가하는 부분수열처음에 문제를 보고 알고리즘을 생각하면 머리가 멍할 수도 있다. 문제 태그가 dp니까 생각해볼 수 있는 알고리즘은 주어진 수열에서 1,2,3,..로 길이가 제한된 수열에서의 LIS라는 부분문제를 풀eigenarea.tistory.com 이 문제는 저번 문제와 다르게 주어지는 수열의 크기가 굉장히 크다 (O(n^2))으로는 무리가 있다.그래서 이분탐색을 진행해주어야하는데, 전반적인 알고리즘의 개요는 이러하다. res[i]는 길이가 i+1인 증가수열 중에 끝이 가장 작은 수열의 끝이다.res를 유도하기 위해서는 리스트를 순차적으로 탐색해나가면서 만약 숫자 arr[j]이 res의 가장 뒤의 숫자.. 2025. 6. 21.
[백준/5582/C] 공통 부분 문자열 이 문제는 일반적인 LCS와 다르게 연속된 부분 문자열을 요구하고있다. 따라서 일반적인 LCS의 풀이는 서로 같은 문자가 아니더라도 왼쪽이나 위쪽의 dp를 계승하였지만, 이 문제는 그러한 경우 그냥 0으로 처리해버리고 두문자가 같을때만 대각선 방향으로 1을 더해 dp를 계승한다. #include #include int main() { char A[4001], B[4001]; scanf("%s", A); scanf("%s", B); int n = strlen(A); int m = strlen(B); static int L[4001][4001]; int ans = 0; for (int i = 0; i ans) { ans = L[i.. 2025. 6. 20.
[백준/9252/C] LCS2 이번엔 LCS문제에 더불어 가장 긴 공통수열을 찾아야한다. 필독 : https://eigenarea.tistory.com/55 [백준/9251/C] LCSLCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 일종의 dp문제이다. 두 문자열을 2차원으로 배열한 다음 순차적으로 늘려가면서 만약 [i][j]에서의 두 문자가 같으면 dp[i-1][j-1]에서 1을 추가해eigenarea.tistory.com 기본적인 매커니즘은 바뀌지않지만, 만들어진 dp의 리스트에서 가장 큰 수를 가진 위치에서 겹쳐왔던 문자들을 역추적해야한다.이는 그렇게 어려운과정은 아닌게, 어차피 두 문자열의 끝의 dp값이 가장 클수밖에 없기 때문에 그 지점을 시작점으로 잡으면 된다. 만약 현재지점의 두 문자.. 2025. 6. 20.
[백준/9251/C] LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 일종의 dp문제이다. 두 문자열을 2차원으로 배열한 다음 순차적으로 늘려가면서 만약 [i][j]에서의 두 문자가 같으면 dp[i-1][j-1]에서 1을 추가해주고 아니라면 dp[i-1][j]나 dp[i][j-1]중 가장 큰 것을 골라 이어나간다. #include #include int max(int a, int b){ if(a>b) return a; else return b;}int main(){ char str1[1001],str2[1001]; scanf("%s %s",str1,str2); int strlen1 = strlen(str1); int strlen2 = strlen(str2).. 2025. 6. 20.
[백준/14500/C] 테트로미노 첫번째시도 : DFS로 풀어보려고 했으나 예외가 있다. 바로 DFS로는 T형태의 테트로미노를 구현할수 없다는점이다. (일반화해보자면 DFS로는 중간에 분기할 수가 없음) #include int T = 4;typedef struct { int x, y;}CORD;int N, M, max = 0,tmp; //행/열 크기int field[500][500], cnt[4];CORD visited[4];int isinside(int i, int j){ if (0>i || i>=N || 0>j || j>=M) return 0; return 1;}int isvisited(int i, int j){ for(int k=0; kmax) max = tmp; visited[index].x= -.. 2025. 6. 3.
[백준/1629/C] 곱셈 첫번째시도:당연히 분할정복을 이용한 거듭제곱이니 분할정복을 이용해서 O(logN)으로 해결할 수 있다.그러나 주어진 숫자가 매우 클 수 있다는 점에서 매 연산마다 모듈러를 씌워주고 long long형식으로 저장해야함을 잊지말자#include int A,B,C;int mpow(int A, int B){ if (B==0) return 1; int M = mpow(A,B/2); if(B%2) return (A*M*M)%C; else{ return (M*M)%C; }}int main(){ scanf("%d %d %d",&A,&B,&C); printf("%d",mpow(A,B));} 결론 :위의 문제에 대한 해결이 된 코드이다#include int A,B,C;in.. 2025. 6. 1.
[백준/11053/C] 가장 긴 증가하는 부분수열 처음에 문제를 보고 알고리즘을 생각하면 머리가 멍할 수도 있다. 문제 태그가 dp니까 생각해볼 수 있는 알고리즘은 주어진 수열에서 1,2,3,..로 길이가 제한된 수열에서의 LIS라는 부분문제를 풀고, 만약에 그게 지금 위치의 전까지에서의 최선이라면 지금 위치의 값은 최선의 값+1이다. 이렇게 생각하면 시간복잡도가 O(n^2)이지만 이 문제는 수의 크기가 작기 때문에 괜찮다.+)부분문제의 수열을 초기화하는걸 까먹지 않도록하자 (절대로 내가 그거땜에 틀려서 하는말은 아니다..!) #include int main(){ int N,max=1; scanf("%d",&N); int arr[N],dp[N]; for(int i=0; iarr[j] && dp[i]max) max = dp[i]; .. 2025. 5. 30.
반응형

티스토리툴바