Developer Cafe

컴퓨터 정렬에서 실제로 가장 많이 쓰이는게 바로 내장 정렬 함수 퀵 정렬이다. 퀵 정렬은 매우 빠른 알고리즘으로 특히 평균 시나리오 에서 효율적이다. 분할 분할은 배열로부터 임의의 수를 가져와(이 수를 피벗이라 부름) 피벗보다 작은 모든 수는 왼쪽, 큰 수는 오른쪽에 둔다. 1 4 2 3 임의의 수 를 선택(2선택 피벗지정) 후 왼쪽 포인터(1)과 오른쪽 포인터(3)을 고른다. 1. 왼쪽 포인터를 한 셀씩 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다. 2. 오른쪽 포인터를 한 셀씩 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다. 3. 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한다. 4. 두 포인터가 가리키는 값이 같거나 왼쪽 포인터가 오른쪽 포인터 바로 오른쪽..

컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. function ex() { ex(); } 재귀에서 메서드가 반복되지 않는 경우를 기저 조건(중단 조건) 이라 부른다. 재귀를 다루는 컴퓨팅 사고 function factorial(number) { if (number === 1) { return 1; } else { return number * factorial(number - 1); } } factorial(3); 위의 코드를 실행시키면 일어나는 컴퓨팅 사고 1. factorial(3)이 먼저 호출된다. 2. factorial(2)가 두 번째로 호출된다. 3. factorial(1)이 세 번째로 호출된다. 4. factorial(1)이 먼저 완료된다. 5. facto..

스택과 큐는 제약을 갖는 배열로 이 제약으로 인해 자료 구조가 매우 간결해진다. 두 자료 구조는 임시 데이터를 처리할때 사용하고 오래 데이터를 사용할 때는 사용하지 않는다. 마치... 음식 주문서같이(식사준비부터 배달까지만 필요하니깐) 스택 스택에는 3가지 제약이 존재한다. ● 데이터는 스택의 끝에만 삽입할 수 있다. ● 데이터는 스택의 끝에서만 읽을 수 있다. ● 데이터는 스택의 끝에서만 삭제할 수 있다. 스택에 삽입하는걸 푸시, 제거하는걸 팝 이라한다. 예를 들어 (var x = {y: [1, 2, 3]})이라는 코드에 괄호 를 빼먹었는지 검사하고싶다면 스택을 사용한다. 1. 괄호((),{},[]) 외엔 전부 무시한다. 2. 처음 ( 이 나왔으니 ( 을 푸시한다. ( 3. 다음 { 이 나왔으니 { 을..

해시테이블은 키값이 있는 테이블이다. [ ["사과", 1000] ["바나나",1500] ["포도",2000] ] 그럼 컴퓨터는 어떻게 값을 저장하고 읽어들일까.. 먼저 문자를 숫자로 변환하는 해싱작업을 한다. 이때 각 문자는 지정되어 있는데 예를 들어 ABC라는 값은 A = 1, B = 2, C = 3 으로 되어있을경우 1*2*3 = 6 으로 해싱한다 ABC에 값으로 apple를 넣으면 아래 그림과 같이 표현된다. "apple" 문제는 BAC에 pop이라는 값을 저장할때이다. 마찬가지로 2*1*3 = 6 이니 셀이 중복된다. 이때 해시는 배열처럼 자리를 나누어 저장한다. ["ABC","apple"]["BAC","pop"] 해시값을 찾을때는 선행검색으로 하나하나 차례대로 찾게 된다. 만약 중복된셀이 없으면..

기준 인덱스 다음 원소값을 임시 변수에 저장해 그 값을 왼쪽 원소들과 차례로 비교해 임시 변수의 값이 왼쪽 원소값보다 작다면 앞으로 시프트시키며 정렬한다. 패스스루1 인덱스 1의 값 2는 임시변수에 저장 4 2 7 1 3 앞의 원소값들과 비교 후 시프트한 후 저장 2 4 7 1 3 패스스루2 인덱스 2의 값 7은 임시변수에 저장 2 4 7 1 3 앞의 원소값들과 비교 후 시프트한 후 저장 (임시변수값이 더 크다 고로 그대로 저장) 2 4 7 1 3 패스스루3 인덱스 3의 값 1은 임시변수에 저장 2 4 7 1 3 앞의 원소값들과 비교 후 시프트한 후 저장 1 2 4 7 3 패스스루4 인덱스 4의 값 3은 임시변수에 저장 1 2 4 7 3 앞의 원소값들과 비교 후 시프트한 후 저장 1 2 3 4 7 삽입정..

인덱스 0부터 패스스루하는데 각 시점의 최솟값을 구해 그 최소값과 같은 원소값고 시작 인덱스 원소값만 바꾼다. 최솟값(2) 최솟값(2) 최솟값(1) 최솟값(1) 2 6 1 4 1 6 2 4 이후 인덱스 0은 값이 정해졌으니 인덱스 1부터 다시 반복한다. 선택 정렬일때는 (N-1) + (N-2)... + 1 = 번의 비교가 나타난다. 비교단계는 버블정렬과 같다. 하지만, 교환은 패스스루 한번당 한번만 나타난다. 즉, N - 1 의 교환단계가 발생한다. N개의 원소 버블 정렬에서 최대 단계 수 선택 정렬에서 최대 단계 수 5 20 14(10 + 4) 10 90 54(45 + 9) 20 380 199(180 + 19) 40 1560 819(780 + 39) 80 6320 3239(3160 + 79) 선택정렬은..

정렬 알고리즘 중 기본인 버블 정렬의 사용법 1. 배열 내에서 연속된 두 항목을 가르킨다. 2 1 3 5 2. 두 항목의 순서가 바뀌었으면(왼쪽값이 오른쪽값보다 크면) 항목을 바꾼다 1 2 3 5 3. 포인터를 한칸 이동하여 반복한다. 1 2 3 5 1 ~3 을 반복하는 것을 패스스루 라고 한다. 패스스루가 끝나면 마지막 원소 즉, 5를 빼고 다시 패스스루를 반복한다. (총 행의 수 - 1 ) 의 패스스루를 반복한다. 위의 예시에선 3번의 패스스루가 일어난다. 위에 예시에선 결국 (N-1) + (N-2)...+ 1번의 비교를 수행한다. 위의 예시에선 3+2+1=6번의 비교가 일어난다. 여기에 더해 만약 모든 수가 역순일경우엔 총 6번의 교환이 더 일어나게 된다. 총 12단계의 작업이 일어난다. 원소 N개..

빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계 수만을 고려함으로써 일관성을 유지한다. 원소수에 따라 단계가 비례하며 증가한다면 O(N) 빅 오 엔 으로 표기한다. 이를 선형 시간 이라고도 부른다. 원소수가 어떻든 단계가 1이면 O(1)빅 오 일(상수 시간 이라고도 부른다), 단계가 4이면 O(4) 으로 표기한다. 이진 검색에선 O(log N)오 로그 앤으로 표기한다. 즉, 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 설명하는 방법이다. ex) O(log 4)란 사실 O(log 2^4) 라는 뜻이다. 결국 최종적으로 2로 2단계란 뜻이다. 가장 효율적인 순서론 O(1) > O(log N) > O(N) 이다. 원소개수(N) O(N) O(log N) 8 8 3 16 16 4 32 32 5..

정렬된 배열([1, 3, 5, 9, 15])은 삽입, 삭제가 일반 배열([3, 5, 1, 15, 9])보다 거쳐야 되는 단계수가 더 많다. 그러나 선형검색(인덱스0부터 차례차례)대신 이진검색(100의 중앙 50찾고 50중앙 25찾고 점점 찾고자하는 값에 절반을 날려 단계수가 대폭 줄어듬)을 사용할 수가 있다. 결론 : 만들고자하는 서비스에 사용될 알고리즘이 데이터 검색은 거의 없고, 데이터를 추가하기만 한다면 일반 배열이 더 나을 수 있으나, 검색 기능이 더 많은 서비스를 구현할때는 정렬된 배열이 훨씬 낫다.

1. 배열의 인덱스는 0부터 시작하며 인덱스 0의 메모리 주소는 1010이다. 2. 인덱스 3은 인덱스 0부터 정확히 세 슬롯 뒤에 있다. 3. 따라서 인덱스 3을 찾으려면 1010+3인 1013 메모리 주소로 간다.