jundyu 님의 블로그

들어가며우리가 일상적으로 사용하는 수식은 대부분 중위 표기법(Infix Notation)입니다. 그러나 수식을 표현하는 방법에는 전위 표기법(Prefix Notation), 후위 표기법(Postfix Notation)도 존재합니다. 이번 글에서는 각각의 표기법에 대해 간단히 알아본 뒤 후위 표기법을 왜 사용해야하는 지와 중위 표기법을 후위 표기법으로 어떻게 변환하는 지에 대해 다뤄보겠습니다. 글의 마지막에 표기법끼리 변환하는 방법도 있으니 참고해주세요. 수식 표기법우선 수식 표기법에 대해 간단히 알아보고 지나가겠습니다. 수식 표기법은 총 3가지로 분류됩니다.전위 표기법 : Prefix Notaion(PN = Polish Notation)중위 표기법 : Infix Notaion후위 표기법 : Postfi..

들어가며문자열 관련 알고리즘에는 일반적으로 검색이나 비교&정렬과 관련된 것이 많습니다. 대표적으로 KMP, Boyer-Moore, Rabin-Karp 등이 있습니다. 이번에 소개할 알고리즘은 패턴 매칭의 Z 알고리즘인데 문자열을 검색하기 좋은 알고리즘입니다. 이번 글에선 간간히 KMP 알고리즘도 언급되므로 원활한 이해를 위해선 아래의 KMP 알고리즘도 읽어보시는 것을 추천합니다. [Algorithm] KMP 알고리즘 with JAVA들어가며긴 글에서 주어진 패턴의 문자열을 검색할 때 가장 구현이 쉬운 방식은 text와 pattern이 주어졌을 때 인덱스를 각각 비교하는 방식(=브루트 포스)입니다. 길이 N인 text를 길이 M만큼의 patterjundyu.tistory.com  Z - AlgorithmZ..

들어가며긴 글에서 주어진 패턴의 문자열을 검색할 때 가장 구현이 쉬운 방식은 text와 pattern이 주어졌을 때 인덱스를 각각 비교하는 방식(=브루트 포스)입니다. 길이 N인 text를 길이 M만큼의 pattern과 비교하기 때문에 시간 복잡도는 O(N*M) 입니다. 이런 방식은 text의 길이가 10만이고 pattern의 길이가 1000인 경우 시간 복잡도는 1억으로 급격히 커지는 것을 알 수 있습니다. 이런 시간복잡도 문제를 해결하기 위해 만들어진 알고리즘은 대표적으로 KMP와 Rabin-Karp가 있습니다. KMP는 단지 비교 횟수를 줄임으로써 시간복잡도 문제를 개선했고, Rabin-Karp는 해시를 이용해서 일치하는 pattern을 찾는 일종의 Rolling-Hash 방식입니다. 이번 글에서는..