Bibidi

3006번: 터보소트 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다. 둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다 www.acmicpc.net 풀이 각 숫자가 어느 자리에 있는지 먼저 기록한다. 숫자 i를 정렬할 때 맨 앞이나 맨 뒤로 보내 정렬하므로 숫자 i가 있는 위치와 가야되는 위치 사이에 있는 숫자의 개수를 파악하면 된다. 그리고 정렬된 숫자를 제외하고 같은 작업을 반복하면 된다. 1을 맨 앞, n을 맨 뒤로 추상화할 수 있다. #include using namespace std; typedef long long ll; int tree[1 > n; for (base = 1; base ..

2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 세그먼트 트리 응용 문제. 사탕맛이 a인 사탕이 몇 개인지 tree[base + a]에 업데이트하고 k 번째 사탕을 찾아서 내주면 된다. k 번째 사탕은 사탕 맛의 크기가 작은 쪽에서 k 번째이다. 루트에서 왼쪽으로 내려가서 찾을지 오른쪽에서 내려가서 찾을지 정해야 하는데, 왼쪽에 사탕이 k 개 이상 있을 땐 왼쪽으로 가고 그렇지 않을 땐 오른쪽으로 가서 k - 왼쪽 사탕의 개수 번째 사탕을 찾으면 된다. - Source code link..

10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 빈 방에 비행기를 채워 넣는 문제입니다. 숫자가 작은 방일수록 더 많은 종류의 비행기를 넣을 수 있으므로 g_i보다 같거나 작은 빈 방 중 가장 큰 빈 방부터 써야 합니다. 이걸 어떻게 구현할 수 있을까요 ? 처음 set에 빈 방을 모두 넣어줍니다. 이때 set이 내림차순이 되도록 설정하면 set.lower_bound(t)를 이용하여 t와 같거나 작은 방을 logN에 찾을 수 있습니다. g_i보다 같거나 작은 방 중 가장 큰 방을..

14868번: 문명 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(1 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지 www.acmicpc.net 백조의 호수랑 비슷한 문제. 옛날에 백조의 호수 풀 땐 유니온 파인드를 몰라서 서로 이어졌는지 확인하는 과정을 까다롭게 구현했었는데, 유니온 파인드를 알고 나니 체감 난이도가 확 떨어짐. 서로 다른 문명을 합치는 과정과 문명이 없는 곳에 문명을 전파하는 과정을 따로 구현하면 된다. 먼저 문명을 합치는 큐를 돌리고 그 과정에 사용된 큐를 다시 전파용 큐로 전달해주고 문명 전파 후 새로 추가된 큐를 문명을 합치기 용 큐로 보내는 과정을 반복하..

16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 제목부터 슬픈 문제. 서로 연결되어 있는 것들을 처리해야 해서 처음엔 Connected Component를 구해서 어찌어찌 처리해야 하나 했지만 친구비를 아끼기 위해 친구 집합의 최소 친구비를 구해야 된다. 트리를 이용하면 루트에 최소 친구비를 업데이트 할 수 있고 두 트리를 합칠 땐 유니온 파인드를 이용하면 된다. 유니온 파인드의 merge를 구현할 때 왼쪽을 우리와 이미 친구인 집합 오른쪽을 새로 친구가 되는 집합..

15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨 배달집 m개를 선택하고 선택한 치킨집 지점들부터 시작해서 거리를 채운 뒤에 집이 있는 장소의 치킨 거리를 모두 더하면 된다. - Source code link github.com/Bibidi/Algorithms/blob/master/boj/boj%2015686.cpp

2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 얼리어답터란 말이 기니 얼리어답터를 색칠된 노드로 생각한다. 처음엔 색칠된 노드의 이웃 노드는 색칠될 필요가 없으니 첫 노드를 색칠하고 그 다음 노드는 색칠하지 않고 그 색칠되지 않은 노드의 다음은 또 색칠하는 식으로 하면 최적의 경우가 나올 거라 생각했는데, 틀렸다. 색칠된 노드의 이웃 노드가 반드시 색칠되지 않을 필요는 없는데, 내 코드는 반드시 색칠되지 않은 노드여야 된다는 논리를 가지니 여기에 문제가 있을 게 뻔하다 생각했고 고치니 맞았다. 그런데 ..

1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 트리가 재귀적으로 되어있다보니 Topdown DP를 구현하기 매우 편하다. 현재 노드를 색칠한 뒤 다음 노드로 보내는 경우 현재 노드를 색칠하지 않고 다음 노드를 보내는 경우 두 가지가 있다. 현재 노드를 색칠한 경우 다음 인접한 노드는 반드시 색칠이 되어 있지 않아야 하고 현재 노드를 색칠하지 않은 경우 다음 노드는 색칠이 될 수도 아닐 수도 있다. - Source code link github.com/Bibidi/Algorithms/blob/..