전체 글 138

BAEKJOON_1789 "수들의 합" PYTHON

[백준] 1789번 Python 파이썬 https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 이 문제에서 N의 최대값을 구하려면 작은 수들을 더하여 S를 만들어야한다. s를 입력받아 s가 1인 경우와 1이 아닌 경우로 나누어 문제를 해결하였다. 아래 코드의 경우 시간 복잡도가 O(sqrt(s)) 이고, 입력이 클 수록 복잡도가 증가한다. s = int(input()) result = 0 for i in range(1, s + 1): if s == 1: result = 2 break else: s -= i result += 1 if s < 0: break print(r..

BAEKJOON_10211 "Maximum Subarray" PYTHON

[백준] 10211번 Python 파이썬 https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 이 문제는 전체 배열에서 최대 부분합을 구하는 문제로 Kadane's Algorithm을 사용하여 해결하였다. Kadane's Algorithm은 다이나믹 프로그래밍을 적용한 방식이다. import sys n = int(sys.stdin.readline()) for _ in range(n): m = i..

BAEKJOON_13241 "최소공배수" PYTHON

[백준] 13241번 Python 파이썬 https://www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다 www.acmicpc.net 1934번과 같은 방법으로 최소공배수를 구하였다. https://rilla0511.tistory.com/94 BAEKJOON_1934 "최소공배수" PYTHON [백준] 1934번 Python 파이썬 https://www.acmicpc.net/problem/1934 1934번: 최소..

BAEKJOON_2851 "슈퍼 마리오" PYTHON

[백준] 2851번 Python 파이썬 https://www.acmicpc.net/problem/2851 2851번: 슈퍼 마리오 첫째 줄에 마리오가 받는 점수를 출력한다. 만약 100에 가까운 수가 2개라면 (예: 98, 102) 마리오는 큰 값을 선택한다. www.acmicpc.net 1. 10개의 정수를 입력 받아 num 리스트에 저장한다. 2. num_sum 리스트에 num 리스트의 i+1 개의 정수 합을 각 요소로 저장한다. 3. df는 abs 함수를 이용하여 num_sum의 첫 번째 원소와 100의 차이로 초기화하고, result는 num_sum의 첫 번째 요소로 초기화한다. 4. for문을 이용하여 num_sum의 두 번째 요소부터 각 요소와 100의 차이를 계산하고, df..

BAEKJOON_2559 "수열" PYTHON

[백준] 2559번 Python 파이썬 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 아래의 코드는 O(nk)의 시간 복잡도를 갖기 때문에 n과 k의 크기가 클 경우 오랜 시간이 걸린다. import sys n, k = map(int, sys.stdin.readline().split()) tp = list(map(int, sys.stdin.readline().split())) lt = [[0] for i i..

BAEKJOON_2167 "2차원 배열의 합" PYTHON

[백준] 2167번 Python 파이썬 https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 11660 문제와 유사하여 행렬의 크기 등만 조금 수정하였다. 아래 사이트 참고! https://rilla0511.tistory.com/95 BAEKJOON_11660 "구간 합 구하기 5" PYTHON [백준] 11660번 Python 파이썬 https://www.acmicpc.net/problem/11660 11660번: 구간..

BAEKJOON_11660 "구간 합 구하기 5" PYTHON

[백준] 11660번 Python 파이썬 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 입력받은 x1, y1, x2, y2 값은 인덱스와 1씩 차이가 있으므로 입력받은 값에서 1씩 빼주었다. import sys n, m = map(int,sys.stdin.readline().split()) tb = [[0 for j in range(n)] for i in range(n)] # n*n의 빈행렬을 만들어..

BAEKJOON_1934 "최소공배수" PYTHON

[백준] 1934번 Python 파이썬 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net for문을 이용하여 최소공배수를 구했더니 시간 초과가 떴다. import sys n = int(sys.stdin.readline()) result = 1 for i in range(n): a, b = map(int, sys.stdin.readline().split()) for j in range(max(a, b)..

BAEKJOON_10798 "세로읽기" PYTHON

[백준] 10798번 Python 파이썬 https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 'words'라는 행렬을 생성한다. 문제에서 알파벳 또는 숫자가 입력된다고 했으므로 '*'가 들어있는 행렬을 만들었다. 이 행렬은 15*5의 크기이다. 이 행렬에 입력은 문자를 한 글자씩 넣어주어 문자가 입력되지 않은 행을 제외하고 세로로 출력해주었다. words = [['*' for j in range(15)] for i in range(5)] f..