본문 바로가기

Algorithm/Baekjoon117

4195. 친구 네트워크 (Python) 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 유니온 파인드를 사용하여 해결할 수 있다. 해당 문제에서는 2개의 딕셔너리를 사용한다. 하나는 친구 관계에서 루트가 될 사용자를 설정하는 parent 딕셔너리이고, 나머지 하나는 친구가 몇 명이 있는지를 카운트하는 friendCount 딕셔너리이다. 친구 관계가 주어졌을 때 처음 등장하는 사용자라면 friendCount에 사용자 아이디를 키 값으로 하여 1로 설정해준다. 그 후 두 사용자를 union 함수를 사용하여 관계를 설정해준다. 만약 두 .. 2022. 2. 28.
17182. 우주 탐사선 (Python) 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 풀이 먼저 모든 지점에서 다른 모든 지점까지의 최단 거리를 구해야한다. 이를 위해서 플로이드 워셜 알고리즘을 사용하면 된다. 플로이드 워셜 알고리즘을 사용하여 최단 거리를 구해놓고 이후에는 순열을 통해서 모든 행성을 방문하는 경우의 수에 대해서 거리를 계산하고 그중 최단 거리를 출력하면 된다. 순열을 구할 때는 시작 행성 위치는 제외하여 구해주면 된다. 문제의 2번째 예제를 예로 들면 1번 행성에서 출발하므로 총 [(0, 2, 3), (0, 3, 2), (2.. 2022. 2. 25.
3079. 입국심사 (Python) 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 풀이 친구들이 심사를 마치는데 걸리는 시간에 대해 이분탐색을 하여 해결할 수 있다. left와 right를 설정하고 mid를 구하여 mid초에 대해서 각 심사대에서 몇 명을 심사할 수 있는지를 체크하여 상근이와 친구들의 수인 M보다 클 경우 답을 갱신해주면 된다. 코드 if __name__ == '__main__': N, M = map(int, input().split()) # N: 입국심사대 총 개수, M: 상근이와 친구들의 수 times = [.. 2022. 2. 25.
15961. 회전 초밥 (Python) 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 풀이 슬라이딩 윈도우를 사용하여 해결할 수 있는 문제이다. 연속으로 먹는 접시에 있는 초밥의 종류에 따른 개수를 카운트 할 수 있는 리스트를 하나 만들어 각 초밥의 개수를 카운트 해주었다. 문제를 해결하는 과정은 다음과 같다. * kind : 현재 범위에서 초밥의 종류 개수, counts[n] : 현재 범위에서 n 종류 초밥의 개수, res : 초밥 종류의 최댓값 쿠폰 번호에 해당하는 초밥의 count를 하나 증가시키고.. 2022. 2. 23.
11049. 행렬 곱셈 순서 (Python) 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 2차원 dp를 활용하여 구할 수 있다. 2차원 dp는 다음을 의미한다. 위의 예제는 dp[2][5]를 구하는 과정 중 하나의 예를 나타낸다. dp[2][5]를 구하기 위해서는 다음과 같은 경우를 모두 탐색해야 한다. dp[2][2] + dp[3][5] + 곱셈 연산 dp[2][3] + dp[4][5] + 곱셈 연산 dp[2][4] + dp[5][5] + 곱셈 연산 이 중 최솟값이 dp[2][5]에 기록된다. 이를 구하는 점화식은 다음과 같다. f.. 2022. 2. 23.
2631. 줄세우기 (Python) 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 풀이 LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)을 활용하여 해결할 수 있는 문제이다. 입력으로 주어진 아이들 중에서 LIS의 길이를 찾은 후 이에 해당하지 않는 나머지 아이들을 옮기면 위치를 옮기는 아이들의 수를 최소로 할 수 있다. 예제를 보면 다음과 같다. 해당 리스트에서 LIS는 {3, 5, 6}에 해당하고 길이는 3이다. 이 3명을 제외한 나머지 7, 2, 1, 4번의 아이들을 옮기면 최소한의 이동으로 번호 순서대로 .. 2022. 2. 23.

티스토리툴바