Python/Coding Test

21940 가운데에서 만나기

문제 https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 접근 모든 도시 간의 거리가 필요하므로 플로이드-워셜을 이용했다. 플로이드-워셜로 모든 도시 간의 거리를 구한 후, 각 도시에 대해 왕복시간의 최댓값을 계산했다. 풀이 주의할 점은 도시 a에서 도시 b로 가는 경로가 여러번 입력될 수 있으므로, 입력받을 때 경로의 최솟값으로 갱신해주어야 한다. n, m = map(int, input().split()) dist = [[1e9] * (n + 1) for _ in range(n + 1)] for..

19844 단어 개수 세기

문제 https://www.acmicpc.net/problem/19844 19844번: 단어 개수 세기 첫째 줄에 “문장”을 나타내는 문자열이 주어진다. 이 문자열은 영어 소문자, 띄어쓰기, -(하이픈), '(어포스트로피)로만 이루어져 있다. 이때 띄어쓰기, 하이픈, 어포스트로피 중 어느 것도 인 www.acmicpc.net 접근 전체 문자열을 띄어쓰기와 하이픈으로 구분한 다음, 각 문자열이 어포스트로피를 포함한다면 문제에서 주어진 합쳐지는 조건을 만족하는지 확인한다. 풀이 s = input().replace("-", " ").split(" ") vowel = ["a", "e", "i", "o", "u", "h"] prefix = ["c", "j", "n", "m", "t", "s", "l", "d", ..

22943 수

문제 https://www.acmicpc.net/problem/22943 22943번: 수 0부터 9까지 $K$가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수들의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다. 서로 다른 www.acmicpc.net 접근 문제에서 어떤 k와 m이 주어지든지 간에 소수, 소수의 합으로 만들 수 있는 수, 소수의 곱으로 만들 수 있는 수는 정해져 있으므로 에라토스테네스의 체를 이용하여 소수를 구한다. 구해진 소수들을 이용해서 덧셈과 곱셈으로 만들 수 있는 수들을 미리 구해놓고 백트래킹으로 해당 수가 조건을 만족하는지 확인했다. 풀이 def solve(num): global ans if len(num..

4803 트리

문제 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 접근 주어진 연결정보에 따라 노드를 분리하고 각 노드 집합에 대해 사이클이 발생하는지 확인하면 트리인지 아닌지 판별할 수 있으므로 유니온 파인드를 이용했다. 만약 사이클이 생긴다면 한 노드에서 다른 노드로 갈 수 있는 경로가 2개 이상이 되므로, 노드 집합의 원소의 개수가 k라고 한다면 노드 집합의 간선의 개수가 k-1보다 크다는 뜻 또한 노드를 연결정보에 따라 분리했으므로..

19641 중첩 집합 모델

문제 https://www.acmicpc.net/problem/19641 19641번: 중첩 집합 모델 S번 노드가 루트 노드일 때, 번호가 가장 낮은 노드부터 오름차순으로 방문해서 중첩 집합을 구성했을 때, 각 노드의 번호 left 필드와 right 필드를 출력한다. 총 N개의 줄에 걸쳐 i번째 줄에 i번 www.acmicpc.net 접근 각 노드에 대해 방문하는 순서가 필요해서 dfs를 이용했다. dfs의 매개변수로 순서를 넘길 경우 같은 레벨에 있는 노드들을 처리하기가 힘들어서 공유변수 order를 이용해서 처리했다. 주의할 점은 노드를 오름차순으로 방문하므로, 연결정보를 입력받은 후 정렬해줘야 한다. 풀이 각 노드를 방문하면 order를 1 증가시키고 left 값을 기록한다. 해당 노드와 연결된 ..

22871 징검다리 건너기 (large)

문제 https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 접근 22869 징검다리 건너기 (small) 문제랑 조건은 똑같고, N번째 돌까지 갈 수 있는 모든 경로 중 K의 최솟값을 찾는 문제이므로 파라메트릭 서치 즉, 이분탐색과 DP로 풀이했다. 풀이 DP 과정은 22869번과 동일하고 lt는 0으로 rt는 10 ** 9으로 초기화한 후 이분탐색으로 적절한 K값중 가장 작은 값을 구했다..

22869 징검다리 건너기 (small)

문제 https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 접근 1번째 돌에서 N번째 돌까지의 돌들에 대해, 돌을 한번 건너갈 때마다 쓸 수 있는 힘이 K를 넘지 않는 경로가 존재하기만 하면 되는 문제 따라서 i번째 돌까지 이동하는 데 필요한 힘의 최댓값의 최솟값을 저장할 배열을 만들고 DP로 풀이했다. 풀이 d[i]를 i번째 돌까지 이동하는 데 필요한 힘의 최댓값의 최솟값으로 정의했을 때..

1863 스카이라인 쉬운거

문제 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 접근 건물 겉넓이, 빗물 트래핑, 주식 매매 같은 문제랑 비슷한 거 같아서 스택으로 풀이했다. 풀이 입력받은 y에 대해 스택에는 y보다 낮은 높이의 건물만 있도록 pop하면서 ans에 1씩 더한다. y가 스택에 있는 마지막 요소랑 같거나 0인 경우에는 스킵하고, 더 작은 경우 append한다. 모든 입력을 처리한 후 스택에 남아있는 원소들..

20182 골목 대장 호석 - 효율성 1

문제 https://www.acmicpc.net/problem/20182 20182번: 골목 대장 호석 - 효율성 1 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 접근 20168 골목 대장 호석 - 기능성 문제는 백트래킹으로 풀이했으나, 이 문제에서는 N과 M의 범위가 아래와 같으므로 시간초과 발생 1 ≤ N ≤ 100,000 1 ≤ M ≤ 500,000 솔직히 풀이 방법이 생각이 안나서 힌트를 참고해서 다익스트라를 써야한다는 것을 알았다. 그러나 문제는 출발지부터 목적지까지의 최단거리를 구하는 것이 아니라, 가지..