blog...

선택 정렬(selection sort) O($n^2$) 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나감 삽입정렬(insertion sort) O($n^2$) 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬 역정렬된 경우 최악 #삽입정렬1 def insertion_sort1(A) : n = len(A) for i in range(1, n): key = A[i] j = i-1 while j>=0 and A[j] > key: A[j+1] = A[j] j-=1 A[j+1] = key #삽입정렬2 - 더 오래걸림 def insertion_sort2(a): for i in range(1, len(a)): # i 현재 원소..

11. Sieve of Eratosthenes 에라토스테네스의 체→ N보다 작거나 같은 모든 소수 찾기 2~N 모든 수 나열 제거 되지 않은 가장 작은 수 i의 배수들 모두 제거 2를 계속 반복 남아있는 수가 소수 11.1 CountNonDivisible For each number A[i] such that 0 ≤ i < N, we want to count the number of elements of the array that are not the divisors of A[i]. We say that these elements are non-divisors. Write a func that, given an array A consisting of N integers, returns a sequence..

Prime 소수 Composite 복합수 만약 숫자 a가 n의 약수라면, n/a도 n의 약수입니다. 이 두 개의 약수 중 하나가 √n보다 작거나 같습니다. ➔ 1부터 √n까지의 모든 숫자를 반복하면 모든 약수을 찾을 수 있습니다. #약수 갯수세기 함수 def divisors(n): i=1 result=0 while i*i

Maximum slice problem 각 위치에 대해 해당 위치에서 끝나는 가장 큰 합을 계산합니다. 만약 위치 i에서 끝나는 슬라이스의 최대 합이 max_ending과 같다고 가정하면 위치 i+1에서 끝나는 최대 슬라이스는 max(0, max_ending+ $a_{i+1}$ )와 같습니다. #O(n) def golden_max_slice(A): max_ending=max_slice=0 for a in A: max_ending=max(0,max_ending+a) # +가 된다면 max_ending에 계속 쌓아가기 # -라면 0부터 다시 시작하기 # max_slice 찾기 max_slice = max(max_slice, max_ending) return max_slice 9.1 MaxProfit Task..

Leader 리더: 과반초과(more than 2/n)으로 등장한 수를 찾기→ 최대 하나, 없을수있음 리더 찾는 기본 코드 #Lesson8_Leader #O(n) def goldenLeader(A): n=len(A) #제일 많이 등장하는 수 찾기(stack알고리즘과 유사) size=0 for k in range(n): if size==0: size+=1 value=A[k] else: if value!=A[k]: size-=1 else: size+=1 #제일 많이 등장한 수가 과반초과인지 확인 candidate=-1 if size>0: candidate=value leader=-1 count=0 for k in range(n): if A[k]==candidate: count+=1 if count>n//2:..

실력진단 학습내용 값을 반환하지 않는 재귀함수 재귀함수를 이용한 별 출력2 https://www.codetree.ai/missions/5/problems/star-output-with-recursive-function-2?&utm_source=clipboard&utm_medium=text n=int(input()) def draw(n): if n==0: return for i in range(n): print("*",end=' ') print() draw(n-1) for i in range(n): print("*",end=' ') print() draw(n) 값을 반환하는 재귀함수 재귀함수를 이용한 최소공배수 https://www.codetree.ai/missions/5/problems/least-com..

실력진단 dx, dy는 여전히 시간 부족으로 못푸는중 학습내용 그 계절, 그 날 https://www.codetree.ai/missions/5/problems/that-season-that-day?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai def isYoon(Y): leap_Y = False # 윤년인지 아닌지 체크할 변수로 기본 평년으로 체크 if Y % 4 == 0: # 4로 나누어떨어지는지 확인 if Y % 100 == 0: # 100으로 나누어떨어지는지 확인 if Y % ..

실력진단 학습내용 릴레이 문제 풀면서 학습했습니다 문자 삼각형 출력하기 2 https://www.codetree.ai/training-field/home/relay/problems/print-char-triangle-2/description n = int(input()) num = 65 arr = [[' ' for _ in range(n)] for _ in range (n)] for y in range((n//2), -1, -1): for x in range(y, n-y): arr[x][y] = chr(num) num +=1 if num>90: num = 65 for i in range(n): # 세로 크기 for j in range(n): # 가로 크기 print(arr[i][j], end=' ') p..

최대공약수 ➡️유클리드 호제: 2 개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다 두 수를 입력으로 받고 작은 수가 0이 될때 까지 나누기 def gcd(a, b): while (b != 0): r = a % b a = b b = r return a 최소공배수 두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다. def lcm(a, b): return (a * b) / gcd(a, b) def gcd(a, b): while (b != 0): r = a % b a = b b = r return a

실력진단 학습내용 완전탐색 모이자https://www.codetree.ai/missions/5/problems/gather?&utm_source=clipboard&utm_medium=text import sys INT_MAX = sys.maxsize #가독성을 위해 n=int(input()) arr=list(map(int, input().split())) ans=INT_MAX for i in range(n): sum_val=0 for j in range(n): sum_val+=arr[j]*abs(i-j) ans=min(ans,sum_val) print(ans) 괄호 쌍 만들어주기 3 https://www.codetree.ai/missions/5/problems/pair-parentheses-3?&utm_..