CEO

문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 문제 풀이 이 문제는 방향이 없는 그래프가 주어졌을 때, 연결 요소의 개수를 찾는 문제이다. 연결 요소는 특정 노드를 시작으로 방문 가능한 다른 노드의 집합이다. 연결 요소는 다음과 같이 찾을 수 있다. 1번 노드를 시작으로 탐색을 시작한다. 1번 노드 탐색 시 방문한 노드, 즉 연결 요소들을 체크한다. 탐색이 완료 되면, 하나의 연결 요소를 찾은 것이다. 탐색 되지 않는 노드가 남아있다면, ..

문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 풀이 그래프에 대한 정보가 주어질 때, DFS(Depth - First - Search)와 BFS(Breadth - First - Searh)를 통해 탐색할 경우에 탐색 순서를 결과로 반환하는 문제이다. 따라서 문제를 풀기 위해서는 DFS와 BFS에 대해 이해하고 있어야 한다. DFS 구현 def dfs(depth, cur_node, visited): # 이미 시작 지점은 방문하였으므로, 탐색 경로는 n - 1 i..

문제 1248번: 맞춰봐 문제 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 www.acmicpc.net 문제 풀이 -10 ~ 10를 선택하면, 선택된 숫자를 기반으로 한 S 배열의 정보를 입력으로 받는다. 해당 배열 정보를 입력받으면, 그를 바탕으로 순열 들과 비교하여 만족하는 순열을 찾으면 된다. 문제의 예제 입력의 S는 -+0++++--+로 이는 다음과 같이 나타낼 수 있다. 첫 행의 정보(i == 0)는 다음과 같은 경우의 수를 나타낸다. j == 0 (0, 0) 0 j == 2 (0, 0) + (0..

문제 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제�� www.acmicpc.net 문제 풀이 부등호가 2개가 주어진다면 부등호 사이에 들어갈 수 있는 숫자는 3개이다. 따라서 수가 중복되지 않고 수의 순서에 따라 다른 경우의 수가 되므로 이는 순열을 구하는 문제이다. 이전의 N과 M (1)과 다른점이 있다면, 입력된 부등호의 조건을 만족하는지에 대해 확인 할 필요가 있다. 코드 def available(i, j, op): if op == '

문제 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 풀이 앞서 푼 문제들은 (15650 N과 M (2), 1759 암호 만들기) 조합을 구하거나, 조합을 만족하는 경우를 찾는 문제였다. 이 문제에서는 조합을 순차적으로 구하게 되면 대칭되는 성질을 활용하는 문제이다. 예를 들어 예제 입력1을 나눌 수 있는 조합을 순차적으로 나열하면 [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]이다. 여기서 알 수 있는 것은 [0, 1], [0, 2], [0, 3] [1, 2], [1, 3], [2, 3] ..

문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 풀이 이 문제는 특정 문자들이 주어질 때, 해당 문자의 조합을 구하고 각 조합들이 1개 이상의 모음과 2개 이상의 자음으로 구성되는 경우를 찾는 문제이다. 앞서 다룬 15650N과 M (2)에서 중복을 허용하지 않는 조합을 DFS와 itertools를 활용하여 구한 적이 있다. 해당 풀이를 이해하고 있다면 쉽게 풀 수 있는 문제이다. 기존의 조합 문제와 다른 점이 있다면, 자음과 모음의 수를 판단하는 부분이 필요하다는 것이다. depth가 L이면, 즉 L개..

문제 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이 N일 이후에 퇴사를 하는데, 그 전까지 할 수 있는 일들 중 최대 수익이 나는 경우의 수익의 합을 반환하는 문제이다. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 위의 예시의 경우 6, 7에 상담하는 일은 퇴사 이후까지 일을 진행하여야 하므로 할 수 없다. 예시에서 가장 최대 수익을 발생시키는 경우는 1, 4, 5일에 상담하는 경우이다. 상담을 하는 것에 대해 두 가지 경우가 있다. 첫 번째는 상담을 하는 것이고, 두 번째는 상담을 하지 않는 것이다. 이를 반영하여 경우의 수를 계산한다면 다음과 같이 계산 할 수 있다..

문제 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 이 문제는 각 도시에 대해 가중치가 주어질 때 모든 도시를 순회하되, 최소 값으로 순회하는 경우의 수를 찾는 문제이다. 보통 이러한 문제는 DFS를 통해 방문한 경로를 기록해두고, 가능한 경로를 모두 탐색하는 방식으로 푼다. 다른 방법으로는 1 - 2 - 4 - 3 - 1과 같은 방문 순서를 순열로 구한 후에 계산하는 방식도 있을 수 있다. 하지만 순열을 계산하고 처리하는 것은 익숙하지 않아, DFS로 ..