본문 바로가기

전체 글

 (160)
[백준 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을 그래프로 시..
[백준 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의 존재..

티스토리툴바