기술 블로그

https://www.acmicpc.net/problem/17213 다시 한 번 풀어보고, 복습할 문제이다. 즉, 생각해볼 문제이다. 복습! 백트래킹으로 풀었다. 그런데 아래 두 코드가 시간 차이가 꽤 났다. 여하튼 핵심은 두 코드 모두 nHr을 n+r-1Cr = n+r-1Cn-1로 바꾼 후에 진행하는 것이다. 그런데 첫 번째 코든느 vector size로 인해 시간이 꽤 걸렸다. vector의 size()가 시간이 꽤 걸리나보다. 정답이긴 하지만 시간이 오래 걸림 123456789101112131415161718192021222324252627282930313233343536373839404142#include using namespace std; int ans, N, M; void c(vector v..

https://www.acmicpc.net/problem/10835 처음에 단순 백트래킹으로 풀다가 시간 초과 났다. 그래서 다른 분의 코드를 보니 cache를 사용한 것에 힌트를 얻어 구현해보았다. cache를 깜빡하고 있었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include using namespace std; int n, cache[2002][2002]; vector l, r; int simulation(int left_idx, int right_idx){ if (left_idx == n || right_idx == n) return 0; int &get = cache[le..

https://programmers.co.kr/learn/courses/30/lessons/42898 예제를 아래처럼 엑셀에서 내 나름의 생각대로 숫자를 적으면서 보니 어떤 한 정점 기준으로 그 정점의 윗 칸과 왼쪽 칸을 더하였더니 아래처럼 나왔고, (n, m)=(행, 열)=(3, 4)의 칸의 숫자가 4여서 혹시나해서 구현해서 제출하였고 한 번에 맞았다. 솔직히 틀릴 줄 알았다. 12345678910111213141516171819202122232425262728293031323334353637#include using namespace std; #define Mod 1000000007 int Map[111][111] = { 0, }, dp[111][111] = { 0, }; int solution(in..

https://www.swexpertacademy.com/main/solvingProblem/solvingProblem.do 저번 코드 : https://hsdevelopment.tistory.com/45 다시 풀어보았다. 처음에 시간 초과 나길래 이유가 뭔가 했더니 하나의 점에 대하여, BFS를 몇 십 번이나 반복하고 있었던 것이었다.그리고 각 그 경우마다 처음부터 끝까지 BFS를 또 돌리고 있었다.(아래 짧은 코드 참고)12345for(int k = 0; k

https://programmers.co.kr/learn/courses/30/lessons/43162 기초적인 DFS 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738#include using namespace std; vector v[201]; bool visit[201] = { false, }; void dfs(int start){ visit[start] = true; for (auto i : v[start]) if (!visit[i]) dfs(i);} int solution(int n, vector computers) { int answer = 0; for (int i = 0; i

https://www.acmicpc.net/problem/tag/MCMF

https://www.acmicpc.net/problem/13460 지난 번 코드 : https://hsdevelopment.tistory.com/3 다시 풀어보았다. 계속 10 초과의 숫자들이 출력되길래 이상했었다. 85번 째 줄의 if문이 무시되는 상황이었다. 알고보니 쓰레기 값이었다. 그래서 88번 째 줄을 추가해줬더니 통과되었다. 핵심은 빨간 구슬, 파란 구슬 둘 다 O의 위치에서 계속 있으면서 queue가 empty() 될 때 까지 return하지 않는 것이다. 그래야 88번 째 줄에 의해 return -1;이 될 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525..

https://www.acmicpc.net/problem/1958 3차원으로 확대되었다. 기본적인 구현 방식은 일반적인 2개의 문자열에 대한 LCS와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include using namespace std; int lcs[101][101][101] = { 0, }; string str1, str2, str3; int main(void){ string input1, input2, input3; cin >> input1 >> input2 >> input..