[알고리즘] 정렬 (선택정렬, 삽입정렬, 퀵정렬, 계수정렬)
정렬 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 이진 탐색을 하기위한 전처리과정 선택정렬, 삽입정렬, 퀵정렬, 계수정렬만 다뤄보자 선택 정렬 O(N^2) 가장 작은것을 선택하여 맨 앞과 바꾼다 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦으므로 선택정렬 소스코드에 익숙해지자 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스, i번째 인덱스와 바꿀 가장 작은 인덱스를 찾는다. for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index =j array[i], array[min_inde..
2021. 3. 17.
[알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬)
순열과 조합 경우의수 한 번의 시행에서 일어날 수 있는 사건의 가지 수 재귀 함수, 반복문을 이용해서 직접 구현 가능하지만 실제 코딩테스트에서 직접 구현하기는 매우 번거롭다 순열 (Permutation) 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것 $nPr = n! / (n-r)!$ 코딩테스트에서는 경우의 수 값만 출력하는 것이 아니라 모든 경우(사건)를 다 출력하도록 요구 파이썬 itertools 라이브러리를 이용한다. import itertools data = [1, 2, 3] for x in itertools.permutations(data,2): print(list(x), end= '') # [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] 조합 ..
2021. 3. 15.
[백준] [브루트포스] 분해합 2231 (파이썬)
문제접근 범위가 100만으로 제한된 다는 것은 많은 탐색을 요구할 때 보통 100만으로 주어진다. 여러 생성자를 담아서 그 중에서 작은 값을 구하는 것 코드 # 분해합 n = int(input()) divide_list = [0,1,10,100,1000,10000,100000,1000000] # 연산을 할 배열을 미리 생성한다. arr = [] # 생성자 리스트 for i in range(1,n): # 1부터 자기보다 작은 수를 탐색한다. next_num_list = [i] # 생성자를 만들 리스트 temp_num = i # 계산을 수행할 번호 for j in range(len(str(i)),0,-1): # ex) 100이면 1의자리 10의자리 100의자리 총 3번 탐색해야하므로 위와 같이 범위를 설정한..
2021. 3. 15.
