본문 바로가기

Dev

 (90)
[백준 11438] LCA 2 LCA(Lowest Common Ancestor, 최소 공통 조상) 문제. 어제 풀었던 것보다 좀 더 심플한 유형으로, 순수하게 LCA만 쿼리한다.   노드의 수가 최대 100,000개까지 입력될 수 있고, 쿼리 또한 100,000개까지 들어올 수 있기 때문에, LCA 탐색에는 O(log N)인 알고리즘을 사용해야 한다. 어제처럼 Sparse Table을 사용하여 풀었는데, Sparse Table을 생성하는 dfs 내부의 로직을 조금 변경했다. 크게 보면 로직은 같은데, 어제의 경우처럼 테이블에 여러 데이터를 저장하는 게 아니므로 좀 더 심플하게 바꿀 수 있었다.  원리는 어제 설명했듯이, LCA를 찾아나갈 때 부모 노드를 통해 일일이 찾아가는 것이 아니라, 각 노드 별로 2^k번째 조상을 모두 저장해 ..
[백준 1761] 정점들의 거리 LCA(Lowest Common Ancestor, 최소 공통 조상) 문제다. 모든 노드에 대해서 조상 노드들까지의 거리를 전처리 해두고, LCA를 찾아 그 거리를 합하면 될 것이라고 쉽게 생각할 수 있다. 대신에 Biased Tree일 경우, 트리의 깊이가 N이 될 수 있고 그렇게 되면 LCA를 찾아내는 알고리즘이 O(트리 높이)인 경우, 전체 시간복잡도가 O(NM)이 되어 시간초과가 발생할 것이다. 풀고 나서 찾아보니까 테스트 케이스가 잘못되었는지 O(N)인 LCA 알고리즘으로도 풀린다고 하지만 문제의 의도와 맞지 않는 풀이라고 생각한다.  LCA를 O(log N)만에 찾을 수 있는 알고리즘은 Sparse Table을 사용하는 것이다. n번째 노드라는 것은 이진수를 떠올리면 알 수 있듯이, 2^k 조합..
[백준 7569] 토마토 BFS 문제다. 이 문제는 포스트를 쓸까 말까 고민을 했다. 원래 포스트를 작성하면서 한 번 더 되뇌이는 용도로 작성해서, 너무 간단한 문제들은 굳이 포스트를 작성하지 않는데, 스탠다드 문제로 분류되어 있길래 그냥 작성하기로 했다.  일반적인 BFS의 단순 차원 확장 문제다. 토마토의 상태 값을 이용해서 방문처리도 겸할 수 있으므로, 굳이 방문처리를 위한 배열을 생성할 필요도 없다. 나는 BFS 내에서 이미 익은 토마토이면 그 노드에 대해서는 BFS 진행을 하지 않도록 했는데, 그러다보니 초기 값 처리를 따로 했다. 처음에 3차원 배열 값들을 입력받을 때, 익은 토마토 주위의 익지 않은 토마토들을 검색해서 큐에 넣어줘도 되고 익은 토마토 좌표들을 큐에 넣고 해당 좌표 값들을 -1로 변경해 두어도 된다. ..
[백준 2150] Strongly Connected Component 그래프 이론 중 SCC 문제. 전에 2-SAT 문제를 풀기 위해 익혔던 SCC 알고리즘을 연습해 보기 위해 따로 고른 문제다. SCC를 찾는 대표적인 알고리즘 중 하나인 코사라주 알고리즘을 어제 구현해 보았고, 타잔 알고리즘도 직접 구현해보고 싶어서 오늘 푼 문제에서는 타잔 알고리즘을 사용했다. 타잔 알고리즘은 코사라주 알고리즘보다는 비교적 구현이 복잡하지만, DFS를 한 번만 사용해도 된다는 장점이 있다. 큰 맥락은 DFS를 통해 자식을 탐색하다가 어떤 자식이 앞서 탐색한 선조 노드를 방문하는 순간, 이는 사이클이며 그 안의 어떤 노드 두 개를 설정하더라도 서로에게 도달할 수 있다는 의미가 된다. 이는 SCC의 정의에 부합하며, 이 원리를 이용해서 타잔 알고리즘을 구현한다.  저 방식으로 알고리즘을 구..
[백준 11280] 2-SAT - 3 그래프 이론을 이용해 푸는 2-SAT 문제. 처음 풀어보는 유형의 문제라, 알고 있는 알고리즘들을 다양하게 떠올려 풀어보려 했지만 마땅한 로직을 찾아내기 힘들었다. 논리식을 유심히 관찰했는데, 여러 가지 관계를 떠올릴 순 있었으나 제 시간 내에 해결할 수 있는 알고리즘으로 잘 연결되지 않았다.  그래서 한참 고민 하다가, 관련된 내용을 찾아봤더니 SCC(Strongly Connected Component)를 이용해서 해결하는 어느정도 정형화된 로직이 있는 것 같았다. 읽으면서 처음 이렇게 접근할 생각을 한 사람이 누구일까 싶었다. 그리고 SCC를 빠르게 찾아내는 알고리즘들도 함께 찾아봤는데, 이건 그래프 문제들을 풀 때 정말 도움이 많이 될 것 같았다.  일단 논리식으로부터 접근하는데, 문제의 각 절들이..
[백준 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을 그래프로 시..

티스토리툴바