뇌의 외장하드

- 정렬되어 있는 데이터들을 비교하며 적절한 위치에 삽입 - 데이터가 거의 정렬 되어 있을 때, 효율적 시간 복잡도 : O(N^2) 최선의 경우 O(N) 공간 복잡도: O(N) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(array)): #첫 번째 데이터는 정렬되어 있다고 판단 for j in range(i, 0, -1): if array[j] < array[j-1]: array[j], array[j-1] = array[j-1], array[j] else: break 정렬 전체가긔 이것이 코딩 테스트다 - 나동빈 정리하긔

- 기준에 가장 적합한 데이터를 선택해 (정렬된 데이터 제외) 맨 앞의 데이터와 교환하는 것을 반복 - 원시적인 방법, 비효율적임 시간 복잡도 : O(N^2) ≒ (N^2 + N)/2 ≒ N! ≒ 연산 횟수 공간 복잡도: O(N) 연산 횟수: N + (N-1) + (N-2) + ... + 2 N개 확인, 정렬된 1개의 데이터를 제외하고 확인 ... 마지막 하나 남은 경우는 확인하지 않아도 됨 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[m..

정렬이란? - 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 - 공식처럼 사용 (이진 탐색의 전처리 과정 등) 선택 : O(N^2), 거의 사용 X 삽입 : O(N) ~ O(N^2), 정렬이 거의 된 경우 가장 빠름 퀵 : O(NlogN) ~ O(N^2), 이미 정렬이 된 최악의 경우가 N^2 계수 : O(N+K), N: 개수 K: 최대값 파이썬 기본 정렬 라이브러리: O(NlogN) 보장 1. 단순히 정렬 기법을 아는지 묻는 문제 (정렬 라이브러리 사용 시 가능) 2. 정렬 알고리즘의 원리를 묻는 문제 3. 빠른 알고리즘이 필요한 문제 (기존의 알고리즘에 구조적인 개선을 거쳐야함) tip. 별도의 요구사항이 있는 경우(데이터 한정, 동작 시간 단축), 계수 정렬 사용이 유리 1. ex) 위에서 아..

일반적으로 2차원 공간은 행렬의 의미로 사용 → Column(열) ↓ Row (행) (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0) (2, 1) (2, 2) 시뮬레이션 및 완전탐색 문제에서 방향 벡터가 자주 활용됨. 1번 방법 #동, 서, 남, 북 dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] # 현재 위치 x, y = 1, 1 for i in range(4): # 다음 위치 nx = x + dx[i] ny = y + dy[i] print(nx, ny) 2번 방법 #동, 서, 남, 북 step = [(0, 1), (0, -1), (-1, 0), (1, 0)] # 현재 위치 row, column = 1, 1 for i in range(4): # ..

그리디 알고리즘이란? - 현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘 - 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려 x 1. 단순히 현재 상황에서 가장 좋아 보이는 것만 반복적으로 선택해도 최적의 해를 구할 수 있는가 2. 정당한가(정당성 분석) tip. 기준에 따라 좋은 것을 선택함으로 문제에서 "가장" 에 대한 기준을 알게 모르게 제시해 줌. ex) 거스름 돈 더보기 닫기 닫기 #거스름 돈 문제(3_1) n = 1260 count = 0 coin_types = [500, 100, 50, 10] for coin in coin_types: count += n//coin n %= coin print(count) 1. 가장 큰 화폐 단위부터 돈을 거슬러 주면 됨..