문제요약 (1976. 여행 가자) n개의 도시가 어떻게 연결되어 있는지와 여행 계획이 주어져있을 때, 여행 계획에 맞춰 도시들을 여행 할 수 있는지 판별하시오. 이때 같은 도시를 여러번 방문하는 것도 가능하다. 노드들의 연결된 상태를 물어보는 문제 이므로 유니온 파인드로도 문제를 풀 수 있다. 그러나 필자는 처음 생각한 문제 풀이 방법이 BFS이기도 하고, BFS로 풀어보고자 하는 마음이 생겨 BFS로 풀었다. 만약 유니온파인드로 푼 문제 풀이를 보고 싶다면 아래 링크()로 들어가길 바란다. 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것..
문제요약 (1717. 집합의 표현) 0부터 n까지 있는 집합이 있다. 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지를 확인지 확인하는 연산 두 가지가 주어질 때 각각에 맞는 출력을 제시하시오. 집합을 알맞게 연결해 같은 집합에 속하는지 확인해야하는 문제입니다. 이때 사용할 수 있는 유니온 파인드 알고리즘입니다. 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이를 위한 부연 설명 유니온 파인드 union과 find 두 가지 연산으로 구성되어 있는 알고리즘 unio..
문제요약 (1325. 효율적인 해킹) 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다. 이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다. 이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오. 문제에 대한 해답이 맞는데 자꾸 시간 초과가 나는 경우, PyPy3로 언어를 바꾸고 제출해보도록 하는 것도 방법이다.. 필자도 구글링하고 코드 수정만 엄청 많이 했었다. (..
문제요약 (1929. 소수 구하기 ) M 이상 N 이하의 소수를 모두 구해 출력한다. 소수를 구하는 여러가지 방법 중 에라토스테네스의 체를 이용해 구해보자 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이를 위한 부연 설명 에라토스테네스의 체의 원리 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성 2부터 숫자를 시작해 숫자가 지워지지 않은 경우 현재 선택된 숫자의 배수에 해당하는 수를 탐색하며 지운다. 단, 처음 선택된 수는 지우지 않는다. 리스트를 반복한다. n = a * b ( a > b) 라는 것은 n = b * a와 같다. 즉..
문제요약 ( 1541. 잃어버린 괄호 ) 주어진 수식에 적절히 괄호를 추가하여 식의 계산 결과값이 최소가 되도록 한다. ex. 55-50+40의 경우 55-(50+40)으로 만들어주면된다. 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이를 위한 부연 설명 - 뒤에 붙는 숫자들은 다음 - 가 나올 때 까지 최대한 많이 묶어서 더한다. 더 좋은 풀이에서는 이 점을 이용하기 위해 split 함수를 사용했다. 주어진 수식을 연산자와 숫자로 나눠준다. 연산자를 하나씩 살펴보며 - 가 나올때를 기준으로 문제를..
문제요약 (1744. 수 묶기) 주어진 수열을 적절히 묶거나 더해서 그 합이 최대가 되도록 한다. 이때 수열의 모든 수는 한 번만 묶거나 묶지 않아야 한다. ex. 어떤 수열이 {0, 1, 2, 4, 3, 5} 일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다. 수열에 음수인 수가 있을 때 처리를 중심으로 생각하는 것이 중요하다. 그리고 생각지도 못한 숫자가 하나 있을 수 있으니 주의하자. 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤..
문제요약 (1715. 카드 정렬하기) 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10..
문제요약 (11047. 동전 0) 원하는 돈의 가치를 만들기 위해 필요한 동전의 최소 갯수를 구해 출력하라 다양한 경우의 수가 있지만 최소 갯수를 구해야한다. 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이를 위한 개념 그리디에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다. [코테 알고리즘] DFS, BFS / 관련 문제 본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문제를 풀며 관련..
문제요약 ( 1920.수 찾기 ) 주어진 리스트에 원하는 값이 있는지 찾아 출력한다.. 풀이를 위한 부연 설명 정렬 알고리즘은 O(nlogn)의 시간 복잡도를 가진다. 이분탐색의 경우 O(nlogn)의 시간 복잡도를 가진다. 이분 탐색은 정렬된 데이터에 대해 실행할 수 있으므로 미리 sort()해야한다. 코드 import sys input = sys.stdin.readline num = int(input()) nums = list(map(int, input().split())) nums.sort() find = int(input()) finds = list(map(int, input().split())) for target in finds: first = 0 last = num - 1 isFind = F..
문제 요약 (11724. 연결 요소의 개수) 방향이 없는 그래프(양방향 그래프)의 노드와 간선이 주어졌을 때 연결 요소의 개수를 구하는 것이다. 연결 요소는 연결된 노드들의 뭉텅이라고 생각하면 문제를 풀기 편하다. ex. 1-5-2, 3-4, 6 이렇게 연결되어 있다면 연결 요소의 개수는 3이다. 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 풀이를 위한 부연 설명 입력되는 값들을 받아 그래프를 완성한다. 그래프 내에서 연결 요소를 찾아야하므로 ..