개발여행

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이 문제는 리스트를 순회하면서 몇명의 인원이 팀이 되었는지 (순환 싸이클이 완성되었는지) 판단하는 문제이다. for _ in range(int(input())): n = int(input()) arr = [0] + list(map(int, input().split())) visited = [0] * (n+1) visited[0] = 1 result = [] for v in range(1, n+1): i..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제에서 제시된 이분그래프에 대한 설명은 아래 블로그에 이해하기 쉽도록 설명되어 있다. https://hongcoding.tistory.com/20 [백준] 1707 이분그래프 (Python 파이썬) www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 이 문제는 시간제한이 작으므로 에라토스테네스의 채를 활용하여야 한다. 에라토스테네스의 채를 이용하여 1부터 1000000까지 소수여부를 저장한 리스트를 만든뒤, 입력받은 숫자와 비교하여 덧셈을 만들어 출력한다. from sys import stdin, stdout arr = [True] * 1000001 arr[1] = False for i in range(1, 1001):..

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 처음에 내장함수인 factorial을 사용했다가 최대 20억이라는 범위에 시간초과가 뜨고 말았다..! 검색해보니 굉장히 심플한 방법으로 풀 수 있었다. 우선, 조합의 개수 공식은 다음과 같다. nCr = n! / {(n-m)! * m!} 즉 조합의 개수는 팩토리얼을 몇번 거친 수들의 곱으로 나타낼 수 있다. 이때 구성되어 있는 수들 중에 2와 5의 개수만 찾아주면 마지막자리의 연속되는 0의 개수를 알 수 있다. ( [2*5 = 10]이 한개 있을 때마다 0..

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 이 문제는 문제 그대로 알고리즘으로 옮길 경우 시간초과가 발생하므로 약간의 트릭을 사용하여 알고리즘을 짜야한다. 편집기에서 수정할 문자열을 하나만 만드는 것이 아니라, 커서를 기준으로 앞부분 문자열과 뒷부분 문자열을 나누는 것이다. from sys import stdin s1 = list(input()) s2 = [] i = len(s1) for _ in range(int(input())): c =..

https://www.acmicpc.net/problem/10820 10820번: 문자열 분석 문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오. 각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있 www.acmicpc.net 이문제는 다른 문제들과는 다르게 몇개 데이터가 입력될지 제공해주지 않는다. 따라서 while 반복문 안에서 더이상 입력이 없을 때 까지 알고리즘을 수행하도록 하면 된다. 입력받은 문자열 구분을 위해 파이썬에서 제공하는 is_ 메소드를 활용했다. from sys import stdin while True: count = [0] * 4 s = stdin.readline().rstrip('\n') ..

https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 수를 입력받으며 바로 갯수를 세기 위해 딕셔너리를 만들어 입력받은 수를 Key로, 해당 숫자가 입력된 횟수를 Value로 저장하도록 했다. 이후 sorted 메소드를 이용해 Value를 기준으로 정렬되게 하였고 오름차순으로 자동 정렬되므로 가장 마지막 원소의 Value값을 찾도록 하였다. 그리고 리스트를 하나 만들어 마지막 원소의 Value와 같은 Value를 가지는 Key값들을 리스트에 삽..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 동적 계획법을 이용해 i = 1부터 N까지 가장 비싼 가격을 계산한다. 예를 들어 dp[4]의 경우에는 P[4], dp[1] + dp[3], dp[2] + dp[2] 중에서 가장 비싼 값을 저장한다. 여기서 4보다 작은 i값의 dp들은 이미 가장 비싼 값이 저장되어 있다고 가정한다. n = int(input()) p = list(map(int, input().split(' '))) dp = [0] * (..