문제출처] https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제요약 좌표의 순위를 입력받은 순서대로 출력 풀이 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline n = int(input()) list_dots = [] # 인덱스를 저당하는 리스트를 만든다. for i in range(n): list_dots.append([i,0])..

문제출처] https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제요약 nPr 을 구하는 문제 풀이 파이썬의 라이브러리 itertools 안에 있는 permutations 사용 from itertools import permutations 소스코드는 Python 3으로 작성되었습니다. from itertools import permutations n, m = map(int,input().split()) nums = [i for i in range..

문제출처] https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제요약 산술평균, 중앙값, 최빈값, 범위를 구하는 문제 풀이 산술평균 소수점 이하 첫 째 자리에서 반올림하기 위해 round() 를 이용한다. average = int(round((sum(datas)/n))) round(number,n)은 소수점 n번 째 자리까지 반올림을 수행한다. 중앙값 데이터를 정렬한 후 데이터의 길이 ÷ 2 를 인덱스로 하는 값을 갖는다. datas.sort() center ..

문제출처] https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제요약 시간 제한과 메모리 제한이 있어 Counting Sort를 이용해 정렬을 수행하는 문제 풀이 카운팅 정렬(계수 정렬)은 데이터 셋이 특정한 범위로 제한되어 있을 때 속도를 높일 수 있는 정렬 방식이다. 데이터를 인덱스로 가지는 배열에 카운트를 1씩 증가시키는 방식으로 정렬이 수행된다. input() 을 이용할 때보다 sys.stdin.readline() 을 이용할 때 수행 속도가 향상된다. 소스코..

문제출처] https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제요약 골드바흐의 추측을 구현 풀이 먼저 4 ≤ n ≤ 10,000 인 범위에서 소수를 판별하기 위해 에라토스테네스의 체를 이용한다. 에라토스테네스의 체는 소수인 수의 배수들은 소수가 아님을 이용한다. list_number = [True for _ in range(10001)] for i in range(2, 10001): if list_number[i]: for ..

문제출처] https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제요약 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램 구현 풀이 파이썬에서는 딕셔너리 자료구조를 이용하면 그래프를 손쉽게 구현할 수 있다. n, m = map(int, input().split()) graph = {i: [] for i in range(1, n+..