2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 분석 N(1 ≤ N ≤ 1,000,000) nlogn 병합정렬로 풀이 시간복잡도, 시간제한, 빅오(Big-O) 표기법 1초 제한 n으로 구성된 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다. 예를 들어 N의 최대값이 10만이라고 문제에서 주어진다면 1. O(N) 의 시간복잡도일 경우에 값이 10만 karla.tistory.com 풀이 import sys input=sys.stdin.readline n=int(input()..

11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 내장함수 풀이 n=int(input()) a=list(map(int,input().split())) a.sort() s=[0]*n # 합배열 s[0]=a[0] for i in range(1,n): # 합배열 만들기 s[i]=s[i-1]+a[i] total=0 for i in range(0,n): # 합배열 총합 구하기 total+=s[i] print(total) 삽입정렬 풀이 n=int(input()) a=list(map(int,input().split())) s=[0]*n # 합배열 # 삽입..

1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 내장함수 풀이 a=list(input()) a.sort(reverse=True) for i in range(len(a)): print(a[i], end="") 선택정렬 풀이 """ 1427 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬 N이 주어진다. N(1~1,000,000,000) 9 2143 """ a=list(input()) length=len(a) for i in range(length): maxIdx=i for j in range(i+1,length): if a[j]>a[maxIdx]: maxIdx=j if a[i]

1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 분석 버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제 버블정렬의 이중 for 문에서 안쪽 for 문 전체를 돌 때 swap이 일어나지 않았다 == 이미 모든 데이터가 정렬됐다 N은 500,000보다 작거나 같은 자연수 : n^2불가 안쪽 루프는 1에서 n-j까지 swap 수행, 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이므로 데이터의 정렬 전 인덱스와 정렬 수 인덱스를 비교..

11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 분석 세그먼트 트리, 인덱스 트리, 구간합 1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 karla.tistory.com 풀이 """ 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 ..

14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 풀이 """ 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다. 입력으로 주어지는 문자열은 알파..