백준/Gold(1~5) (13) 썸네일형 리스트형 [백준]_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를 활용한 선분의 교차 조건 그래서 결국 세 점의 상대적인 방향을 알아.. [백준]_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)$, 원소 추출(.. [백준]_2239번, 2580번 : 스도쿠(파이썬) # 입력 부분 import sys input = sys.stdin.readline tmp=[input().strip() for _ in range(9)] board=[[0]*9 for _ in range(9)] for r in range(9): for c in range(9): board[r][c]=int(tmp[r][c]) # 출력 부분 for r in range(9): for c in range(9): print(board[r][c], end='') print() 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.. [백준]_2565번 : 전깃줄(파이썬 and C언어) 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 아이디어만 잘 찾으면 풀기 쉬웠던 문제였다. 다만 LIS(Longest Increasing Subsequence)와 이 문제가 무슨 연관이 있는지 떠올리는 데에 시간의 대부분을 할애했다. 접근 전깃줄이 꼬이지 않게 하기 위해서는 어떤 특징이 있을까? 먼저 예제에서 언급한 대로 전깃줄 3개를 한 번 제거해 보자. 3개를 제거하고 나니 전깃줄이 꼬이지 않기 위해서는 어떤 원칙을 지켜야 하는지 보이기 시작한다. 그것은 바로 전봇대 A가 전봇대 B로 전사하는 전깃줄은 A의 번.. 이전 1 2 다음
