기술 블로그

https://www.acmicpc.net/problem/5582 LCS 알고리즘하고 비슷했다. 다만, 나는 LCS처럼 접근하려고 표를 그리면서 구현하였었는데 즉, LCS처럼 값을 누적하면서 표를 작성하였는데, 같을 때의 처리가 애매해서 다른 코드를 참고하였다. 그 코드는 아래의 표처럼 오직 같을 때만 [행-1][열-1]의 값에 +1을 해주었다. 생각해보니 공통 부분 문자열의 최댓값을 구하는 것이므로 따로 누적(?)할 필요가 없었다. 초록색이 답이다. 1234567891011121314151617181920212223242526272829303132333435#include using namespace std; int dp[4040][4040] = { 0, }, answer = 0; string str1..

https://www.acmicpc.net/problem/17218 41, 42, 43, 45, 46, 47번 째 줄 순서 중요하다. 41 ~ 43 : 41, 42 두 경우 모두 아닌 경우에만 43이 실행되어야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include using namespace std; int lcs[44][44] = { 0, }; string str1, str2; int main(void){ string input1, input2; cin >> input1 >> input2; str1 = '0' + inp..

https://www.acmicpc.net/problem/9251 41, 42, 43, 45, 46, 47번 째 줄 순서 중요하다. 41 ~ 43 : 41, 42 두 경우 모두 아닌 경우에만 43이 실행되어야 한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include using namespace std; int lcs[1010][1010] = { 0, }; string str1, str2; int main(void){ string input1, input2; cin >> input1 >> input2; str1 = '0' + input1; str2 = '0' + i..

https://www.acmicpc.net/problem/16932 지난 번 코드 : https://hsdevelopment.tistory.com/265 다시 풀어보았다. 이번에는 map으로 풀어보았다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include using namespace std; bool visit[1001][1001] = { false, }; int N = 0, M = 0, g[1001 * 1001] = { 0, }, Map[1001][1001]..

https://programmers.co.kr/learn/courses/30/lessons/49994 단순 구현 문제이다. 방문 여부 배열(visit)이 4차원 배열인 것만 확인하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include using namespace std; bool visit[12][12][12][12] = { false, }; int solution(string dirs){ int answer = 0, sy = 5, sx = 5, ey = 5, ex = 5; for (auto i : dirs) { sy = ey; sx = ex; if (i == 'U..

https://programmers.co.kr/learn/courses/30/lessons/49993 C++ STL인 find()와 is_sorted()의 개념만 알고있으면, 매우 쉽게 풀 수 있다. 12345678910111213141516171819#include using namespace std; int solution(string skill, vector skill_trees){ int answer = 0; for (auto i : skill_trees) { vector v; for (auto j : skill) v.push_back(find(i.begin(), i.end(), j) - i.begin()); if (is_sorted(v.begin(), v.end())) ++answer; } re..

1.중복을 허용한 모든 경우의 수. 16번 째 줄의 i = 0으로 재귀적인 함수에서도 무조건 실행되고 있다. 재귀적으로 넘겨질 때 마다, 출발은 무조건 i = 0. 1234567891011121314151617181920212223242526272829303132333435#include using namespace std; vector v = { 1, 2, 3}; void backtracking(vector vc){ if (vc.size() == 3) { printf("\n"); for (auto i : vc) printf("%d ", i); return; } for (int i = 0; i

https://www.acmicpc.net/problem/4991 지난 코드 : https://hsdevelopment.tistory.com/192 구현과 백트래킹 그리고 BFS을 모두 혼합한 문제를 공부할겸 다시 풀어보았다. next_permutation()을 사용하지 않고, 구현하려고 하였으나, 이상하게 구현이 안 되었다. 그래서, 사용하였더니 또 틀렸다. 이유는 알고보니, 1 1o0 위의 경우와 나는 단순히 while()을 사용했었는데, 처음인 경우(1, 2, 3, 4..)가 있어서 do ~ while()을 사용해야 한다. 시간도 거의 1/3이나 줄었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445..