#2108 통계학 1. from collections import Counter 모듈 사용 - Counter()를 사용하면 다음과 같이 빈도수와 리스트를 dictionary 형태로 저장해준다. - most_common()을 사용하면 빈도수로 정렬하고 dictionary를 list[tuple()] 형태로 저장해준다. from collections import Counter colors = Counter(['blue', 'green', 'red', 'blue','red','blue']) print(colors) # Counter({'blue': 3, 'red': 2, 'green': 1}) print(colors.most_common()) # [('red', 3), ('blue', 2), ('green', ..

# 백준 11050 이항계수 1 1. 이항 계수에 대한문제인데 푸는방법은 2가지가 있다. python 내장함수인 math를 이용하거나 재귀함수를 사용하거나 물론 재귀함수를 연습하도록 하는것이 이 문제의 목적이겠지만, 어느것이 더 빠를까에 대한 궁금증이 생겨서 실험해 보았다. 2. 결과는 비슷...(당연한건가?) import math a,b = map(int, input().split()) print(math.comb(a,b)) n,k = map(int, input().split()) def fac(a): if a == 0: return 1 if a == 1: return 1 else: return a*fac(a-1) print(fac(n)//(fac(n-k)*fac(k)))

#1920 수찾기 1. 시간초과 코드(매우매우 직관적인 코드) import sys input = sys.stdin.readline() n = int(input) a = list(map(int,input.split())) m = int(input) x = list(map(int, input.split())) for i in range (n): if m_arr[i] in n_arr: print(1) else: print(0) 2. 이진탐색 이용(576ms) import sys def BinarySearch(a,x): start = 0 end = len(a)-1 while starta[mid]: start = mid+1 else: end = mid-1 return 0 n = int(input()) a = li..

1. map()함수 ==> 반복가능한 자료형을 원하는 자료형으로 mapping해줌 ==> mapping후 map 객체로 반환 2. list(map()) ==> map객체를 list 형태로 바꿔줌 (ps. 백준 4153번을 풀다가 map에서 list로 변환해주는 과정이 없으면 오류가 난다는 것을 깨닫고 쓰는 글)

백준 10814 나이순정렬 처음에 1번코드로 실행했는데 결과는 맞았지만 시간이 무진장 오래걸린다... 그래서 좀 더 나은 방법을 찾던중 예전부터 계속 봐왔던 sys를 이용해보았다. 입력 데이터가 많아질수록 시간차이가 많이 난다고 이론적으로는 알고있었지만, 실제로 적용하니깐 정말 다르다...! 앞으로도 sys를 사용할예정...!

1) 계수 정렬이란? 반드시 어떠한 범위안에 존재하는 데이터들로 이루어진 데이터 배열에 한하여 데이터의 크기를 기준으로 카운트하여 정렬하는 알고리즘이다. 2) 계수 정렬의 시간복잡도 크기를 기준으로 개수를 세어주기 때문에 위치를 바꿀 필요가 없다. 따라서 O(n)이다. 3) 계수 정렬 구현 #include int main() { int A[10] = { 1, 4, 5, 2, 2, 4, 1, 3, 5, 3 }; int count[5];//빈도수 측정결과를 담을 배열 for (int i = 0; i < 5; i++) { count[i] = 0; } for (int i = 0; i < 10; i++) { count[A[i]]++; } for (int i = 0; i < 5; i++) { if(count[i] ..

1) 퀵 정렬이란? 기준이 되는 수(pivot)를 수열 안에서 임의로 선택한 후 'pivot 보다 작은 수'와 'pivot 이상인 수'의 두 그룹으로 나누고 이것을 배치 2) 퀵 정렬의 시간복잡도 각 층에서 각 숫자는 pivot과 1회만 비교되므로 한 층의 계산 시간은 O(n)이 되고, 전체 계산 시간은 O(n log n)이다. 3) 퀵 정렬 구현 #include void quickSort(int* data, int start, int end) { if (start >= end) { return; } int pivot = start; int i = start + 1; int j = end; int temp; while (i j) { // 엇갈리면 피벗과 교체 temp = data[j]; data[j] =..

1) 병합 정렬이란? 정렬하고 싶은 수열을 두 개의 수열로 분할해 간다. 더 이상 분할되지 않는 상태(즉, 각 그룹이 한 개의 숫자가 된 경우) 그룹들을 병합해 나간다. 병합할 때에는 정렬이 끝난 두 개의 수열을 병합해서 정렬이 끝난 하나의 수열로 만들고, 이것을 전체가 하나의 그룹이 될 때까지 반복한다. 2) 병합 정렬의 시간복잡도 병합 정렬에서 숫자를 분할해 갈 때는 계산 시간이 걸리지 않는다. 사실상 처음부터 분할된 상태라고 생각해도 무방하다. 두 개의 정렬이 끝난 수열을 병합하는 부분은, 선두의 수를 비교해서 작은 쪽을 위로 올리는 것을 반복하는 것이 전부이므로 두 수열의 길이에 따라 달라진다. 따라서 하나의 층에서 병합 계산 시간은 그 층에 있는 숫자의 수가 된다. 어떤 층을 봐도 숫자는 n개 ..

1) 힙 정렬이란? 힙이라는 데이터 구조를 사용하여 정렬하는데, 최소값이나 최대값을 찾는데 최적화되어있는 완전이진트리 형태의 자료구조이다. 2) 힙 정렬의 시간복잡도 힙 정렬을 위해 n개의 숫자를 힙에 저장할 때 걸리는 시간은 O(n log n)이 된다. 1회 추가에 O(log n)의 시간이 걸리기 때문이다. 또한, 각 라운드에서 최대 숫자를 꺼내서 힙을 재구축하는 데 걸리는 시간은 O(log n)이다. 라운드 수는 n이므로 힙이 완성된 후에 정렬하는 시간도 n*O(log n)이 된다. 따라서 힙 정렬의 계산시간은 전체적으로 O(n log n)이다. 버블 정렬, 선택 정렬, 삽입 정렬의 O(n^2)에 비해 빠른 속도지만, 복잡한 데이터 구조를 구현하는 것이 어렵다. point! 힙 정렬의 전체 시간 복잡..