알고리즘 & 자료구조

https://solved.ac/profile/seaworld0125 solved.ac 알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 난이도 및 티어 정보 제공 solved.ac 약 두 달 넘는 기간 동안 백준을 풀었고 오늘 후기를 남기려고 한다. 일단 기록을 보면 알 수 있지만 초반에 중요한 코딩 테스트가 예정되어 있어서 뜻하지 않게 시작되었던 1일 1 백준 도전이었다. 초반에 미친 듯이 알고리즘을 풀었고 하루에 5문제는 기본으로 풀었던 것 같다. 그때쯤 블로그에 알고리즘 개념도 많이 정리해서 포스팅했었다. 그 이후에는 다른 중요한 일정들이 있어서 병행하다 보니 하루에 많은 문제를 풀지는 못했다. 그리고 두 달이 지난 지금 돌아보면 알고리즘 공부는 미친 듯이 하는 게 실력 ..

이 문제를 풀면서 어려웠던 건.. 이 문제가 DP가 맞는가? 였다. 요즘 (DP, 그리디, 브루트포스) 종류의 문제를 만나면 갈피를 잡지 못하는 것이 가장 힘들다. 배낭 문제라는 사실을 알았을 땐, 아.. 그치 배낭 문제지..라고 금방 이해되지만 혼자서 그 생각을 해내는 게 가장 어려운 것 같다. 이 문제는 최근에 만난 DP 문제들처럼 약간의 응용이 필요하다. 문제의 목표는 M이상의 메모리를 확보하면서 가장 적은 Cost를 사용하는 것이 목표이다. 그렇다면 DP 관계(?)를 설정할 때 다음과 생각해 볼 수 있다. DP 배열은 2차원 배열로 구성하고 배낭 문제 처럼 접근한다고 하자. 그렇다면 1, 2 선택지 중에 어떤 것을 골라야할까? DP[앱의 index][앱의 memory] 로 구성 DP[앱의 inde..

펜윅 트리는 값이 변경되어도 구간의 합을 빠르게 구할 수 있는 자료구조이다. 기존의 구간 합을 구하는 방법은 값의 변경이 있을 때 매번 O(n)의 시간이 걸리지만 펜윅 트리는 O(logn)의 시간이 걸린다. 어떻게 가능한 걸까? 우선 펜윅 트리의 구조를 먼저 그려보고 살펴보자. 펜윅 트리의 특징은 다음과 같다. 펜윅 트리는 화살표가 가리키는 곳에 각 구간의 합이 저장된다. 조금 헷갈릴 수 있는 부분이 BIT 배열의 인덱스는 0이 아닌 1부터 시작한다. 즉 BIT[1] 에는 원래 배열 arr[0]이 저장된다. BIT[4] 에는 원래 배열 arr[0]~arr[3]의 구간 합이 저장된다. BIT 자료구조를 사용하는 가장 큰 이유는 값의 업데이트와 구간 합을 구하기 위함일 것이다. 값을 어떻게 업데이트하고 합을..

특정 정점을 제거했을 때 트리의 수가 증가한다면, 해당 정점을 단절점이라고 표현한다. 단절점을 구하기 전에 먼저 해야 할 일이 있다. 위와 같은 트리가 주어졌다고 했을 때 우리는 DFS를 수행하면서 방문 순서를 기록해야 한다. 방문 순서를 확인하면 단절점의 특징을 찾을 수 있다. 1번 노드는 루트 노드이고 자식 노드가 두 개 이상이다. 또한 1번 노드는 단절점이다. 2번 노드의 자식 노드들(3, 4)은 2번 노드를 거치지 않고 1번 노드로 갈 수 없다. 또한 2번 노드는 단절점이다. 5번 노드의 자식 노드들(6, 7)은 5번 노드를 거치지 않고 1번 노드로 갈 수 없다. 또한 5번 노드는 단절점이다. 정리해보면 루트 노드는 자식 노드가 둘 이상이면 무조건 단절점이다. 특정 노드의 자식 노드들이 해당 노드..

개 킹 받는 매개변수 탐색 문제 풀이를 자세하게 작성해보았다. 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러 개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈칸을 사이에 ..

외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다. 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 ..