👋 들어가기 전 알고리즘 관련 글을 쓰는건 진짜 오랜만인 것 같다.. 아마 마지막이 퀵 정렬과 관련된 포스팅인 것 같은데 https://hamp.tistory.com/95 .. 2달이 되어간다. 이번 시간에는 자주 헷갈리는 개념인 분할 정복과 동적 계회법의 차이점을 알아보자.🚧 공통점과 차이점공통점두 접근법 모두 문제를 작게 쪼개는 작은 단위에서 해결하려는 접근법이다.차이점동적 계획법은 부분 문제를 풀기 때문에 문제가 중복될 수 있다. 그렇기 때문에 메모제이션 기법을 사용한다. 반대로 분할 정복은 중복되는 문제가 없어 메모제이션 기법을 사용하지 않는다.📄 동적계획법문제를 잘개 쪼개 입력이 작을 때 문제를 먼저 해결한 후, 다음 연산에 사용하는 기법더 큰 연산에 이전 문제들을 사용하기 위해서는 이전 ..

퀵 정렬 개념정해진 pivot을 기준으로 pivot보다 작은 것은 왼쪽 piviot보다 큰 거는 오른쪽으로 배치한다. 퀵 정렬은 크게 2가지 과정으로 이루워진다. partition을 통해 pivot을 기준으로 정렬한다. 재귀적 반복을 통해 잘게 분할한다. 여기서 분할하는 기준은 pivot의 정렬된 이후 위치이다.전체 적인 과정은 아래에서 살펴보자.과정 pviot을 고르 때 가장 오른쪽에 있는 값을 고른다.우리는 두가지 포인터를 사용한다.i = 바뀜을 당할 위치 포인터 , i는 low부터 시작한다. [ 왼쪽 끝에서 시작 ]j = arr를 순회할 포인터 pivot가 비교될  값들  arr[j] pivot 이하라는 것은 왼쪽에 위치해야하므로, i를 증가 즉, 바뀔 공간을 확보한다.이후 j와 i 값을 바꿈 , ..

KMP 알고리즘 정의KMP(커누스 모리스 프랫 3명의 사람이 같이 만들어서 KMP)알고리즘이며 불필요한 비교 즉, 어차피 틀릴걸 아는 부분은 건너뛰어버리는 원리를 이용하는 대표적인 문자열 매칭 알고리즘이다. 문자열 매칭이란 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾아내는 것을 의미한다. 쉽게 말하면 우리가 브라우저에서 ctrl+f를 통해 찾고자하는 문자열을 검색하는 행위라고 생각하면 된다. 과정1. 패턴 내 접두사 , 접미사를 활용하자.kmp 알고리즘의 핵심은 패턴의 접두사와 접미사 개념을 적극 활용하여 '반복되는 연산을 얼만큼 건너뛸 수 있는 지'에 대해 집중한다는 것이다. 패턴 내에 존재하는 접두사와 접미사가 '일치' 한다면 접미사를 접두사로 다시 바라봄으로써 문자열 탐색을 이어서 진행할..