너와 나의 스토리

문제: https://www.acmicpc.net/problem/4196 문제풀이: dfs돌려서 stack에 정점들 쌓아주고 stack에서 정점 빼주면서 다시 dfs 돌리면서 visit해줌 stack에서 뺀 정점이 이미 visit되어 있으면 다시 빼고 아니면 res++해주고 dfs 돌림 * https://hororolol.tistory.com/94 > tc; while (tc--) { cin >> n >> m; memset(visit, false, sizeof(visit)); int res = 0; adj.clear(); adj.resize(n + 1); for (int i = 0; i > q >> w; adj[q].push_back(w); } for (i..

문제: https://www.acmicpc.net/problem/17209 문제 풀이: 현재 보는 사람이 새내기라면 그가 지목한 사람들은 헌내기 현재 보는 사람이 헌내기라면 그가 지목한 사람들은 새내기 즉, 항상 반대 이므로 두가지 경우를 다 돌려줄 필요가 없음 dfs를 이용하여 한 사람을 새내기(새내기=1)라고 두고 그가 지목한 사람은 헌내기(헌내기++) 그 헌내기가 지목한 사람은 새내기(새내기++) 해줘서 max(새내기,헌내기)를 결과 값에 더해준다. 소스 코드: int n,res,people[2]; bool visit[2001]; vector adj; void func(int cur,bool old) { if (visit[cur]) return; visit[cur] = true; for (int i..

문제: https://www.acmicpc.net/problem/13911 문제 풀이: 맥도날드가 있는 곳, 스타벅스가 있는 곳에서 각각 시작해서 다익스트라 돌림 각 정점을 입력 받을 때 pq에 (0,시작정점)으로 넣어넣고 시작하면 한번에 돌릴 수 있음 소스 코드: typedef pair P; int n, m, macs, stars, x, y, dist[2][10001],res=inf; bool visit[2][10001]; vector adj; typedef priority_queue Prior; Prior tmp,tmp2; void di(int cnt,Prior pq) { while (!pq.empty()) { int cur; do { cur = pq.top().second; pq.pop(); } w..

문제: https://www.acmicpc.net/problem/6543 문제 설명: bottom(G) 어떤 정점에서 출발하여 갈 수 있는 모든 정점에서 돌아 올 수 있는 정점들의 집합 ex) 5 5 1 2 2 3 3 1 3 4 4 5 1->2->3->1로 1,2,3이 bottom(G) 속할 것 같아 보이지만 3->4->5로 가고 4나 5에서 1,2,3으로 올 수 없으므로 bottom(G)에 속하지 않음 5는 출발한 정점이 없으므로 bottom(G)에 속함 문제 풀이: 알고리즘 - scc 1. dfs 돌려서 정점 stack에 쌓기 2. scc를 저장하는데 현재까지 저장된 res(scc)의 크기가 t라고 했을 때, 지금 rdfs를 돌려서 얻은 scc는 res[t]이후에 쌓이게 된다 그러므로 한 번 scc ..

문제: https://www.acmicpc.net/problem/1890 문제풀이: "경로의 개수는 2^63-1보다 작거나 같다." -> long long "메모리 제한: 128 MB" -> DP 이미 갔던 길 다시 안가고 그 지점에서 갈 수 있는 경우의 수+1 해주면 됨 * 함수 리턴 타입 확인 잘하자.... int func()해서 계속 틀림 ㅠㅅㅠ 소스코드: int n, arr[100][100]; long long dp[100][100]; long long func(int x, int y) { if (x == n - 1 && y == n - 1) return 1; if (x >= n || y >= n) return 0; long long& ret = dp[x][y]; if (ret != -1) ret..

문제: https://www.acmicpc.net/problem/11722 문제 풀이: https://hororolol.tistory.com/103 (BOJ) 11053 가장 긴 증가하는 부분수열 문제: https://www.acmicpc.net/problem/11053 문제풀이: 현재 위치 이전에 자기보다 작은 값 찾아서, 작은 녀석까지의 최대 개수+1 소스 코드: int n,arr[1001],dp[1001],res; int main() { ios::sync_with_stdio.. hororolol.tistory.com ㄴ 거의 같은 문제 부등호 방향만 바꾸면 됨 소스코드: 풀이1 - 시간 복잡도: O($n^{2}$) int n,arr[1001],dp[1001],res; int main() { ios:..

문제: https://www.acmicpc.net/problem/11053 문제풀이: 현재 위치 이전에 자기보다 작은 값 찾아서, 작은 녀석까지의 최대 개수+1 소스 코드: 시간복잡도: O($n^{2}$) int n,arr[1001],dp[1001],res; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; for (int i = 0; i > arr[i]; dp[i] = 1; for (int j = 0; j < i; j++) { if (arr[j] < arr[i]) { dp[i] = max(dp[i], dp[j] + 1); } } res = max(res, dp[i]); } c..

문제: https://www.acmicpc.net/problem/9251 문제풀이: ex) ACAYKP CAPCAK A C A Y K P 0 0 0 0 0 0 0 C 0 0 1 1 1 1 1 A 0 1 1 2 2 2 2 P 0 1 1 1 2 2 3 C 0 1 2 2 2 2 2 A 0 1 2 3 3 3 3 K 0 1 2 3 3 4 4 => 답: 4 행과 열의 첫 줄을 0으로 해둠 같은 문자를 만나면 대각선, 즉, 현재 (x,y)라면 (x-1,y-1) 값 +1 해준다 // arr[x][y]=arr[x-1][y-1]+1; 다른 문자를 만다면 자신의 왼쪽이나 위쪽 값 중 큰 값을 넣어줌 // arr[x][y]=max(arr[x][y-1],arr[x-1][y]); 가장 큰 값이 결과값이다. 소스 코드: strin..