문제https://www.acmicpc.net/problem/9177시간 제한메모리 제한solved.ac 티어1초256MB골드 4풀이 dfs + dp로 풀었다. 첫번째 단어를 a, 두번째를 b, 세번째를 c라고 하자. c의 첫번째 글자은 a의 첫번째 글자이거나, b의 첫번째 글자일 것이다. 둘다일수도 있다. 현재 사용된 이 알파벳이 a일때와 b일때를 구분해서 계속 dfs로 들어가면서, 최종적으로 c를 만들 수 있는지를 판단한다. dfs를 하면서 지금 사용해야하는 a와 b, c의 인덱스를 인자로 넘겨준다. 이때, 재귀를 하면서 a, b의 같은 인덱스를 여러번 탐색할 수도 있다. 예를 들어, 다른 탐색에서 a와 b의 인덱스가 각각 1, 2일때 불가능함을 알았을때, 다른 경로로 1, 2에 다시 왔다면, 볼 이..
문제https://www.acmicpc.net/problem/15681시간 제한메모리 제한solved.ac 티어1초128MB골드 5풀이 트리를 배웠다면 아주 간단한 문제이다. 쿼리로 들어오는 정점을 루트로 가지는 서브트리의 정점의 개수를 구하는 문제이다. 풀이방법은 간단하다. 입력으로 들어온 루트노드로부터, 자식 노드로 dfs하며, 정점의 개수를 저장하고 세어준다. 이때, 모든 정점은 적어도 자기 자신을 트리로 가지고 있기 때문에, 서브트리의 정점 개수를 저장할 배열을 1로 초기화한 후, 각 서브트리로 재귀하며 개수를 세어준다.코드#include #define endl '\n'using namespace std;int n, r, q;vector> tree;vector query, child;void in..
문제https://www.acmicpc.net/problem/1167시간 제한메모리 제한solved.ac 티어2초256MB골드 2풀이 이 문제는 정말 며칠동안 고심하고 해결한 문제이다. 이 문제는 뭔가 무엇도 참조하지 않고 내가 직접 풀어보고 싶다는 욕망이 들었고, 이를 실제로 행한 문제이다. 처음에는 별 생각없이 정점의 개수도 체크하지 않고 플로이드 워셜을 돌린 후, 트리의 지름을 찾고자 했다. 하지만 정점의 개수가 10만개인데 당연히 불가능한 풀이였고, 바로 폐기한 방법이다. 두번째는 내가 풀이한 방법이다. 임의의 정점을 골랐을 때, 트리의 지름을 구성할 때 내가 선택한 정점이 트리의 지름에 낄 수도 있고 아닐수도 있다. 정확히 말하면, 트리의 지름은 내가 현재 위치한 정점을 사용할 수도 있고, ..
문제https://www.acmicpc.net/problem/11725시간 제한메모리 제한solved.ac 티어1초256MB실버 2풀이이 문제의 풀이를 사용하는 알고리즘 문제를 공부하고 풀어본 적이 있어서 쉽게 푼 것 같다. LCA라는 알고리즘인데, 이 알고리즘을 사용하는 문제도 역시 블로그 글 쓰기에 밀려있는 문제들이다. 조만간 풀이하겠다. 언뜻 보면 어려워보일수 있다. 입력의 각 줄의 데이터가 가 부모-자식 순서라는 보장이 전혀 없기 때문이다. 정말 정점간 연결 정보만을 알려주기 때문이다. 트리는 아주 특수한 형태의 그래프이다. 트리는 계층 구조를 가지는 자료구조이지만, 동시에 사이클, 즉 순환이 없는 그래프이기도 하다. 이런 그래프는 어떤 정점을 고르더라도 트리가 될 수 있다. 순환 구조가 없기 ..
문제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/15650 시간 제한메모리 제한solved.ac 티어1초512MB실버 3풀이이 문제를 무작정 중첩반복문으로 풀기에는 어려워보인다. 중첩반복문을 쓰게되면 시간복잡도의 문제도 생기지만, 그 전에 몇번 중첩해야할지가 애매해진다. 숫자를 M개를 선택해야하는데, 이는 단순하게 생각해서 M중첩 반복문이 필요하다는 뜻이 될테니 말이다. 따라서 반복문만 사용하는 것이 아닌, 재귀함수와 섞어, 어떤 숫자를 선택했을때, 그 뒤의 숫자부터 다시 탐색하도록 작성하였다. 그러기 위해 제일 최근에 선택한 숫자가 무엇인지, 지금 몇개를 선택했는지를 재귀하면서 넘겨주고, 항상 이전에 선택한 숫자보다 더 큰 숫자부터 다시 탐색을 하는 방식을 선택하였다. 답을 출력하기 용이하..
문제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..
