https://coding-food-court.tistory.com/216 위 글에 있는 내용과 그림을 참고하였습니다. 다만, 코드에 오류가 있어서 수정하였습니다. 길이가 M인 전체 문자열에서 길이가 N인 문자열을 찾는다고 하면 시간 복잡도 O(M*N)인 알고리즘이다. 이렇게도 풀수는 있지만 시간 복잡도가 상당하다. 라빈-카프 문자열 탐색 알고리즘을 사용하면 시간 복잡도가 O(N)으로 감소한다. 라빈-카프의 원리 찾는 패턴의 길이만큼을 전체 문자열과 찾는 문자열의 해시 코드로 비교한다. 만약 전체 문자열과 찾는 문자열의 해시 코드가 일치한다면 하나씩 비교해가면서 정말로 맞는지 확인한다. 이렇게 한 번더 비교하는 이유는 해시 충돌때문이다. 해시 충돌 A = 0, B = 1, C = 2라고 하고 해시함수가 ..

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다. 다양한 빅오 카테고리 단어 생성기 이 예제는 문자 배열로부터 두 글자짜리 모든 문자열 조합을 모으는 알고리즘이다. 예를 들어, [a,b,c,d]라는 배열이 주어지면 다음과 같은 문자열 조합을 포함하는 새 배열을 리턴한다. 아래는 이 알고리즘을 자바스크립트로 구현한 코드이다. 이 알고리즘의 효율성은 바깥 루프는 N개 원소를 모두 순회하고 각 원소마다 안쪽 루프는 다시 N개 원소를 모두 순회하니 O(N²)이다. 세 글자짜리 모든 문자열 조합을 계산하도록 알고리즘을 수정하면 함수는 아래와 같은 배열을 반환할 것이다. function wordBuilder(array) { let collection = [..

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다. 삽입 정렬 삽입 정렬의 수행 순서는 아래와 같다. 1. 첫 번째 패스스루에서 임시로 인덱스 1(두 번째 셀)의 값을 삭제하고 이 값을 임시 변수에 저장한다. 인덱스 1에 값이 없으므로 공백이 생긴다. 이후 각 패스스루마다 다음 인덱스의 값을 삭제한다. 2. 다음으로 공백 왼쪽에 있는 각 값을 가져와 임시 변수에 있는 값과 비교하는 시프트 단계를 시작한다. 공백 왼쪽에 있는 값이 임시 변수에 있는 값보다 크면 그 값을 오른쪽으로 시프트한다. 값을 오른쪽으로 시프트했으므로 자연히 공백이 왼쪽으로 옮겨진다. 임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달해야 시프트 단계가 끝난다. 3...

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다. 선택 정렬 선택 정렬은 아래와 같은 단계를 따른다. 1. 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정한다. 한 셀씩 이동하면서 현재까지 가장 작은 값을 기록한다.(실제로는 그 인덱스를 변수에 저장) 변수에 들어 있는 값보다 작은 값이 들어 있는 셀을 만나면 변수가 새 인덱스를 가리키도록 값을 대체한다. 2. 최솟값이 어느 인덱스에 있는지 알았으므로 그 인덱스의 값과 패스스루를 처음 시작했을 때의 값을 교환한다. 패스스루를 시작했을 때 인덱스는 첫 패스스루에서는 인덱스 0일 것이고, 두 번째 패스스루에서는 인덱스 1일 것이다. 3. 매 패스스루는 1, 2 단계로 이..

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다. 버블 정렬 버블 정렬은 단순 정렬(simple sort)이라 알려졌다. 이해하기 쉬워서 이렇게 불리지만, 더 빠르다고 알려진 정렬 알고리즘보다 비효율적이다. 버블 정렬은 아래와 같은 단계를 따른다. 1. 배열 내에서 연속된 두 항목을 가리킨다. 즉, 첫 번째 항목과 두번째 항목을 비교한다. 2. 두 항목의 순서가 뒤바뀌어있으면, 두 항목을 교환한다. (순서가 올바르다면 2단계에선 아무것도 하지 않는다.) 3. 포인터를 오른쪽으로 한 셀씩 옮긴다. 4. 배열의 끝까지 또는 이미 정렬된 값까지 1단계부터 3단계를 반복한다. 이제 배열의 첫 패스스루(pass-through)가 끝났다. 즉, 배열 끝까지..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 8퀸 문제란? 서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓는 것 퀸은 현재 놓여있는 지점에서 가로 or 세로 or 대각선의 8가지 방향으로 직선 이동 가능하다. 체스판의 가로줄을 행, 세로줄을 열이라 하고 배열 인덱스에 맞추어 행과 열에 0~7의 번호를 부여한다. 이 문제의 답이 되는 조합은 92가지이다. 아래의 그림은 92가지중 하나의 조합을 나타낸 것이다. 퀸 배치하기 8개의 퀸을 체스판 64칸(8*8)이므로 처음에 64칸중 아무칸에 놓고, 다음 퀸을 배치할 때는 나머지 63칸에서 임의로 선택한다. 64 x 63 x 62 x 61 x 60 x 59 x 58 x 57 = 178,462,987,637,..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. public class Main { static void recur(int n) { if(n > 0) { recur(n - 1); System.out.println(n); recur(n-2); } } public static void main(String[] args) throws Exception { recur(4); } } /* 1 2 3 1 4 1 2 */ 위 recur 메소드는 실행 과정에서 같은 계산을 여러번 반복하여 수행한다. 위 에서 보는 것과 같이 recur(4)를 호출하면 recur(1)을 3회 실행한다. n 값이 커지면 반복하는 계산 횟수는 더욱 늘어난다. recur(3)은 1, 2, 3, 1을 차례로..

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다. 빅 오 단순히 어떤 알고리즘을 22단계 알고리즘, 400단계 알고리즘이라고 표시할 수 없다. 알고리즘에 필요한 단계 수를 하나의 수로 못 박을 수 없기 때문이다. 예를 들어 선형 검색에는 배열의 원소 수만큼의 단계가 필요하므로 배열에 따라 필요한 단계 수가 다르다. 선형 검색의 효율성을 정량화하는 보다 효과적인 방법은 배열에 N개의 원소가 있을 때 선형 검색에 N단계가 필요하다고 표현한다. 빅 오 표기법을 사용해 주어진 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다. 선형 검색 알고리즘을 빅 오로 나타내면 O(N)이다. O(N)은 알고리즘에 N단계가 필요하다는 뜻이다. 원소가 N개인 배열의 ..