-
[BOJ] 2611 : 자동차경주
2611 : 자동차경주 풀이 처음 문제를 보자마자 다익스트라 풀이를 떠올렸는데 문제를 다시 읽어보니 1번 노드를 거치지 않고 다시 원래 노드로 돌아 올 수 없다 이거 싸이클도 없고 완전 DAG잖아? 위상정렬해서 풀려고 했는데 생각해보니 dp로 풀 수 있잖아? 코드 #include <stdio.h> #include <vector> using namespace std; const int n_ = 1000 + 1; int n, m, dp[n_], route[n_]; vector<pair<int, int> > gph[n_]; int dfs(int now) { if (!dp[now] && now != 1) for (auto nxt :...
-
[일상] 웹알못 블로거의 신나는 웹 코딩
약 2시간 정도 삽질했는데, 결론부터 말하자면 구현은 실패 했다. 아이 신난다 사실 이 블로그가 카카오 테크 블로그에서 따온 블로그인데, 원래 검색 기능은 이렇게 구현되어 있었다: $('#search').submit(function (e) { e.preventDefault(); var q = $('#searchQueryEdit').val(); var url = 'http://search.daum.net/search?q=' + encodeURIComponent(q + ' site:tech.kakao.com'); window.open(url, '', '_blank'); }); 아니 무려 카카오에서 일하시는 분들이 검색을 짜기가 귀찮아서 웹으로 넘겼다고? 그럼 내가 한 번 해보지! 잘은 모르지만 대충 배껴서 만들면 아마 돌아갈거야 재앙의 시작 룰루 랄라~ ...
-
[BOJ] 1992 : 쿼드트리
1992 : 쿼드트리 풀이 분할정복을 하자 네모 크기가 1일 떄 까지 내려갔다가 올라오자 코드 #include <stdio.h> int n; char a[65][65]; void gogo(int x1, int y1, int x2, int y2) { char now = a[x1][y1]; if (x1 == x2 && y1 == y2) { printf("%c", now); return; } for (int i = x1; i < x2; ++i) { for (int j = y1; j < y2; ++j) { if (now != a[i][j]) { printf("("); gogo(x1, y1,...
-
[BOJ] 1753 : 최단경로
1753 : 최단경로 풀이 다익스트라를 짜자 우선순위 큐를 쓰자 코드 #include <stdio.h> #include <algorithm> #include <queue> #include <vector> using namespace std; const int v_ = 20000 + 1; const int INF = 987654321; struct edg { int idx, dst; edg() {} edg(int idx, int dst) : idx(idx), dst(dst) {} bool operator <(edg A)const { return dst > A.dst; } }; int v, e, s, dst[v_]; vector<edg> gph[v_]; void dijkstra() { for (int i = 0;...
-
[BOJ] 10844 : 쉬운 계단 수
10844 : 쉬운 계단 수 풀이 점화식을 세우자 dp[i][j] = 총 i 자릿수이고, 가장 큰 자릿수의 숫자가 j인 경우의 수 = dp[i-1][j-1] + dp[i-1][j+1] 끗! 코드 #include <stdio.h> const int mod = 1e9; int n, i, j, dp[101][11], ans; int main() { scanf("%d", &n); for (i = 1; i <= 9; ++i) dp[1][i] = 1; for (i = 2; i <= n; ++i) for (j = 0; j <= 9; ++j) dp[i][j] = (dp[i -...
-
[BOJ] 1260 : DFS와 BFS
1260 : DFS와 BFS 풀이 bfs를 돌리자! dfs도 돌리자! 코드 #include <cstdio> #include <queue> #include <cstring> using namespace std; int n, m, v, chk[1001], gph[1001][1001]; void dfs(int now) { chk[now] = 1; printf("%d ", now); for (int i = 1; i <= n; i++) if (!chk[i] && gph[now][i]) dfs(i); } void bfs(int now) { queue<int> que; que.push(now); chk[now] = 1; while (!que.empty()) { int now = que.front(); que.pop(); printf("%d ", now); for (int i =...
-
[BOJ] 1948 : 임계경로
1948 : 임계경로 풀이 문제를 다르게 생각해보자. 마지막에 도착하는 사람까지 도착을 하는 시간 이라는 문장은 결국 가장 먼 길을 선택하는 사람, 즉 최장 거리를 의미한다. 따라서 이 문제는 최장 거리와, 최장 경로들에 포함되는 모든 간선의 개수를 카운팅해서 출력하면 된다! 풀다보니까 이게 개수를 카운팅 할 때 뒤에서 부터 돌아야 할 것 같은데… 인접행렬이 아니라 백터를 써서 짰단 말이야 코드를 다시 짜긴 귀찮고 그래서 dp 배열을 아예 백트랙킹? 그런 느낌으로 구했다. get_max_len() 함수를 보면 일단 카운팅하기 전에...
-
[BOJ] 11758 : CCW
11758 : CCW 풀이 CCW 알고리즘의 연습문제이다. 식: S = (x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1) S > 0 : 반시계 방향 S = 0 : 일직선 S < 0 : 시계 방향 코드 #include <stdio.h> int main() { int x1, y1, x2, y2, x3, y3, S, ans = 0; scanf("%d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3); S = (x2 - x1) * (y3 -...
-
[BOJ] 머그컵 풀이
문제: https://www.acmicpc.net/contest/view/213 많은 도움 주신 스타트링크께 감사드립니다! A. 준오는 심술쟁이!! BOJ 백준 14437 준오는 심술쟁이!! 제한시간이 1초이기 때문에 단순히 3000 * 3000 * 25 dp를 돌렸다간 시간초과를 받는다. dp[문자열길이][s의 합] 일 때, 문자열 길이를 p, s 합을 q라고 하면 dp[p][q] = k가 0 ~ min(q, 25)일 때의 모든 dp[p-1][q-k]의 합 으로 점화식을 세워 해결할 수 있다. #include <iostream> #include <string> #define min(x, y) ((x)<(y)?(x):(y)) using namespace std; typedef long long ll; const int MOD =...
-
SIGPL Winter School 2017 3일차 정리
SIGPL Winter School 2017 3일차 정리 마지막 날 Type Check Val/Computation.Inductive/Fuction 4가지 룰이랑 Eval만 사용해서 체크함 logical한 step 4개의 룰만 있으면 거의 모든 증명을 할 수 있음 나머지 불가능한 것도 axiom? 추가하면 가능 프로그램 식을 그대로 읽으면 증명하는 거랑 똑같음 ->은 non dependent function forall은 dependent function ==forall, ->, =, P -> false, True, False, /|, |/, exists== 이것만 가지고 모든 set을 만들 수 있음 set이 바로 proposition (coq에서, m zigler set은 set prop는 prop)...