본문 바로가기

Dev

 (84)
[백준 30805] 사전 순 최대 공통 부분 수열 구현 문제다. 그리디나 완전 탐색이라고 생각해도 될 것 같다. N과 M의 범위가 상당히 작기 때문에 어떻게 풀어도 풀린다. 처음엔 DP스럽게 접근하려고 배열만 이용해서 풀었는데, 조건 처리가 많아서 지저분해 보이는 것이 마음에 안 들었다.  원리는 간단한데, 핵심 부분은 O(n^2)인 LCS 알고리즘과 유사하다. 배열 A를 선형 탐색하는 루프 내에서 배열 B를 선형 탐색한다. 이때, 값이 일치하는 경우를 찾았다면 lcs 배열을 앞에서부터 선형 탐색하며, 현재 일치하는 값보다 작은 배열 원소가 있는지 확인한다. 그런 원소가 있다면 현재 일치하는 값으로 갱신해 주고, 아니라면 lcs 배열 끝에 붙일 수 있는지 확인해서(마지막 원소에서 사용한 배열 B 인덱스보다 현재 일치된 값을 가지는 배열 B 인덱스가 큰 ..
[백준 13334] 철로 자료 구조 문제다. 잊을만하면 접하게 되는 유형인데, 처음에 우선순위 큐가 아닌 일반 큐를 사용했다가 가차 없이 틀렸습니다를 받아서 좀 당황했다. 이후 우선순위 큐로 바꾸고 바로 통과할 수 있었다.  입력받는 데이터의 양을 보면 알 수 있듯이, 모든 좌표를 시작점으로 해서 탐색해 보는 브루트 포스를 이용하면 시간 초과가 난다. 하지만 조금 생각해 보면 굳이 모든 지점을 확인할 필요는 없음을 알 수 있다. 정수 쌍이 많아봐야 100,000개고 그 정수 쌍에 나타나는 필요한 좌표들만 확인하면 되는 문제다.  먼저 기준점 하나가 고정되면 철로의 길이를 이용해서 유효한 범위는 확정할 수 있으므로, 기준점을 정해 데이터셋을 정렬한 다음에 기준점이 변경될 때마다 그에 맞게 처리하면 되겠다고 생각할 수 있다. 나는 ..
[백준 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 클래스를 정의하고 나면 로직은 심플하다. 각 로봇 개미들이 보내준 먹이 정보를 바탕으로 트리를 구축한다. 현..

티스토리툴바