Why? 배열을 정렬할 때, 아래 문제처럼 원하는 기준으로 정렬을 하고 싶을 때가 있을 것이다! https://programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 이러한 경우에 key에 단순한 lambda식을 넣어서 문제를 해결할 방법이 떠오르지 않는다! 사용법 커스텀 정렬을 하고 싶다면 아래처럼 cmp_to_key를 임포트한 후 커스텀 함수를 만들어서 리턴값을 ..

Binary search 배열이 정렬되어 있을 경우, 절반씩 줄여나가면서 탐색하는 기법 이진 탐색을 사용하기 위해서 배열이 꼭 정렬되어 있어야 한다!! left = 0, right = 배열의 길이 - 1, mid = (left + right) // 2로 시작해서 만약 찾고자 하는 값이 mid 인덱스에 해당하는 값보다 크면 left = mid + 1로 바꿔주고 찾고자하는 값이 mid 인덱스에 해당하는 값보다 작으면 right = mid - 1로 바꿔주면서 left가 right보다 크거나 같을 때까지 반복해준다! 예시 - 4의 위치 찾기 a = [1, 2, 3, 4, 5, 6, 7, 8] 일 때, left = 0, right = 1, mid = (left + right) // 2 = 3 로 시작한다 a[mi..

퀵 정렬 - Quik sort 분할 정복(Divide and Conquer)을 이용해서 배열을 정렬하는 알고리즘 배열에서 기준(pivot)을 정해서 기준보다 작은 집합과 큰 집합으로 나누고(Divide) 그 사이에 기준을 위치시킨다. 작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬(Conquer)한 뒤 결과를 합치면 정렬된 배열을 구할 수 있다! 시간 복잡도는 최선일 때 O(NlogN) 최악일 때(내림차순으로 정렬되어 있거나 오름차순으로 정렬되어있을 때) O(N^2) 예시 1단계 마지막 원소인 4를 기준(pivot)으로 정하고 pivot보다 작은 집합의 인덱스 i를 -1로 설정한다 (맨 왼쪽 인덱스-1) → i보다 같거나 작은 인덱스에 해당하는 값은 전부 pivot보다 작은 값이다 j는 pivot에 해..

버블 정렬(bubble sort) 첫번째와 두번째, 두번째와 세번째, N-1번째와 N번째 요소를 비교해 나가면서 정렬을 하는 방법 만약 N-1번째와 N번째 요소를 비교했다면 다시 첫번째와 두번째 요소부터 N-2번째와 N-1번째 요소를 비교한다! 만약 오름차순으로 정렬하려면 매번 두 요소를 비교할 때마다 작은 요소와 큰 요소의 위치를 바꾼다 반복문 두개를 중첩해서 사용하므로 시간복잡도는 O(N^2) 예시 소스코드 def bubblesort(lst): lst_len = len(lst) - 1 for i in range(lst_len): j = lst_len - i for k in range(j): if lst[k] > lst[k + 1]: lst[k], lst[k + 1] = lst[k + 1], lst[k..

이진 트리 모든 노드가 최대 두개의 자식을 가지는 트리 하위 노드가 3개 이상이면 안되고 무조건 0, 1, 2개 있어야 한다! 완전 이진 트리 노드를 삽입할 때 최하단 왼쪽부터 차례로 삽입하는 이진 트리 완전 이진 트리를 배열로 표현 BFS로 탐색을 할 때 왼쪽에서부터 읽어서 넣는다고 생각하자! 완전 이진 트리 노드 갯수 레벨을 n이라고 하면각 레벨에 최대로 들어갈 수 있는 노드의 수는 2^k개이다. 완전 이진 트리의 높이 트리의 높이는 루트 노드부터 가장 아래 리프노드 까지의 길이이다. 아래 같은 경우 2 - 0 = 2, 즉 높이가 2다 만약 높이가 h 일때, 최대 노드 갯수가 N이라고 하면 N = 2^(h+1) - 1개이다! N = 2^(h+1) - 1 → h = log2(N+1) - 1 으로 노드의..

등장 배경 기존 Cookie와 Session 기반(세션 기반)의 인증의 문제 기존 Cookie와 Session을 이용한 세션 기반 인증은 HTTP의 Stateless 프로토콜의 특징을 해결하기 위해 등장했다. 세션 기반 인증은 사용자의 인증 정보를 세션 형태로 서버 내에 저장하고 인증이 필요할 때마다 session-ID로 검증을 했다. → 매번 요청이 일어날 때마다 세션 저장소를 조회해서 session-ID를 검증해야 한다! → DB에 접근하는 로직이 한번 더 수행됨! 가장 큰 단점은 서버에 메모리를 저장하기 때문에 서버가 클라이언트가 요청하는 데이터에 응답함과 동시에 사용자의 인증 정보도 관리해야 했다. 즉, 접속한 사용자가 증가하면 서버가 그만큼 과부하가 일어난다는 의미이다. → HTTP의 장점인 S..