반응형 언어별 개념 정리/Python16 [파이썬] 스택(Stack) 알고리즘 정리 - 계산기 구현하기 stack으로 계산기 구현하기 why 계산기 구현? 중위 표기법 수식을 스택을 이용하여 후위 표기법으로 변경할 수 있음 계산기 입장에서 계산이 쉬워져 속도 ↑ 중위 표기법 연산자를 피연산자의 가운데에 표기하는 일반적인 방법 ex) A+B , 2+3*4, 인간에게 친숙한 표현법 후위 표기법 컴퓨터의 입장에서 중위 표기법보다 후위 표기법이 더 쉬움 연산자가 나오면 이전 숫자 2개와 연산을 하는 방식 ex) 2 3 4*+ → 2 12 + → 14의 과정으로 계산 A*B-C/D을 후위 표기법으로 변환 방법 ((A*B)-(C/D)) // 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현 ((AB)*(CD)/)- // 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동 AB*CD/- // 괄호 .. 2023. 2. 8. [파이썬] 문자열(String) 알고리즘 정리 - 보이어 무어(Boyer-moore) 알고리즘 보이어 무어(Boyer-moore) 알고리즘 참고 자료 링크 https://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf 정의 Boyer-Moore 알고리즘은 패턴의 마지막 문자부터 역순으로 검사를 진행하면서 비교하는 알고리즘 기존의 방법이 왼쪽에서 오른쪽으로 했다면, 보이어-무어 알고리즘은 오른쪽에서 왼쪽으로 비교 (단, 이동(skip) 할 때는 왼쪽에서 오른쪽) 대표적으로 Bad Character Rule과 Good shuffix Rule BAD Character Rule 방법 Step1 문자열과 패턴을 오른쪽에서 왼쪽으로 문자가 일치하는지 확인 문자열과 패턴의 문자가 b 부분에서 다른 것을 확인 (C / T) 이때의 Bad char.. 2023. 2. 7. [파이썬] 문자열(String) 알고리즘 정리 - 브루트 포스(brute force) 정의 무식하게 진행 한다는 의미로 brute force 알고리즘이라 불리며 가능한 모든 경우의 수를 모두 탐색하기에 완전 탐색 알고리즘이라고도 불린다. 일반적으로 문제 해결을 위해서 모든 자료를 탐색해야 하기에 특정 구조를 전체적으로 탐색할 수 있는 방법 요구 선형 구조로 탐색하는 순차 탐색, 비선형 구조로 탐색하는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 가장 기본적인 방법 → 브루트 포스와 가장 관련이 깊은 방법은 BFS 비밀번호 자물쇠를 생각하면 이해하기 쉽다 (단순히 무식하게 4자리 자물쇠를 확인하더라도 총 10^4번의 확인이 필요하다) 장점 알고리즘 설계와 구현이 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현이 가능하다 단점 알고리즘의 실행 시간이 매우 오래 걸린다 메모리 효율면에서.. 2023. 2. 6. [파이썬] 알고리즘 풀이에 자주 사용되는 python 함수 및 알고리즘 기술 정리하기 알고리즘 문제를 풀면서 여러가지 내장 함수를 사용하게 된다. 그 중 이런 함수가 있는건 알지만 어떻게 적용되는지, 어떻게 사용해야하는지 정확하게 개념을 잡고자 하나씩 정리하고자 한다. 특히 함수들의 사용 원리를 파악하기 위해서 싸피 알고리즘 주간에는 과제로 내어준 문제들에 대해 max, min, sum, sort 등의 내장 함수를 사용하지 말라고 한다. (물론 개인 공부때는 별개) 알고리즘을 풀면서 (특히 백준) 시간 초과, 메모리 초과, 런타임 에러 등 많은 고려 사항들이 발목을 잡고 있는데, 시간 복잡도 생각하는 방식 등을 제대로 아직은 이해하지 못하고 있어서 그런거 같다. 지금 가장 많이 사용하는 함수 1) input() 함수 → 백준 풀 때는 sys 모듈 import 해서 sys.stdin.rea.. 2023. 2. 5. 이전 1 2 3 다음 반응형
