코딩 테스트/알고리즘 꿀팁 정리 (5) 썸네일형 리스트형 [정렬 알고리즘 정리] [정렬] 선택정렬(Selection Sort) : -> 한바퀴를 돌며 가장 작은 수를 선택해 맨 앞으로 보낸다 -> 두 번째 값부터 한바퀴 돌며 가장 작은 수를 찾아 두 번째로 보낸다. 삽입정렬 : 데이터를 하나씩 확인하여 적절한 위치에 삽입하기 -> 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다. 퀵정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 계수정렬(counting sort) : * 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다. * 인덱스값을 늘리고, 데이터 최댓값의 크기만큼 반복을 수행해야 한다. => 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다. * 기수행렬(Radix sort)과 .. 이것이 코딩 테스트다 :: 이진 탐색 순차 탐색 시간복잡도 : O(N) N개의 데이터를 차례대로 하나씩 확인하는 방법 이진 탐색 시간복잡도 : O(logN) 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. N개의 데이터를 절반씩 좁혀가며 데이터를 탐색하는 방법 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 원소의 개수가 절반씩 줄어든다는 점에서 시간복잡도는 O(logN)이다. 퀵 정렬과 공통점이다. 재귀함수 이용하는 방법과 반복문을 이용하는 방법 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해보자. 시작점과 끝점은 모두 index를 의미한다. // 기호나 int형변환은 모두 단방향(정수 부분 남김)으로 동작하.. 이것이 코딩 테스트다 :: 구현 코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다룬다. 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다. 이것이 코딩 테스트다 :: 그리디 단순하지만 강력한 문제 해결 방법이다. 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘으로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘과 자주 짝을 이뤄 출제된다. 탐욕적인 해결법이 존재하는지 고민해보자. 해결 방법을 찾을 수 없다면, 이후의 장에서 다루게 될 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 재차 고민해보는 것도 한 방법이다. 문제풀이 [파이썬 순열 조합 정리] 2. 구현(탐색) - from collections import Counter # 딕서녀리 - from itertools import permutations, combinations # 하나의 리스트에서 모든 케이스 구하기 - from itertools improt product # 두 개 이상의 리스트의 조합 구하기 3. DFS/BFS - from collections import deque [DFS] - 재귀함수 [BFS] queue = deque() (append, popleft, queue.reverse) - 최단거리(가중치 1) - 인접리스트 : graph = [[] for _ in range(3)] 5. 이진탐색 * 순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 .. 이전 1 다음
