본문 바로가기

백준

 (47)
[백준]_14220번 : 양아치 집배원(파이썬) 14220번: 양아치 집배원 첫 줄에는 방문하는 도시 n개가 주어지고(1≤n≤500), 그 다음 n줄에는 n개의 원소가 주어지는 데, i번째 줄의 j번째 원소는 i에서 j로 가는데 거리이다. 만약 거리가 0이면 i에서 j로는 이동할 수 없 www.acmicpc.net 애초에 문제 자체가 이해하기 되게 어려웠던 문제이다. 예제 입력들을 이용해서 현 상황을 이해해 보자. 예제 입력 1 1행 2열에 있는 1이 의미하는 것은 1번 도시에서 2번 도시로 이동하는데 걸리는 비용이다. 그래서 만일 1행 2열의 1을 선택하면 이 시점까지의 이동 비용은 1이고 총 방문한 도시의 수는 2(1번 도시에서 출발, 2번 도시에 결국 도착. 총 2개의 도시를 방문)이다. 대각 성분들이 전부 0인 이유는 예를 들어 n번 도시에서 ..
[백준]_11000번 : 강의실 배정(파이썬) 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 우리의 목표는 강의 시작 시간과 끝 시간을 고려하여 최소 사용 강의실 수를 구하자 이다. 예를 들어 강의 시간을 다음과 같이 나타낸다면, (1, 2, 4) (3) 으로 총 2개의 강의실이 필요함을 알 수 있다. 물론 이 결과는 직관적으로 강의의 끝과 시작이 겹치는 1, 2, 4번 강의를 묶는 것이 강의와 강의 사이의 시간 낭비(공강)를 줄일 수 있기 때문에 나온 것이다. 즉 tuple(시작 시간(s), 끝 시간(f))이 원소인 리스트를 정렬하여 시작 시간과 끝 시간을 더 쉽게 관찰할 수 있게 해주는 것이 우선 ..
[백준]_17387번 : 선분 교차 2(파이썬) 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 이 문제를 풀기 전에 사전 지식이 많이 필요하다. 1. CCW(Counter Clock Wise) 알고리즘 2차원 평면에 놓여 있는 점 3개에 대해 상대적인 위치 관계를 외적을 통해서 구할 수 있다. 이 알고리즘을 적용했을 때 양수가 나오면 반시계, 음수면 시계, 0이면 한 직선 위에 점들이 놓여 있는 것이다. 결괏값은 점의 연산 순서(A->B->C)에 매우 민감하기 때문에 점들의 순서가 매우 중요하다. 알고리즘 계산법은 여기서 더 알아보자. 2. CCW를 활용한 선분의 교차 조건 그래서 결국 세 점의 상대적인 방향을 알아..
[백준]_11724번 : 연결 요소의 개수(파이썬) 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. Union-Find 알고리즘 해당 알고리즘을 이용하면 모든 노드의 최상위 노드를 모두 찾을 수 있다. 무방향 그래프라 상위 노드 개념은 없지만 유..
[백준]_1016번 : 제곱 ㄴㄴ 수(파이썬) 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 문제의 전체 맥락을 보아하니 특정 자연수 구간에서 제곱 수로 나누어 떨어지는 수들을 제외시켜야 하는 작업이 필요하다. 제곱수들의 배수에 해당하는 숫자들을 지우면 되기 때문에 에라토스테네스의 체 알고리즘과 비슷한 맥락임을 알 수 있다. 즉 아래와 같은 코드로 시작하면 좋지 않을까 생각이 든다. s, f = map(int, input().split()) # (int)(f ** 0.5)보다 큰 자연수의 제곱은 f보다 크기 때문에 관찰할 필요가 없다. ..
[백준]_1202번 : 보석 도둑(파이썬) 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 먼저 무게와 가격 중에서 무엇을 더 중시할 것인지 알아야 한다. 우리가 최종적으로 원하는 것은 훔칠 수 있는 최대 값어치의 보석이지만 가방의 무게 한계를 고려하지 않으면 무용지물이다. 즉 가격은 무게 다음으로 중요한 요소이다. 무게(w)와 가격(v)을 튜플로 묶어서 힙큐(tag)에 push 해준다. 이후에 tag에서 무게가 적은 순서로 보석이 나올 것이다. 이제 보석을 담아야 하는데 가능하다면 무게 한..
[백준]_1655번 : 가운데를 말해요(파이썬) 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제를 보면 정렬되지 않은 데이터가 입력되고 입력이 일어날 때마다 정렬을 한 후에 가운데 요소를 출력해야 한다. 하지만 입력이 있을 때마다 데이터들을 정렬하는 것은 시간 복잡도가 $O(N^2log{N})$이므로 바람직하지 않다. 특히나 이문제는 시간제한이 0.1초이므로 매우 빠듯한 편에 속한다. 데이터 입력이 일어날 때마다 정렬을 해주는 우선순위 큐(heapq)를 이용해주자. 힙큐는 원소의 추가(heappush)가 $O(logN)$, 원소 추출(..
[백준]_1991번 : 트리 순회(C언어) 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 입력으로 노드들이 부모, 왼쪽 자식, 오른쪽 자식 순서로 주어지고 이렇게 완성된 트리에서 전위 순회, 중위 순회, 후위 순회를 해서 노드에 저장된 값들을 순회별로 출력하면 되는 문제이다. 전략 먼저 입력 방식을 정의해 보자. 부모 노드는 반드시 입력되고 존재하지 않는 자식 노드는 '.'으로 대체된다. 즉 일단 크기가 6인(최대 입력이 5개까지인데 크기가 6인 이유는 배열의 마지막에 널 문자('\0')를 저장해야 되기 때문) 배열로 문자열을 받은 다음에..

티스토리툴바