유제필의 개발 블로그

요약 시간 복잡도 : 최상 O(mn) 문자열에서 특정 패턴을 미리 찾아내 검색하는 문자열 검색 알고리즘 문자열 검색 시 검사했던 위치 결과를 버러지 않아 효율적으로 검색할 수 있음 문자열 검색 시 불필요한 문자간 비교를 없애기 위해 실패 함수를 사용함 Boyer-Moore 법과 성능이 같거나 좋지 않아 실제로 많이 사용되지 않는 알고리즘 KMP(Knuth-Morris-Pratt Algorithm) 알고리즘이란 KMP 알고리즘이란 문자열 중에서 특정 패턴을 찾아내는 문자열 검색 알고리즘 중 하나이다. 문자열 검색 시 검사했던 위치 결과를 버리지 않고 효율적으로 검색할 수 있는 특징이 있다. 문자열 검색 시 불필요한 문자간 비교를 없애기 위해서 실패 함수를 사용한다. 문자열 검색 방법 아래 예제는 "ZABC..

요약 시간 복잡도 : 최상 O(n) 최악 O(mn) 브루트 포스 알고리즘이란 완전탐색 알고리즘으로 문제에 나와있는 모든 경우의 수를 시험하는 방법 찾고 싶은 문자열이 있을 때 각각의 문자 하나하나 대조하며 찾아내는 방법 검색할 문자열의 커서와 찾을 문자열의 커서를 두고 한 문자씩 비교 구조가 간단하여 구현 및 이해가 쉽지만 비효율적 알고리즘 브루트-포스법(Brute force) 알고리즘 브루트 포스 알고리즘이란 완전탐색 알고리즘으로 문제에 나와있는 모든 경우의 수를 시험하는 방법이다. 문자열을 검색하는 가장 기초적인 알고리즘으로 꼽히며 찾고 싶은 문자열이 있을 때 하나하나 대조하며 찾아낸다. 브루트 포스 알고리즘은 구조가 간단하여 구현 및 이해가 쉽지만 비효율적 알고리즘이다. 아래 예제는 문자열 "ABA..

요약 시간 복잡도 : O(n log n) ~ O(n ^ 2) 정렬할 데이터에서 피벗을 기준으로 두 개의 비균등한 크기로 분할하는 작업을 반복 피벗 이하의 그룹과 이상의 그룹이 왼쪽, 오른쪽으로 분리되었을 경우 배열을 다시 분할 요소가 1개가 되었을 때 분할을 멈춤 퀵 정렬(Quick Sort) 퀵 정렬이란 정렬할 데이터에서 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬하는 알고리증믈 말한다. 퀵 정렬은 가장 빠른 정렬 알고리즘으로, 찰스 앤터니 리처드 호어(C. A. R. Hoare)가 붙인 이름으로, 속도가 빠른 만큼 많이 사용되는 정렬 알고리즘이다. 만약 어떤 학생 그룹이 있고, 수가 8명이며 키 순서대로 정렬해야 되는 구조가 있다. 먼저 임의의 학생 A를 ..

요약 시간 복잡도 : O(log N) 데이터의 중간 값을 확인해 검색 범위를 반씩 좁혀가는 검색하는 검색 알고리즘 오름차순 또는 내림차순으로 정렬된 데이터 구조에서만 사용할 수 있음 검색이 반복될 때마다 검색 범위가 반으로 좁혀지므로 검색 속도가 빠름 검색 범위를 맨 앞, 맨 끝, 중앙 요소로 두고 중앙 요소의 값으로 학인함 이진 탐색(Binary Search) 이진 탐색이란 데이터가 오름차순 또는 내림차순으로 정렬되어 있을 때 검색하는 정렬 알고리즘이다. 이진 탐색은 정렬되지 않은 데이터에서는 사용할 수 없으나, 선형 검색보다 빠르게 검색할 수 있는 장점이 있다. 데이터의 중간 값을 확인해 검색 범위를 반씩 좁혀가며 검색하는 구조를 가지고 있다. 먼저 정렬된 배열이 있다고 가정한다. [5, 7, 15,..

요약 시간 복잡도 : O(n) 검색 방법 중 가장 단순하여 구현이 쉽움 정렬되지 않은 데이터 구조에서도 사용 가능 길이가 길수록 비효율(모든 데이터 검색 필요) 선형 검색(Linear Search)이란 선형 검색이란 데이터가 모인 집합(배열, 링크드 리스트 등)에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 검색하여 찾는 검색 알고리즘을 말한다. 다른 말로 순차 검색(Sequential Search)라고도 한다. 검색하고자 하는 데이터 집합이 있다고 가정한다. 이 배열에서 2라는 값을 찾기 위해 0번 인덱스 요소부터 차례로 검색한다. 위 배열에서는 2라는 값을 찾기 위해 4번의 검색으로 발견하였다. 첫 번째 인덱스 값 6 확인, 원하는 값이 아님 두 번째 인덱스 값 4 확인, 원하는 값..

요약 시간 복잡도 : O(n^2) 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하는 정렬 알고리즘 정렬되지 않은 데이터가 있을 때 정렬되지 않은 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입 정렬이 많이 이루어진 경우 효율적으로 사용 가능 정렬에 안정적이고 단순해서 구현이 쉬우나 시간 복잡도가 비효율적임 삽입 정렬(Insertion Srot)이란 삽입 정렬이란 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하는 정렬 알고리즘이다. 정렬되지 않은 데이터가 있을 때 정렬되지 않은 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입하는 개념이다. 위와 같은 정렬되지 않은 배열이 있다고 가정한다. 삽입 정렬은 2번째 요소부터 선택하여 진행한다. 이때 4는 6보다 앞쪽에..

선택 정렬(Selection Sort) 요약 시간 복잡도 : O(n ^ 2) 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 정렬 알고리즘 배열의 가장 작은 값을 찾아 맨 처음 요소와 위치를 변경하는 작업을 반복하여 정렬을 수행 같은 값이 있을 경우 상대적인 위치가 변경될 수 있어 안전하지 않음 배열의 크기를 알고 있기 때문에 이동 횟수를 미리 알 수 있다는 장점이 있음 단순 선택 정렬이란 단순 선택 정렬이란 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 정렬 알고리즘이다. 어떤 배열이 있을 때, 배열의 가장 작은 값을 찾아 맨 처음 요소와 위치를 변경하는 작업을 반복하여 정렬을 수행한다. 배열에서 가장 작은 값 1을 찾아 0번째 인덱스 6과 위치를 교환한다. 1번째..

버블 정렬(Bubble Sort) 요약 시간 복잡도 : O(n) = n ^ 2 인접한 두 요소의 대소 관계를 비교하여 반복 교환 시간 복잡도가 느리지만, 코드가 단순하여 구현이 쉬워 자주 사용 요소의 개수가 n개인 배열에서 n - 1회 비교, 교환을 하고 나면 가장 작은 요소가 맨 처음 또는 끝으로 이동 비교, 교환 과정을 패스라고 함 버블 정렬이란 인접한 두 요소의 대소 관계를 비교하여 교환을 반복하는 것을 말한다. 시간 복잡도가 상당히 느리지만, 코드가 단순하여 구현이 쉽기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 이라는 이름이 붙었다. 버블 정렬은 정렬을 앞에서 시작할 수도 있고, 뒤부터 시작할 수도 있지만, 요소의 끝부터 확인하고 정렬해야 한다..

하노이의 탑(Towers Of Hanoi) 요약 큰 원반이 아래에서 차례로 위치할 수 있고, 최소한의 횟수로 마지막 기둥으로 원반을 옮기는 문제 가장 큰 원반을 제외하고 나머지 원반을 그룹으로 묶어 문제 해결에 접근 그룹은 원반 개수의 N - 1 하노이의 탑(Towers Of Hanoi)이란 하뇌의 탑은 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제이다. 모든 원반는 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여 있다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소한의 횟수로 옮기는 문제이며, 원반은 1개씩만, 큰 원반을 작은 원반위에 쌓을 수 없다. 문제를 해결하기 위해 가장 큰 원반을 제외하고, 나머지 원반을 그룹으로 묶어..

재귀(Recursive)란 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적 이라고 한다. 쉽게 말해서 자기 자신을 포함한 것이라고 쉽게 생각할 수 있다. 프로그래밍에서 재귀란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법을 말한다. 재귀를 효과적으로 사용하면 프로그램을 간결하게 작성할 수 있다. 재귀적 정의에 의해 무한으로 존재하는 자연수를 아래의 두 조건으로 정의할 수 있다. 1은 자연수이다. 자연수 n의 바로 다음 수도 자연수이다. 팩토리얼(Factorial) 팩토리얼이란 한글로 계승 또는 순차곱셈이라고 하며, 1에서 시작하여 어떤 범위에 있는 모든 정수를 곱하는 것을 의미한다. 팩토리얼 예제는 재귀함수의 예제로 많이 사용한다. ..