피너클의 it공부방

1533번: 길의 개수https://www.acmicpc.net/problem/1533 행렬을 이용한 거듭제곱으로 풀었다.이 문제를 풀기전에12850번: 본대 산책2대충 이런 문제를 풀고오면 쉽다. matrix[1][2] = 1 이라면 1에서 2로 가는 길이 있다는 의미다.matrix[2][3] = 0 이라면 2에서 3으로 가는 길이 없다는 의미다. 이를 기본으로 생각해보자.문제에서는 5이하의 숫자로 입력이 들어온다.matrix[1][2] = 5라면 1에서 2까지 가는데 5의 시간이 걸린다는 의미이다.이걸 조금만 변형할것이다.정점은 무조건 5를 곱한 수로 생각한다.이전에 matrix[1][2] = 1이었다면이제는 matrix[1 * 5][2 * 5] = 1으로 생각하는 것이다.이러면 01001110대충..

12850번: 본대 산책2https://www.acmicpc.net/problem/12850 이건 이해하는것부터 힘들었다./*정보과학관 : 0전산관 : 1신양관 : 2미래관 : 3진리관 : 4한경직기념관 : 5학생회관 : 6형남공학관 : 7*/long long m[8][8] = { {0, 1, 0, 1, 0, 0, 0, 0}, {1, 0, 1, 1, 0, 0, 0, 0}, {0, 1, 0, 1, 1, 1, 0, 0}, {1, 1, 1, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 1, 0}, {0, 0, 1, 1, 1, 0, 0, 1}, {0, 0, 0, 0, 1, 0, 0, 1}, {0, 0, 0, 0, 0, 1, 1, 0}};먼저 배열로 그래프를 그려줬다.m[1][2] = 1이라면 ..

nanasin120/a-star-algorithm-in-web: 웹에서 A* 알고리즘 만들어보기 GitHub - nanasin120/a-star-algorithm-in-web: 웹에서 A* 알고리즘 만들어보기웹에서 A* 알고리즘 만들어보기. Contribute to nanasin120/a-star-algorithm-in-web development by creating an account on GitHub.github.com 나름 잘 작동된다.

8979번: 올림픽https://www.acmicpc.net/problem/8979 그냥 정렬 문제다. long long n, k;vector> v;사용할 변수다.v에는 가 들어간다. int main(){ cin >> n >> k; for (int i = 1; i > a >> b >> c >> d; v.push_back(make_tuple(b, c, d, a)); } long long sum = 0; sort(v.begin(), v.end(), cmp); for (long long i = 0; i (v[i]) == k) break; sum++; } cout 그냥 입력받고 정렬하고 번호가 k가 나올때까지 반복문 돌린뒤sum+1을 출력하면 된다. bool cmp(tuplea, tupleb) { if (..

10217번: KCM Travelhttps://www.acmicpc.net/problem/10217 dp로 풀었다. int n, m, k;vector>> graph[101];int cache[101][10001];사용할 변수들이다. int test; cin >> test; while (test-- > 0) { cin >> n >> m >> k; graph->clear(); memset(cache, -1, sizeof(cache)); for (int i = 0; i > u >> v >> c >> d; graph[u].push_back({ v, {c, d} }); } int s = solve(1, m); if (s == 987654321) cout main에서 돌리는 것들이다.graph는 ..

20437번: 문자열 게임 2https://www.acmicpc.net/problem/20437 그냥 풀었다. int test; cin >> test; while (test-- > 0) { cin >> str; cin >> k; vector arr[27];arr은 각 알파벳의 위치가 들어간다.arr[0]에는 a의 위치들이 들어간다. int len = str.length(); for (int i = 0; i 위치들을 넣어준다. int ans_min = 987654321, ans_max = -1; for (int eng = 0; eng 그리고 위치들에서 k만큼 떨어진놈들의 길이를 구해주면 된다. if (ans_min == 987654321) cout 출력하면 끝이다. #include #..

15927번: 회문은 회문아니야!!https://www.acmicpc.net/problem/15927 그냥 풀었다. 가장 긴 팰린드롬이 아닌 문자열을 구하는 것이니 아주 간단하게 생각했다. 만약 주어진 문자열이 팰린드롬이 아니라면? 주어진 문자열의 길이를 출력하면 된다.만약 주어진 문자열이 팰린드롬이라면? 주어진 문자열의 길이 -1 을 출력하면 된다. 팰린드롬에서 하나를 뺏는데도 팰린드롬인 경우는 전부 같은 문자인 경우밖에 없다.이 경우는 따로 빼줬다. cin >> str; int len = str.length(); char c = str[0]; bool chk = true; for (int i = 0; i 전부 같은 문자인지 확인해주고 맞다면 -1을 출력한다. else { int start = 0..

3392번: 화성 지도https://www.acmicpc.net/problem/3392 세그먼트 트리랑 스위핑으로 풀었다.x축을 기준으로 정렬해서 왼쪽부터 오른쪽으로 스위핑할것이며세그먼트트리고 현재 활성화되어있는 y축의 길이를 한번에 구할것이다. int n;vector> v;long long segtree[4 * 30000];long long cnt[4 * 30000];사용할 변수들이다.v로 입력을 받고 {x축, y1축, y2축, 시작인지 종료인지} 이렇게 입력받는다.segtree에는 범위 안에 활성화된 y축의 길이가 들어가고cnt에는 해당 범위가 활성화 되었는지가 들어간다. 0보다 크면 활성화 된거다. cin >> n; for (int i = 0; i > a >> b >> c >> d; v.push..

13511번: 트리와 쿼리 2https://www.acmicpc.net/problem/13511 lca로 풀었다. 문제에서 2개의 값을 구해야 한다.경로의 비용과, 경로에 존재하는 정점중 k번째 정점 둘다 기존의 lca를 개조해서 풀수있다. int n, m;vector> graph[100001];long long parent[21][100001];long long weight[21][100001];int depth[100001];사용할 변수들이다.대부분 기존의 것에서 사용하는 것이며 weight만 추가된것이다.weight는 당연히 비용이다. int main(int argc, char** argv){ std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); ..

14868번: 문명https://www.acmicpc.net/problem/14868 bfs와 유니온 파인드로 풀었다. int n, k, cnt = 0;int parent[2001 * 2001];int arr[2001][2001];int dx[] = { 1, 0, -1, 0 };int dy[] = { 0, 1, 0, -1 };사용할 변수들이다.arr[10][10]의 parent는 parent[10 * 2001 + 10] 이런식으로 나타낼것이다.int union_find(int v) { if (parent[v] == v) return v; else return parent[v] = union_find(parent[v]);}일반적인 유니온 파인드 코드다.void union_make(int u, int v) ..