문제https://www.acmicpc.net/problem/11444시간 제한메모리 제한solved.ac 티어1초256MB골드 2풀이 피보나치 수열의 n번째 원소를 1000000007으로 나눈 나머지를 구하면 되는 아주 간단한(?) 문제이다. 단지 n이 최대 100경일 뿐이다...누가 봐도 O(logN)으로 줄일 필요가 있어 보인다. 피보나치 수열은 행렬로도 나타낼 수 있다고 들은 기억이 있어 해당 정보를 통해 피보나치 수열의 행렬식을 찾아보았다. 피보나치 수열의 행렬식은 다음과 같다. 이전에 풀었던 빠른 행렬 제곱을 이용하면 n이 아무리 커도 O(logN)의 시간복잡도를 통해 행렬의 제곱을 구할 수 있다. 빠른 행렬 제곱에 대해서는 다음 글을 참조하자. https://codejin.tistory.c..
문제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..
