관심이 가는 개발 보물창고

문제 풀이 단순하게 완전탐색으로는 문제를 해결할 수 없다. 해당 나무의 종이 몇번 등장하는지 알아야 하기 때문에 해당 나무가 있는지 없는지를 빠르게 파악할 수 있어야 한다. 이걸 풀어서 생각해보면 탐색을 O(logN)에 해결하면 쉽게 풀 수 있다. O(입력받는 나무의 종 10000 x log1000000) => O(60000) 탐색을 빠르게 할 수 있으면서 해당 종이 몇 개 있는지 알 수 있는 자료구조는 map이 있다. 해당 나무의 종이 없다면 새롭게 1로 할당하면 되고, 이미 있는 종이라면 그 횟수를 늘리는 식으로 카운팅을 해놓고 해당 나무의 종의 개수 / (전체 입력 수) * 100을 하게 되면 해당 나무의 % 비율을 계산할 수 있게 된다. 나무 종의 이름이 공백을 포함한 형태이기 때문에 공백을 포함..

미루고 미뤘던 자료구조, 이번 기회에 트라이에 대해서 공부하게 됐다. 내가 여러 사이트를 검색하면서 공부한 것을 정리했다. 트라이(Trie) 자료구조란? 쉽게 생각해서 문자열을 빠르게 탐색할 수 있는 자료구조다. 얼마나 빠르길래 이렇게 따로 명칭까지 있는 것일까? 결론부터 말하자면 M이 최대 문자열의 길이라고 했을 때, O(M)만에 검색할 수 있다. 트라이를 표현하는 특징은 여러 가지가 있다. 1) 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리구조 2) 루트에서부터 내려가면서 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻을 수 있다. 3) 문자열 트리 구조 트라이 작동 원리 트라이는 주어진 문자열을 이루고 있는 문자를 앞에서부터 하나씩 노드를 생성해가면서 만들어진다. 이..

문제 풀이 카드 덱 n개가 있을 때, 카드 두 개를 뽑아서 두 개의 카드를 더한 결과를 뽑은 두 개의 카드에 반영한 후에 다시 카드 덱이 넣는 것을 m번 반복한다. 이때 카드 덱의 총합이 최소가 되는 것을 찾아달라는 문제다. 어떻게 하면 카드 덱의 총합을 최소로 만들 수 있을까? 카드를 뽑을 때 카드의 숫자가 작은 것을 우선적으로 뽑아서 합치면 된다. 만약에 큰 수 2개를 뽑아서 합치면 카드 덱의 총합은 그만큼 더 커지기 때문이다. n개의 데이터에서 빠르게 작은 숫자를 찾는 방법은 우선순위 큐(최소 힙)이면 O(logN)만에 뽑을 수 있다. 그런데 주의할 점은 한 카드의 숫자가 최대 100만이라 int로 선언할 시 오버플로우가 발생하므로 자료형 주의가 필요하다. 소스 코드 #include #include..

문제 풀이 산타 할아버지는 아이들에게 선물을 줄 때, 가장 가치가 큰 선물을 준다. 선물 보따리에 머가 들었는지 모르겠지만 꺼냈을 때 그 가치가 가장 큰 것을 뽑으려면 최대 힙 구조로 구현하면 된다. 따라서 우선순위 큐를 최대 힙으로 구성해서 뽑으면 된다. 소스 코드 #include #include using namespace std; int n, a, x; priority_queue pq; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; while (n--) { cin >> a; if (a == 0) { if (pq.empty()) cout

문제 풀이 입력 범위가 최대 1000이라 다양한 방법이 있을 수 있다. 다솜이가 국회위원으로 뽑히려면 최소한 모든 투표보다는 +1 커야 한다. 3 3 3 3 3 이라면 다솜이는 최소한으로 1명을 꼬셔야 한다는 것이다. 3 3 4 7 5 3 이라면? 제일 많은 득표수를 가진 7에게서 3번 뺏으면? 다솜이가 당선된다. 하지만 다른 방법으로도 당선될 수도 있다. 어떻게 하면 최소한으로 뽑을 수 있을까? 제일 많은 득표수를 가진 사람부터 빼앗으면 된다. [3 3 4 7 5 3] 를 통해서 확인해보자. 다솜이가 3개의 득표 수고, 나머지 국회위원들 3 4 7 5 3 중에서 가장 많은 득표수를 가진 사람은 7표이므로 7 -> 6표로 깎아주고, 다솜이는 3 -> 4표로 증가시켜준다. 다솜이가 4개의 득표수고, 나머지..

문제 풀이 단순하게 완전탐색법으로 접근하면 1초 안에 해결 가능한 범위이지만, 문제에서 보면 메모리 제한이 12MB로 다른 문제들에 비해서 무척이나 작은 공간이다. 12MB => 12 x 1000 x 1000 만약에 2차원 배열을 사용한다고 하면? int(4byte) x 1500 x 1500 => 9,000,000 충분하다고 생각하지만 여기에 헤더 파일 등등 포함되면 빡빡하게 된다. 따라서 모든 자료를 저장할 필요 없이 N번째 큰 수를 찾아야 한다. 즉, 일부를 알기 위해서 전부를 저장할 필요가 없다. 우선순위 큐를 이용하는 방법이다. 다만 이때 우선순위 큐도 전체 자료를 저장하게 된다면, 마찬가지로 메모리 초과가 발생하게 된다. 이유는 위와 같다. 따라서 우선순위 큐를 사용하지만 일정 범위 이상으로 넘..

문제 풀이 반시계 방향으로 배열을 돌리면 된다. 단순하게 생각해서 구현 문제이며, 어떻게 구현하냐에 따라 풀이가 제각각일 것 같다. 반시계 방향으로 배열을 돌린다고 생각할 때, 가장 바깥쪽부터 반시계 방향으로 회전하는 식으로 구현했다. 가장 바깥쪽 반시계 돌리기, 그다음 바깥쪽 반시계 돌리기, 언제까지? 좌표가 엇갈릴 때까지 돌려주면 된다. 바깥쪽의 구분은 왼쪽 대각선의 시작점 (sx, sy) 와 오른쪽 대각선 끝점 (ex, ey)를 기준으로 잡아서 시작과 끝을 구분했다. 엇갈린다는 것은 sx >= ex || sy >= ey 를 의미한다. 배열을 돌릴 때는 swap 개념을 이용해서 기존의 값을 임시 저장소 temp에 저장하고, 다 돌리고 나서 temp의 값을 넣어주면 된다. 이때 원소의 이동은 한 칸씩 ..

위상 정렬이란? 사전 작업, 선행 작업 등 순서가 정해진 작업을 차례대로 수행해야 할 때, 그 순서를 나열한 것. 사이클이 존재하지 않는 방향 그래프의 모든 노드를 순서에 거스르지 않도록 나열한 것. '스타크래프트' 게임을 생각하면 쉽게 이해할 수 있다. '서플', '배럭'을 짓기 위해서는 선행 작업으로 '커맨트 센터'를 먼저 만들어야 한다. 이 순서를 어기게 되면, 영원히 '서플'과 '배럭'을 건설할 수 없게 된다. 이렇듯, 선행이 필수인 것부터 나열해서 정렬하는 것이 위상 정렬이다. 위상 정렬의 동작 과정 진입 차수가 0인 노드 먼저 큐에 넣는다. 큐가 빌 때까지 반복한다. 큐에서 원소를 꺼내고, 그 노드에서 출발하는 간선들을 모두 제거한다. 이때 새롭게 진입 차수가 0인 노드들은 큐에 넣어준다. 큐..

문제 풀이 오큰수를 다시 정리하면 다음과 같다. 나보다 크며, 오른쪽 중에서는 가장 작은 수여야 한다. [3 5 2 7]에서 내가 5라고 가정하면, 오큰수는 7이다. 단순하게 완전 탐색으로 돌리게 되면 O(N^2)이 걸리게 된다. N이 100만이기 때문에 시간 초과가 발생하므로 조금 더 빠르게 오큰수를 찾는 방법이 필요하다. 이런 문제는 스택 자료구조를 사용하면 O(N)으로 해결할 수 있게 된다. 스택은 아래와 같은 방법으로 동작한다. 1) 스택이 비어있으면 -1 (오큰수가 없으므로) 처리하고, 스택에 push 한다. 푸시하는 이유는 다음의 오큰수에 해당될 수 있으므로 2) 스택이 비어있지 않으면, 입력된 arr[i] = 이면 >..

문제 풀이 주어진 문자열 집합 S에서 입력되는 M개의 문자열이 같은 게 몇 개인지를 찾는 문제다. 단순히 생각해보면 전체 집합 S에서 전체 M개의 문자열을 2중 탐색으로 반복해서 문자열 비교까지 하게 된다면 시간 복잡도가 O(10,000 x 10,000 x 500) = 2초를 훌쩍 넘는다. 여기서 줄일 수 있는 방법은 문자열 탐색 속도를 줄이는 것이다. 균형 이진 탐색 트리를 사용하는 set이나 map을 이용하게 되면 O(logN) 만에 탐색 속도를 줄일 수 있다. 소스 코드 #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, M; cin >> ..