본문 바로가기

전체 글

 (141)
[백준 14725] 개미굴 자료 구조 문제다. 트라이를 구현해서 푸는 것이 정석 풀이인 것 같은데, 먹이 이름으로 주어지는 문자열의 길이가 15이고 N이 최대 1,000인데 굳이 도입의 필요성은 못 느꼈다. 입력 값이 클린하게 주어지기 때문에, 트리를 구축하기 쉽다. 나는 노드 클래스를 만들고, 자식 노드들을 형태의 map(C++ STL 기준)으로 가지도록 했다. 먹이 정보의 수가 컸다면, 삽입에 O(log N)만큼 소모되는 map을 택하기 껄끄러웠겠지만 다행히 N과 K 모두 범위가 그리 크지 않다. 그래서 어차피 정렬된 형태로 결과를 출력할 필요가 있기 때문에 정렬된 상태를 보장할 수 있는 map을 선택했다.  Node 클래스를 정의하고 나면 로직은 심플하다. 각 로봇 개미들이 보내준 먹이 정보를 바탕으로 트리를 구축한다. 현..
[백준 14938] 서강그라운드 그래프 이론 중에서 최단 거리 문제다. 요새 계속 어려운 문제만 풀었더니, 처음에 입력 값의 크기가 너무 작아서 내가 문제에서 뭔가 놓쳤는지 의심부터 했다. 각 지역마다 다른 지역들까지의 최단 거리를 구해서, 수색범위 보다 작은 비용으로 도달할 수 있는 구역의 아이템 가치를 더해서 얻을 수 있는 아이템 가치 총합을 구한다. 그리고 어떤 지역에서 시작할 때 얻을 수 있는 아이템 가치 총합이 가장 큰 지 판별하면 끝이다.  최단 거리를 구하는 알고리즘들은 너무 잘 알려져 있고, 대표적으로 다익스트라 알고리즘, 플로이드-워셜 알고리즘, 벨만-포드 알고리즘이 있다. 노드와 간선의 수가 둘 다 최대 100밖에 되지 않고, 간선이 음의 가중치를 가지는 경우도 없기 때문에 사실 뭘 선택해도 문제없이 해결된다.  나는..
[백준 11266] 단절점 제목 그대로 단절점을 찾는 그래프 이론 문제다. 이건 정말 한참을 고민해도 떠오르지 않아서, 단절점 알고리즘을 따로 찾아 간단하게 공부하고 풀었다. 체감상 플레4 이상의 문제들은 슬슬 모르면 해법을 떠올리기 어려운 문제들이 등장하는 것 같다.  일단 매번 브루트 포스로 단절점 여부를 확인하는 방법을 떠올릴 수 있으나, O(VE)의 시간 복잡도이기 때문에 문제를 해결할 순 없다. 다른 방법을 떠올려보려고 했으나, 사이클 문제 때문에 쉽사리 떠오르지가 않았다.  이 문제를 해결하기 위해서는 DFS Spanning Tree를 사용해야 한다. DFS Spanning Tree는 DFS를 통해 그래프 탐색을 할 때 방문 순서를 바탕으로 형성되는 트리 구조를 일컫는다.    예제1을 예로 들면, 예제1을 그래프로 시..
[백준 2618] 경찰차 DP 문제이다. DP를 사용해야 한다는 것은 바로 알아챘지만, 점화식 떠올리는 게 쉽지 않았다. 계속 DP 테이블을 초기 상태부터 순서대로 채우려고 시도해서 그런 것 같다. 확실히 DP 문제에 약한 편이라, 같은 난이도여도 DP 문제는 더 어렵게 느껴진다.  일단 브루트 포스 풀이를 생각해보면, 각 사건에 대해 경찰차1과 경찰차2를 배정하는 두 경우가 존재한다. 따라서 경우의 수가 2^W에 달하며, O(2^W)의 시간 복잡도를 가진다. 당연히 문제를 제 시간 내에 해결할 수 없다. 하지만 브루트 포스 로직을 관찰하면서 어떤 부분에서 비용을 줄일 수 있을지 생각해 볼 수 있다.  특정 i 번째 사건에 경찰차를 배정하려고 할 때, 이전까지 경찰차를 배정하는 경우를 떠올려 보면, { 1, 1, 1, 1, 1 ..
[백준 11505] 구간 곱 구하기 세그먼트 트리 문제이다. 전체적인 맥락은 세그먼트 트리를 이용해 구간 합을 구하고 수정하는 문제와 유사하지만, 곱 연산이 들어가고 입력으로 주어지는 수에 0이 존재할 수 있기 때문에 구간 합 문제보다 까다로운 문제가 된다. [백준 2042] 구간 합 구하기 (tistory.com) [백준 2042] 구간 합 구하기세그먼트 트리 문제이다. 어제의 문제와 같은 유형이기 때문에, 이제 보자마자 알 수 있었다. 대신 어제 푼 문제와 다른 점은 원본 배열이 중간중간 수정될 수 있다는 점인데, 이 때문에 트리를 uwinterry.tistory.com   트리를 초기화하는 부분과 값을 가져오는 함수는 문제 조건에 맞춰 모듈러 연산이 더해진 것 말고는 구간 합 문제와 같다. 위에서 언급했듯이, 까다로운 것은 0의 존재..
[백준 11054] 가장 긴 바이토닉 부분 수열 LIS를 응용한 DP 문제. LIS 알고리즘을 공부했거나 관련 문제를 풀어봤다면 어렵지 않게 풀이 방법을 떠올릴 수 있다. 기준이 될 인덱스를 정해두고, 앞부분에 대한 LIS를 구하고 뒷부분에 대한 LDS를 구해서 더한 값에 1을(기준 값이 포함되어야 하기 때문에) 더해주면 끝이기 때문이다.  다만 내 접근 방식대로 풀려면 수열의 처음부터 끝까지 모두 기준으로 잡고 한 번씩 구해봐야 하기 때문에, LIS와 LDS 구하는 알고리즘은 O(n log n)인 알고리즘을 사용해야 한다. 굳이 이 방법이 아니어도 O(n^2) 알고리즘을 두 번 사용하는 형태로 구해도 될 것 같긴하다. LIS를 기준으로 간략하게 적자면,  - 길이별로 최적 LIS의 마지막 값을 저장해둘 배열(여기선 lis로 지칭)을 생성해 둔다.  ..
[백준 2533] 사회망 서비스(SNS) DP 문제다. 처음에는 트리의 레벨을 홀수 레벨과 짝수 레벨로 나누어 해당하는 노드 수를 센 다음에 더 작은 값을 출력하는 그리디 알고리즘으로 풀 수 있지 않을까 생각했는데, 예제2만 봐도 성립하지 않음을 알 수 있었다. 좀 더 고민해봐도 일반적인 그래프 탐색을 이용해서는 풀 수 없을 것 같아서 다른 알고리즘을 생각하다가 DP를 도입해 해결했다.  문제 해결을 위해 각 노드에 대해 고려해 보아야 하는 상태는 해당 노드가 얼리 아답터인 경우와 아닌 경우다. 문제에서 주어지는 그래프가 트리임을 보장하고 있으므로, 어떤 한 노드를 루트 노드로 설정하면 모든 노드에 대해 부모 노드와 자식 노드를 정할 수 있다.   i번 째 노드에 대해, dp[i][0]를 i번 째 노드가 얼리 아답터일 때 서브 트리의 최소 얼리..
[백준 2042] 구간 합 구하기 세그먼트 트리 문제이다. 어제의 문제와 같은 유형이기 때문에, 이제 보자마자 알 수 있었다. 대신 어제 푼 문제와 다른 점은 원본 배열이 중간중간 수정될 수 있다는 점인데, 이 때문에 트리를 update하는 함수를 따로 구현해 주었다. 그 외에 신경쓰였던 것은 입력으로 주어지는 모든 수의 범위가 long long int의 범위라는 것인데, 정답이 long long int의 범위를 보장하지만 이러면 구간 합을 구해내는 도중에 오버플로우가 나지 않을까 하는 점에서였다. 그런데 잘 생각해 보면 정답이 long long int의 범위를 보장하므로, 중간에 오버플로우가 나더라도 결국에 구간 합을 구해내면 답을 정상적으로 출력되겠구나 싶었다(오버플로우가 범위를 초과하는 순간 무식하게 임의의 쓰레기 값이 들어가는 게..

티스토리툴바