목록python (74)
just inside
[백준] Silver 4. 1158 - 요세푸스 문제 python
문제 링크https://www.acmicpc.net/problem/1158문제 설명요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이 요세푸스 순열을..
[알고리즘 in python] 신장 트리 / 최소 신장 트리 / 크루스칼 알고리즘 / 프림 알고리즘
그래프 (Graph)정점(Vertex)과 이 정점들을 연결하는 간선(Edge)으로 구성된 데이터 구조.가중치 그래프 (Weighted Graph) : 각 간선에 가중치(비용 또는 거리 등)가 할당된 그래프비가중치 그래프 (Unweighted Graph) 신장 트리 (Spanning Tree) 알고리즘그래프 이론에서 최소 비용으로 모든 정점을 연결하는 트리를 찾는 알고리즘네트워크 설계, 도로 건설, 통신 케이블 배치와 같은 문제에서 최소 비용으로 네트워크 구성하기 위해 사용 신장 트리의 특징주어진 그래프의 모든 정점을 포함하는 연결 그래프사이클이 없는 그래프n-1개의 엣지를 가짐. n은 그래프의 정점 수 최소 신장 트리 (Minimum Spanning Tree, MST)주어진 가중치 그래프에서 가능한 모든..
[백준] Silver 3. 17626 - Four Squares python
문제 링크https://www.acmicpc.net/problem/17626문제 설명라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^2.자연수 n..
[백준] Silver 3. 11727 - 2xn 타일링 2 python
문제 링크https://www.acmicpc.net/problem/11727문제 설명2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 제출 코드import sysinput = sys.stdin.readlinen = int(input().rstrip())dp = [0 for _ in range(1001)dp[1] = 1dp[2] = 3dp[3] = 5if n > 3: for i in range(4, n+1): dp[i] = dp..
[백준] Silver 3. 11659 - 구간 합 구하기 4 python
문제 링크https://www.acmicpc.net/problem/11659문제 설명 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제출 코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())nums = list(map(int, input().split()))prefix_sum = [0]..
[백준] Silver 3. 9461 - 파도반 수열 python
문제 링크https://www.acmicpc.net/problem/9461문제 설명위 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 출력 각 테스트 ..
[백준] Silver 3. 9375 - 패션왕 신해빈 python
문제 링크https://www.acmicpc.net/problem/9375문제 설명 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.모든 문자열은 ..
[백준] Silver 3. 2579 - 계단 오르기 python
문제 링크https://www.acmicpc.net/problem/2579문제 설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포..