문제https://www.acmicpc.net/problem/10830시간 제한메모리 제한solved.ac 티어1초256MB골드 4풀이 빠른 행렬 거듭제곱 문제이다. 큰 틀에서는 두가지의 알고리즘이 들어간다. 분할 정복을 이용한 빠른 거듭제곱 알고리즘과 행렬곱 알고리즘이다. 분할정복을 이용한 빠른 거듭제곱 알고리즘은 전에 풀이했던 것이 있으니 다음을 참조하자. https://codejin.tistory.com/114 백준 1629번 C언어 풀이https://www.acmicpc.net/problem/1629 1629번: 곱셈첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.www.acmicpc.net 단순히 계속 곱했다가는..
문제https://www.acmicpc.net/problem/5972시간 제한메모리 제한solved.ac 티어1초MB골드 5풀이 이 문제도 밀려있던 문제이다. 전형적인 최단거리 문제이다. 문제에서 사람 헷갈리라고 가는 길의 길이는 고려하지 않는다고 하지만, 간선 가중치를 여물의 양으로 따져야 하기에 결국은 최단거리 문제로 귀결된다. 우리가 잘 아는 다익스트라를 사용하도록 하자. 잘 쓰던 C++ 대신 자바를 쓴 이유는 당시에 컴퓨터에 깔려있는건 자바밖에 없었다 허허... 그래서 구현과 제출에 정말 애를 먹었던 기억이 있다.코드import java.util.*;import java.io.*;class Pair implements Comparable { public int destination, dist..
문제https://www.acmicpc.net/problem/14938시간 제한메모리 제한solved.ac 티어1초128MB골드 4풀이 이 문제 역시 최단경로 문제이다. 다만, 특정 정점을 시작점으로 잡는 것이 아니라 임의의 정점에서 시작했을 때, 수색 범위 내에 있는 아이템의 개수의 최댓값을 구하는 문제이다. 정점의 개수도 그렇고 간선의 개수도 모두 100 이하이기 때문에 모든 정점에서 다익스트라를 돌려도 되겠으나, 정점의 개수가 적기 때문에 플로이드워셜로 한번에 최단 거리를 구한 후, 각 정점에 대해 순회하며 최댓값을 구했다.코드#include #define endl '\n'using namespace std;vector> graph;vector item;int n, m;void input() { i..
문제https://www.acmicpc.net/problem/11725시간 제한메모리 제한solved.ac 티어1초256MB실버 2풀이이 문제의 풀이를 사용하는 알고리즘 문제를 공부하고 풀어본 적이 있어서 쉽게 푼 것 같다. LCA라는 알고리즘인데, 이 알고리즘을 사용하는 문제도 역시 블로그 글 쓰기에 밀려있는 문제들이다. 조만간 풀이하겠다. 언뜻 보면 어려워보일수 있다. 입력의 각 줄의 데이터가 가 부모-자식 순서라는 보장이 전혀 없기 때문이다. 정말 정점간 연결 정보만을 알려주기 때문이다. 트리는 아주 특수한 형태의 그래프이다. 트리는 계층 구조를 가지는 자료구조이지만, 동시에 사이클, 즉 순환이 없는 그래프이기도 하다. 이런 그래프는 어떤 정점을 고르더라도 트리가 될 수 있다. 순환 구조가 없기 ..
문제 시간 제한메모리 제한solved.ac 티어2초192MB골드 3풀이 이 문제 유형은 예전부터 도전해보고 싶은 유형이었다. 단순히 그래프를 탐색하여 최단경로를 찾는 것이 아닌, 벽을 부수거나 뛰어넘는 등의 지나갈수 없는 길을 조건적으로 지나가는 문제유형은 생각해야하는 것이 정말 많기 때문이다. 사실 전에 의도치 않게 이런 류의 문제의 풀이 일부를 지인에게 스포당했다. 같이 랜덤 실버 디펜스를 하고 있었는데, 이와 비슷한 문제를 시도했다가 실패했고, 지인에게 풀이법을 듣게 되었다. 하지만 그 지인의 말로는 이 풀이를 들었다고 이런 유형의 문제를 다 풀수 있는게 아니라는 말을 듣고 일단은 알겠다고 한 기억이 있다. 스포당한지 어언 5개월 후, 다른 문제인 이 문제를 풀게 되었다. 스포를 당해서 풀이법을 작..
문제 시간 제한메모리 제한solved.ac 티어0.5초128MB골드 5풀이 문제 제목이 "최소비용 구하기" 이길래 (왜인지 모르겠지만) 순간적으로 MST 문제인줄 알았다. 하지만 문제를 조금만 읽어보니 최단경로 문제임을 알 수 있었고, 간선 가중치가 모두 음수가 아니기 때문에 다익스트라로 처리하면 끝나는 문제이다.코드#include #define endl '\n'using namespace std;using pii = pair;int n, m, qst, qed;vector> graph;void input() { int st, ed, dist; cin >> n >> m; graph.resize(n + 1); for(int i = 0; i > st >> ed >> dist; graph[st].push_ba..
문제https://www.acmicpc.net/problem/15652시간 제한메모리 제한solved.ac 티어1초512MB실버 3풀이 역시 백트래킹 문제이다. 다만 이전에 풀었던 15650번 N과 M(2)과 비슷한 문제이다. 비내림차순이라는 단어가 나와서 내림차순이 아닌 상태의 수열을 출력하라는줄 알고 순간 놀랐지만, 오름차순이라는 말을 굳이 꼬아서 쓴 것이었다. 해당 문제는 중복을 허용하기 때문에 15650번과는 다르게 반복문의 범위를 이전에 선택한 값도 다시 선택할 수 있도록 했다.코드#include #define endl '\n'using namespace std;int n, m;void sol(int prev, int cnt, string output) { if (cnt == m) { cout..
문제https://www.acmicpc.net/problem/6593시간 제한메모리 제한solved.ac 티어1초128MB골드 5풀이 밀린 문제 정리하기이다. 짬짬히 정리하는 나 자신. 이대로만 가자. 문제만 읽어봐도 이 문제는 그래프 탐색문제임을 알 수 있다. 거기에 최단경로를 찾아야 하기 때문에 bfs를 쓰면 될 것이다. 특이한 점은 이 문제는 3차원 bfs라는 것이다. 2차원에서 시작점과 출구를 잇는 최단 경로를 찾는 것이 아닌, 3차원 공간에서 시작점과 출구를 이어야 하기 때문에, 위치정보를 저장하고 이동하는데 유의해야 한다.코드#include #define endl '\n'using namespace std;int l, r, c;vector> building;tuple st;void input..
