Bibidi

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를 구현할 때 왼쪽을 우리와 이미 친구인 집합 오른쪽을 새로 친구가 되는 집합..

2020년 마지막 코드포스 ㅎㅎ. 이 당시 코드포스 애니타임 기준 평균 퍼포먼스가 1500 정도 되길래, 아 이제 적어도 그린은 찍어놔야지 하고 참가했었다. 결과는 평소보다 낮은 퍼포 ㅜㅜ C, D 문제 수준 보고 이건 최소 1500대 떠야 되지 않나 생각했지만 1400대 ㅜㅜ 근데 다음 날 인도 텔레그램 사건이 터졌다. 인도에선 취업 시 코드포스 레이팅이 높으면 뭔가 가산점이 붙나보다. 그래서 인도 텔레그램 방에서 문제 풀이를 공유해서 치팅한 것 ㅋㅋ 문제를 E번까지 공유했다고 들었다. 덕분에 내 퍼포하고 점수까지 쪽 빨린 것. 아니 못하면 실력을 키워야지 그걸 왜 치팅을 해. 실력을 더 높여서 치팅한 애들 점수까지 빨아먹을 수 있도록 노력해야겠다. 더러운 것들 ㅡㅡ 그리고 코드포스에선 치팅한 사람들 ..

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/..

4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 1. Preorder는 루트, 왼쪽, 오른쪽 순으로 방문하므로 제일 먼저 출력하는 정점은 항상 탐색하려는 트리의 루트이다. 2. Inorder는 왼쪽, 루트, 오른쪽 순으로 방문하므로 루트를 기준으로 왼쪽에 있는 정점들은 루트의 왼쪽 서브 트리, 오른쪽에 있는 정점들은 루트의 오른쪽 서브 트리를 구성하는 정점들이다. 3. 위 성질을 이용하여, Preorder의 탐색 순서에 맞추어 Inorder 내의 정점들을 잘 잘라나가면 원래의 트리를 구할 수 있다...

2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 1. 각 노드의 열은 왼쪽에 있는 노드들의 개수 + 1이다. 왼쪽 서브 트리에 속하는 노드의 개수와 왼쪽에 있지만 서브 트리에 속하지 않는 노드를 잘 파악해야 한다. 왼쪽 서브트리의 개수는 재귀를 이용하여 구하고 그 외의 노드는 따로 매개변수를 이용하여 전달하여야 한다. 2. 각 깊이의 가장 왼쪽 열과 가장 오른쪽 열을 파악하면 각 깊이의 최대 너비를 알 수 있다. 노드를 방문할 때마다 업데이트 해주고 마지막에 최대 너비와 그 깊이를 구하면 된..

16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 경로가 겹치는 양들 다 모아서 한 번에 지나간다고 생각하고 구현하면 된다. 늑대가 양을 여러 번 잡아먹는 구현만 피하면 간단하다. - Source code link github.com/Bibidi/Algorithms/blob/master/boj/boj%2016437.cpp