알고리즘
-
[Algorithm] 알고리즘 - 문자열 매칭(Pattern Matching)Study/Algorithm 2020. 8. 27. 19:00
문자열 매칭 또는 패턴 매칭은 컴퓨터 과학에서 중요한 문제이다. 노트패드나 워드파일 또는 웹 브라우저 데이터베이스에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다. 문자열 매칭 방법의 종류는 아래와 같다. 1. Naive Matching (원시적인 매칭) - $O(mn)$ 2. Automata Algorithm (오토마타를 이용한 매칭) - $\Theta(n + |\sum| m)$ 3. Rabin-Karp Algorithm (라빈-카프 알고리즘) - $\Theta(n)$ 4. Knuth-Morris-Pratt(KMP) Algorithm (KMP알고리즘) - $\Theta(n)$ 5. Boyer-Moore Algorithm (보이어-무어 알고리즘) - $\Theta(n)$ Wor..
-
알고리즘 소개Study/Algorithm 2020. 5. 6. 12:24
알고리즘은 주어진 문제를 해결하기 위한 단계적 절차 또는 방법이다. 알고리즘은 명확하게 기술되어야 하고 유한한 시간 내에 모든 유효한 입력에 대해 올바른 해를 주어야 한다. 주어진 문제를 해결하는 여러 개의 알고리즘들 중 시간적으로 효율적인 알고리즘을 선택해야 한다. 문제를 알고리즘으로 해결하는 단계별 과정들은 다음과 같다. 1. 문제 이해: 주어진 문제를 완전히 이해해야 한다. 2. 알고리즘 설계: 주요 알고리즘 설계 기법을 참고하여 알고리즘을 설계햐야 한다. 3. 정확성 증명: 알고리즘이 정확하다는 것을 증명해야 한다. 4. 알고리즘 분석: 알고리즘의 시간(혹은 공간) 효율성을 분석해야 한다. 5. 알고리즘 구현: 알고리즘은 컴퓨터 프로그램으로 구현해야 한다. 알고리즘은 자연어나 의사 코드로 표현한다..
-
BOJ 2193번 파이썬Study/BOJ 2020. 1. 30. 17:30
블로그 두번째로 올리는 글인데... 부지런하게 새로운 걸 올리려 하는데... 게을러서 이번에도 알고리즘 하나 풀었습니다. 이친수의 갯수를 구하는 문젠데 N 자리의 이친수의 갯수를 순서대로 나열하면 1 10 100, 101 1010, 1000, 1001 10000, 10100, 10010, 10101, 10001 ... 위와 같은 식으로 가는데 여기서 10 [(100), 101] [(1010, 1000), 1001] [(10000, 10100, 10010), 10101, 10001] N-1에서 ()감싸진 0으로 끝나는 이친수가 N에선 1로 끝날 수 밖에 없겠죠? 왜냐하면 11과 같이 1이 연속되면 안되니까! N-1에서 [] 감싸진 전체의 이친수에 대해선 N에선 0이 붙어도 상관없습니다. 왜냐하면 0은 ....
-
BOJ 1149번 파이썬Study/BOJ 2020. 1. 29. 17:31
블로그 처음으로 글 올리는데 마땅히 쓰고 싶은 말이 없어서 문제하나 풀고 올립니다. 'ㅁ' for문을 돌며 RGB 각각의 비용을 min함수를 통해 작은 값을 계속 더해가는 방식으로 풀었습니다. def next_cost(r, g, b, nr, ng, nb): r += min(ng, nb) g += min(nr, nb) b += min(nr,ng) return r, g, b if __name__=="__main__": N = int(input()) nr = 0 ng = 0 nb = 0 for i in range(N): r, g, b = map(int, input().split(' ')) nr, ng, nb = next_cost(r, g, b, nr, ng, nb) print(min(nr, ng, nb))