문제https://www.acmicpc.net/problem/11725시간 제한메모리 제한solved.ac 티어1초256MB실버 2풀이이 문제의 풀이를 사용하는 알고리즘 문제를 공부하고 풀어본 적이 있어서 쉽게 푼 것 같다. LCA라는 알고리즘인데, 이 알고리즘을 사용하는 문제도 역시 블로그 글 쓰기에 밀려있는 문제들이다. 조만간 풀이하겠다. 언뜻 보면 어려워보일수 있다. 입력의 각 줄의 데이터가 가 부모-자식 순서라는 보장이 전혀 없기 때문이다. 정말 정점간 연결 정보만을 알려주기 때문이다. 트리는 아주 특수한 형태의 그래프이다. 트리는 계층 구조를 가지는 자료구조이지만, 동시에 사이클, 즉 순환이 없는 그래프이기도 하다. 이런 그래프는 어떤 정점을 고르더라도 트리가 될 수 있다. 순환 구조가 없기 ..
문제 시간 제한메모리 제한solved.ac 티어2초192MB골드 3풀이 이 문제 유형은 예전부터 도전해보고 싶은 유형이었다. 단순히 그래프를 탐색하여 최단경로를 찾는 것이 아닌, 벽을 부수거나 뛰어넘는 등의 지나갈수 없는 길을 조건적으로 지나가는 문제유형은 생각해야하는 것이 정말 많기 때문이다. 사실 전에 의도치 않게 이런 류의 문제의 풀이 일부를 지인에게 스포당했다. 같이 랜덤 실버 디펜스를 하고 있었는데, 이와 비슷한 문제를 시도했다가 실패했고, 지인에게 풀이법을 듣게 되었다. 하지만 그 지인의 말로는 이 풀이를 들었다고 이런 유형의 문제를 다 풀수 있는게 아니라는 말을 듣고 일단은 알겠다고 한 기억이 있다. 스포당한지 어언 5개월 후, 다른 문제인 이 문제를 풀게 되었다. 스포를 당해서 풀이법을 작..
문제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..
문제https://www.acmicpc.net/problem/16953시간 제한메모리 제한solved.ac 티어2초512MB실버 2 풀이1이 문제는 정말 생각할 수 있는 부분이 많은 좋은 문제라고 생각한다. 일단 문제를 보고 바로 든 생각은 그래프 문제구나 싶었다. 실제로 두 과정을 통해 a를 b로 만드는 최소 연산 횟수 + 1(a에서 b로 이동하는 최단경로)을 구하는 것이기 때문이다. a, b의 최댓값이 10^9로 약 2^30에 근접하고, 두 연산이 모두 곱하거나(2x), 곱하고 더하는 연산(10x + 1)이기 때문에 아무리 큰 케이스를 주더라도 연산은 30번에 근접할 것이다. 그리고, 나름의 최적화를 시도하여 큰 값부터 우선 처리하면, 더 빠르게 구할 수 있을거라고 생각하여 우선순위큐를 사용하여 bf..
