본문 바로가기

전체 글

 (166)
[백준 5670] 휴대폰 자판 트라이 문제. 트라이에 대해 몰라도 자료 구조와 그래프에 대해 잘 이해하고 있다면, 충분히 떠올릴 수 있다. 주어진 단어들을 가지고 트리를 만든다고 생각하면 된다. 각 문자열의 위치 별 문자가 하나의 노드가 되고, 연속된 같은 문자라면 노드를 공유하면 된다. 위의 예시를 구현하면 아래와 같은 형태가 된다. 위 문제에서는 똑같은 단어가 두 번 주어지지 않으므로, 나는 해당 문자를 끝으로 하는 완전한 단어가 있음을 표시할 빈 노드를 만들어 사용했다(코드에서는 공백 값을 주었다).   위처럼 트라이를 구현하고 나면 어느 부분까지 자동 완성이 가능한지 쉽게 찾아낼 수 있고, 나는 DFS를 통해 각각의 완전한 단어들을 만드는 데 필요한 입력 횟수 합을 재귀적으로 받아오도록 했다. 주의할 점은 첫 문자는 무조건 입..
[백준 11400] 단절선 그래프 이론 문제다. 예전에 풀었던 단절점 문제와 상당히 유사한 형태로 풀 수 있고, 오히려 예외 처리할 부분이 더 적어서 심플하다. [백준 11266] 단절점  [백준 11266] 단절점제목 그대로 단절점을 찾는 그래프 이론 문제다. 이건 정말 한참을 고민해도 떠오르지 않아서, 단절점 알고리즘을 따로 찾아 간단하게 공부하고 풀었다. 체감상 플레4 이상의 문제들은 슬슬 모winterry.tistory.com DFS Spanning Tree를 구축하고, 이를 통해 자식 노드가 부모 노드의 조상 노드로 향할 수 있는지 판별하는 게 전부다. DFS를 통해 노드들을 탐색하면서 발견 순서를 저장해뒀다가, 모든 자식에 대해 부모 노드를 거치지 않고 도달할 수 있는 조상 노드를 확인한다. 만약 자식이 도달한 조상 노..
[백준 1086] 박성원 DP 문제인데, 생각보다 발상이 까다롭다. 당연히 모든 순열을 완전 탐색했다간 15!가지의 경우를 탐색해야 하므로 시간 초과가 발생한다. 그리고 집합에 포함된 수도 길이가 50까지인 자연수 범위로 상당히 크기 때문에, 수를 만든 후에 모듈러 연산을 적용하는 부분도 쉽지 않다.  따라서, 먼저 매우 큰 수에 대한 모듈러 연산을 어떻게 처리할지 생각해 봐야 한다. 물론 문자열 형태로 만들어 한 글자씩 처리하는 방법도 있겠지만, 그렇게 하겠다면 적어도 나는 위 문제를 제 시간 안에 풀어낼 로직이 떠오르지 않는다. 모듈러 연산은(합동식) 덧셈, 뺄셈, 곱셈에 대해 분배법칙이 성립하는 연산이고 나눗셈에 대해서는 성립하지 않는다(그래서 페르마의 소정리를 이용해 곱셈 꼴로 바꿔서 해결한다). 따라서 문제에서 예시로 ..
[백준 1786] 찾기 문자열 매칭 문제. 문제에서 설명하고 있는 건 KMP 알고리즘인데, 문득 보이어-무어 알고리즘이 떠올라서 그걸 먼저 시도했다. Bad Character 방법만 이용해서 구현했는데, 모든 테스트 케이스나 반례를 다 통과함에도 이상하게 제출만 하면 자꾸 바로 틀렸습니다가 나와서 원인을 결국 못 찾았다. 나중에 여유가 생겼을 때 다시 확인해봐야 할 것 같다. 그래서 그냥 문제에 있는 KMP 알고리즘을 그대로 구현했더니, 바로 통과할 수 있었다. 탐색을 생략할 수 있는 길이를 알아낼 수 있도록 미리 전처리해서 pi 배열을 만들었고, 탐색할 때도 이를 활용해 적절하게 불필요한 탐색 구간을 뛰어넘도록 했다. 문제에서 설명하는 대로 패턴 문자열의 중복되는 부분을 이용하여 매칭 실패가 발생했을 때, 앞에서 일치했던 부..
[백준 3176] 도로 네트워크 희소 배열 및 LCA(Lowest Common Ancestor, 최소공통조상) 문제.   N개의 도시와 그 도시를 연결하는 N-1개의 도로가 있고, 모든 도시 쌍을 연결하는 경로가 유일하게 존재한다. 따라서 이는 트리 형태의 그래프임을 짐작할 수 있다. N이 최대 100,000이 들어오고, K가 최대 100,000이므로 매번 일반적인 방법으로 그래프 탐색을 진행하면 시간 초과가 발생할 것이다. 따라서 캐싱된 데이터를 마련할 필요가 있음을 추측할 수 있고, 하지만 모든 도시 연결 쌍에 대해 미리 경로 상의 가장 긴 도로와 가장 짧은 도로를 구하는 것은 불가능하다. 도시가 100,000개인 경우, 100,000 * (100,000-1) 개의 도시 쌍이 존재하고 도시 쌍마다 4 Bytes 정수 두 개가 필요하..
[백준 4195] 친구 네트워크 분리 집합과 해시를 이용하는 자료구조 활용 문제다. 문제를 유심히 읽어보면 알 수 있듯이, 친구 집합이 계속해서 합쳐져야 하고 특정 아이디의 유저가 속한 친구 집합을 빠르게 조회할 수 있어야 한다. 따라서 분리 집합을 활용해 이를 효율적으로 처리할 수 있다. 다만 유저에 대한 정보를 문자열 형태의 아이디로 제공하고 있으므로, 이를 Union-Find 연산 내에서 매번 문자열 형태로 비교하면 효율성이 떨어진다. 나는 그래서 해시 맵을(C++ 내의 unordered_map을 사용했다) 활용해, 각 유저의 아이디에 대한 고유 정수 id값을 부여했다. 이렇게 하면 처음 유저 아이디를 입력받았을 때만, 한 번 id 값을 조회하고 그 이후부터는 정수 id로 빠르게 Union-Find 연산을 처리할 수 있다.  나머..
[백준 1949] 우수 마을 트리 DP 문제다. 처음 본다면 로직을 떠올리기 조금 힘들 수도 있다. 트리 DP 문제를 풀어본 경험이 있다면 쉽게 접근할 수 있는 문제.  각각의 마을이 일반 마을일 수도 있고, 우수 마을일 수도 있는데 문제에서는 조건을 통해 이를 제약하고 있다. 1. 우수 마을로 선정된 마을 주민 수의 총합을 최대로 해야 한다.2. 우수 마을끼리는 인접할 수 없다.3. 일반 마을은 최소한 하나의 우수 마을과 인접해야 한다.  따라서 dp 값을 계산할 때 어떤 마을이 일반 마을인 경우와 우수 마을인 경우로 나눈 다음에 트리 탐색 과정에서 이를 조건에 맞게 처리해 주어야 한다. 나처럼 dp[마을 번호][우수 마을 선정 여부(0: 선정x, 1: 선정)] = 해당 마을 번호를 루트로 하는 서브 트리의 최대 우수 마을 주민 ..
[백준 1507] 궁금한 민호 그래프 이론 문제다. 처음 문제를 가볍게 읽었을 때는 최소 스패닝 트리 문제인 줄 알았다. 하지만 문제를 꼼꼼하게 읽다 보니 개성 있는 문제라고 느꼈는데, 각 노드에서 목적 노드 별 최단 거리가 주어지고 최소 간선으로 그 그래프를 만들었을 때 간선의 비용 총합을 추측하는 문제였다.  먼저 시도했던 방법은, 최소 스패닝 트리를 만들듯이 간선들을 우선순위 큐에 넣고 비용이 작은 간선을 우선해서 그래프를 만들어 나가는 방법이었다. 이 방법으로 구현하다가 결국에는 다른 노드를 경유해서 만들어질 수 있는 최단 거리 문제 때문에 중간에 지워버렸다. 매 간선을 추가하려고 할 때마다 DFS가 필요할 테니까.  그다음으로 이용한 방법은, 플로이드-워셜 알고리즘을 이용한 방법이었다. 문제에서 주어지는 입력값은 결국 어떤 ..

티스토리툴바