old/Programming (103) 썸네일형 리스트형 퀵정렬 Quick Sort 정의 오름차순으로 정렬하는 기초적인 알고리즘 중 하나 가장 중요한 알고리즘. 어떤 언어든 가장 중요하고 많이 씀. 실무에서 많이 사용. 최악의 상황을 줄이는 법은 랜덤으로 위치를 선정. 그래도 $O(n^2)$이 절대 있어서는 안된다면, 다른 정렬을 사용해야 함. 구조 부분 정복 Decrease and Conquer 알고리즘 순서 pivot을 기준으로 둘로 나눠서 재귀적으로 순회. pivot값보다 작은 값은 왼쪽 큰 값은 오른쪽으로 분류한다. 단 길이변환을 하지 않기위해 아래 과정을 진행한다 기준점인 pivot을 정한다. 보통 맨 오른쪽 값 혹은 맨 왼쪽값을 잡음(로무토 or 호어 분할법에 따라 다름) 첫번째 값을 선택값라고 정한다. 체크하는 값이 pivot값보다 작으면, 선택값과 체크하는 값을 교환하고 .. 삽입 정렬 Insertion Sort 정의 오름차순으로 정렬하는 기초적인 알고리즘 중 하나 기법 무차별 대입 Brute Force 알고리즘 순서 첫번쨰부터 마지막 까지 순회한다 순회하는 수와 왼쪽에 있는 수를 비교한다. 만약에 왼쪽의 수가 오른쪽 보다 크다면 작은수를 왼쪽 큰수를 오른쪽에 넣는다 앞에서 비교되었으니 왼쪽을 한번더 비교 하여 작은수를 왼쪽 큰수를 오른쪽에 넣는다 왼쪽의 수가 오른쪽 보다 크지 않다면 더이상 비교할 필요가 없다 마지막 까지 반복한다. 자바 코드 public static int[] insertSort(int[] input) { for (int i = 1; i 0) { if (input[chkPos - 1] > inpu.. 파이썬의 자료구조-리스트 List 리스트 List 정의 파이썬의 자료구조 중 하나 다른 언어의 어레이array와 매우 비슷함. 파이썬 자료구조의 종류 리스트 List 튜플 Tuple 딕션어리 Dictionary 셋 set 선언 temp=[] temp=list() temp=[5,9,44] 인덱싱 특징 list안에 list 넣기 가능 - 이 경우 이는 다른 언어의 2D array와 같음 string 역시 기본적으로 array이므로, 똑같은 현상이 발생 슬라이싱 [시작 인덱스 : 마지막 인덱스-1 : 조건 인덱스] [0:8:3] = index 0 에서 7 까지 3을 더해가며 선택하라 [:8:] = index 0 에서 7 까지 1을 더해가며 선택하라 [7::] = index 7 에서 -1 까지 1을 더해가며 선택하라 [::-1] = index .. 선택정렬 Selection Sort 정의 오름차순으로 정렬하는 기초적인 알고리즘 중 하나 기법 무차별 대입 Brute Force 알고리즘 순서 순회해서 최소값을 찾는다 첫번째 값과 최소값을 스왑한다 두번쨰 값부터 순회해서 최소값을 찾는다 두번쨰 값과 최소값을 스왑한다 마지막 직전까지 반복한다. 자바 코드 public static int[] selectionSort(int[] input) { for (int i = 0; i i; --j) { if (input[j] < input[i]) { int temp = input[i]; input[i] = input[j]; input[j] = temp; } } } return input; } 평균.. 버블정렬 Bubble Sort 정의 오름차순으로 정렬하는 기초적인 알고리즘 중 하나 기법 무차별 대입 Brute Force 알고리즘 순서 두 숫자(첫번째와 두번째)를 비교하며 순회한다 두 숫자를 비교하여, 작은수를 왼쪽, 큰수를 오른쪽으로 이동시킨다. 첫번째 선회를 하면, 맨 오른쪽에 가장 큰 수가 위치하게 된다 마찬가지로 하나씩 줄여가며 순회하면 완성 자바 코드 public static int[] bubbleSort(int[] input) { for (int i = 0; i input[j + 1]) { int temp = input[j]; input[j] = input[j.. [Java코드]알파벳 오더로 정렬하기 알파벳 오더로 정렬하기 아스키 코드 룰에 따라서 [숫자][대문자][소문자]로 정렬됩니다 0 ~ 9, A ~ Z, a ~ z Time complexity : O( log n) Space complexity : O(1) List Collections.sort(List_values); Array Arrays.sort(String[]array); Time complexity : O(n^2) Space complexity : O(1) public static String[] LexicalOrder(String[] words) { int n = words.length; for (int i = 0; i < n - 1; ++i) { for (int j = i + 1; j < n; ++j) { if (words[i].c.. 무차별 대입Brute force 알고리즘 정의 가능한 경우의 수를 모조리 시도해서 결과 값을 찾는 방법 특징 효율성을 고려하지 않음. 가장 직관적인 문제 해결 방법 기하급수적exponential growth으로 증가함 exhaustive search 완전 검색 기법이기도 함 예제 Brute force로 비밀번호를 찾을 경우, n=비밀번호 자릿수, 4 k=각 자리에 들어갈수 있는 문자수, 0~9 라고 할때 경우의 수는 kn=104=10000k^n=10^4=10000kn=104=10000 숫자로만 구성된 4개짜리 비밀번호는 총 10000개 이고. 이정도는 컴퓨터로 시도한다면 1초안에 시도가 가능한 숫자량입니다. 또한, 비밀번호 자릿수가 4를 넘어가는 순간부터 기하급수적exponential growth으로 증가합니다. 그래서 비밀번호는 길수록 좋음 탐색 알고리즘의 종류 탐색 알고리즘의 종류 선형 탐색 이진 탐색 해쉬 선형 탐색 알고리즘 Linear Search Definition 전체 리스트를 하나씩 확인해 가며 찾는 방법 Time complexity O(n) 특징 모든 데이터 타입에 사용 가능 n만큼의 용량 필요 이진 탐색 알고리즘 Binary Search Definition 전체 리스트에서 가운데를 비교하고 그 수가 원하는 수보다 작을 경우, 왼쪽의 작은 숫자 리스트는 버리고 나머지 오른쪽에서 다시 찾는 방법. 절반씩 줄여가며 찾는 방법 Time complexity O(log n) 특징 전제 조건: 정렬이 되어 있어야 함 전제 조건: 입력할때마다 재 정렬 필요. 입력할때마다 재정렬이 필요하므로, 출력보다 입력이 많을 경우 프로그램이 느려질수 있음 divide-and.. 이전 1 ··· 5 6 7 8 9 10 11 ··· 13 다음
