오꾸오꾸(오늘도 꾸준히 오랫동안 꾸준히)

보호되어 있는 글입니다.

순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다. 중간점보다 작기 때문에 왼쪽을 재귀 함수로 불러옵니다. 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 logN에 비례합니다. 2단계를 거치면 8개가량의 데이터만 남습니다. 3단계를 거치면 4개가량의 데이터만 남습니다. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장합니다. def binary_search(array, target, start, end): if start ..

정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 O(N^2) O(N) 아이디어가 매우 간단 삽입 정렬 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때는 가장 빠름 퀵 정렬 O(NlogN) O(N) 대부분의 경우에 가장 적합하며, 충분히 빠릅니다. 계수 정렬 O(N + K) O(N + K) 데이터의 크기가 한정되어 있는 경우에만 사용이 가능 하지만 매우 빠르게 동작 N, K = map(int, input().split()) # 5 3 a = list(map(int, input().split())) # 1 2 5 4 3 b = list(map(int, input().split())) # 5 5 6 6 5 for i in range(K): if a[i] < b[i]: a[i], b[i] = ..

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능 데이터의 개수가 N, 데이터(양수) 중 최댓값이 k일 때 최악의 경우에도 수행 시간 O(N + K)를 보장합니다. 데이터를 돌면서 그 값에 있는 인덱스의 count++해줍니다. # 모든 원소의 값이 0보다 크거나 같다고 가정 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] # 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화) count = [0] * (max(array) + 1) for i in range(len(array)): count[array[i]] += 1 # 각 데이터에..

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다. 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다. 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정 그렇게 되면 pivot값의 위치가 중간으로 들어가게 되고 이제 pivot을 중심으로 왼쪽에 있는 값들을 퀵 정렬해주고 오른쪽에 있는 정렬을 퀵정렬 해줍니다. 퀵 정렬이 빠른 이유 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)를 기대할 수 있습니다. 너비 X 높이 = N x logN = NlogN 퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가집니다. 하지..

삽입 정렬 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다. 선택 정렬에 비해 구현 난이도가 높지만 일반적으로 더 효율적으로 동작 9를 7과 비교합니다. 7보다 더 크기 때문에 오른쪽에 위치에 놓습니다. 0을 9와 비교 9보다 작기 때문에 왼쪽으로 놓고 7과 비교해 작으니 왼쪽 5하고 비교하여 작기 때문에 왼쪽에 놓습니다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): for j in range(i, 0 , -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법 if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동 array[j],array[j - 1] = array[j - 1], arra..

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다. 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[min_index] = array[min_index], array[i] #스와프 print(array) 선택 정렬..

rotatedArraySearch 문제 부분적으로 오름차순 정렬*된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다. 부분적으로 정렬된 배열: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열 예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩니다. 나의 문제 풀이 const rotatedArraySearch = function (rotated, target) { // TODO : 여기에 코드를 작성합니다. // 반복문을 돌면서 target과 같은 value의 인덱스를 리턴한다 // return rotated.indexOf(target) function find..

Achievement Goals Express 라이브러리 express 라이브러리가 어떤 작업을 단순하게 만드는지 이해할 수 있다. express 라이브러리를 사용하는 예시와 그렇지 않은 예시를 들어서 작업을 단순화 차이를 알아보자 if (req.method === 'POST') { if (req.url === '/lower') { let data = ''; req.on('data', chunk => { data = data + chunk; }); req.on('end', () => { data = data.toLowerCase(); res.writeHead(201, defaultCorsHeader); res.end(data); }); } else { res.writeHead(404, defaultCor..

DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 3. 더 이상의 2번의 과정을 수행할 수 없을 때까지 반복합니다. 스택 자료구조로 구현이 가능하다. def dfs(graph, v, visted): # 현재 노드를 방문 처리 visted[v] = True print(v, end =' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 f..