본문 바로가기

BOJ7

LCA - Lowest Common Ancestor (최소공통조상) 기본문제 https://www.acmicpc.net/problem/11438 https://www.acmicpc.net/problem/1761 '트리'에서 두 정점간의 공통 조상 중 가장 가까운 조상의 번호를 찾는 알고리즘이다. O(logn) (0번노드가 첫 노드) 기본 버전이다. O(n) 코드 이해하기가 굉장히 쉽다. 하지만 사용하진 않을 것. LCA 알고리즘이 크게 어떻게 돌아가는지 파악하기만 하면 됨. int depth[MAX], parent[MAX]; void dfs(int curr) { vst[curr] = true; for (int next : adj[curr]) { if (!vst[next]) { depth[next] = depth[curr] + 1; parent[next] = curr; d.. 2019. 10. 1.
BOJ 2749 - 피보나치 3 (MOD=10^k꼴일 때 주기 이용) https://www.acmicpc.net/problem/2749 피보나치를 MOD로 나눈 나머지는 항상 주기를 갖는다. (피사노 주기라고 함) 그중 특히 MOD = 10^k (k>2) 인 경우 PRD = 15*10^(k-1)이다. fibo(n)의 값은 fibo(n%PRD)의 값과 같아진다. 피보나치를 dp를 이용하여 풀게되면 O(n)에 풀 수 있으므로 이 방법을 이용하면 O(MOD)라고 볼 수 있겠다. #include #include using namespace std; typedef long long ll; const int MOD = 1e6; const int PRD = 15e5; ll dp[PRD]; ll fibo(int k) { if (k > n; fill(dp, dp + PRD, -1); cout 2019. 9. 27.
BOJ 1194 - 달이 차오른다, 가자 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다. www.acmicpc.net 제약조건(열쇠,문)이 추가된 플러드필 문제이다 처음엔 큐에 방문노드위치(cy,cx)와 비트마스크를 이용한 현재 key, 그리고 visited배열을 넘겨주면서 열쇠를 먹으면 false로 초기화된 visited를 다음 .. 2019. 8. 6.
BOJ 2098 - 외판원 순회 TSP https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net #include #include #include using namespace std; const int INF = 1e9; int n, w[16][16], dp[16][1 2019. 8. 6.

티스토리툴바