반응형 알고리즘/알고리즘 이론23 투 포인터, 슬라이딩 윈도우 기법 투 포인터(Two Pointers method) 투 포인터란? - 배열을 따라 두 개의 포인터를 이동시키면서 데이터를 처리하는 알고리즘 - 포인터 두 개는 모두 한쪽 방향으로 움직인다. - 투 포인터를 이용한 경우 값이 모두 양수이여야 한다. 투 포인터 예시(부분합이 27인 구간 구하기) - SUM = 1 27 이기 때문에 LEFT를 왼쪽으로 한 칸 이동 - SUM = 32 > 27 이기 때문에 LEF.. 2020. 11. 29. 문자열 탐색 자료구조 - 트라이(Trie) 트라이(Trie) 트라이란? - 문자열의 집합을 관리하는 자료구조. - 문자열을 빠르게 탐색할 수 있게 도와주는 자료구조. - 탐색하려는 문자를 O(n)의 시간복잡도로 구할 수 있다.(n은 문자열의 길이) - 트라이는 시간 복잡도 측면에서 강점을 가지지만, 공간 복잡도 측면에서는 단점을 가진다. 트라이 작동 방법 - 1. 탐색하려는 문자열의 문자들을 순차적으로 접근한다. - 2. 해당 문자들이 노드에 있는 지 확인한다. - 3. 해당 문자들이 노드에 존재하지 않는다면, 새로 추가한다. - 4. 문자의 마지막에 해당하는 노드에는 마지막이라는 표시를 해준다. - 트라이 자료구조에서 cake 라는 단어를 탐색. - root노드와 연결된 노드 중 cake의 첫 번째 문자인 c가 있는지 탐색 후 방문 - c노드와.. 2020. 11. 29. 소수 판별 - 에라토스테네스의 체 소수 판별 - 에라토스테네스의 체 에라토스테네스의 체 란? - 소수 : 약수가 1과 자기 자신만 있는 1보다 큰 수. - 에라토스테네스의 체 : 고대 수학자 에라토스테네스가 발견한 소수 판별 방법. 에라토스테네스의 체 예시 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴.. 2020. 11. 24. 다이나믹 프로그래밍(Dynamic Programming, DP) 다이나믹 프로그래밍(Dynamic Programming, DP) 다이나믹 프로그래밍이란? - 큰 단위의 문제를 작은 단위로 나누고, 작은 단위 문제부터 처리한다. 큰 단위의 문제를 해결하기 위하여 기존에 처리했던 작은 단위의 문제를 이용한다. - 작은 단위의 문제를 풀다보면 반복적인 작업이 많이 발생하는데, 이를 해결하기 위하여 메모이제이션이라는 기법을 이용한다. - 메모이제이션 : 기존에 처리했던 문제를 저장한 후, 같은 문제를 처리해야 할 때 다시 문제를 처리하는 것이 아니라 기존에 저장된 값을 사용하는 것. 다이나믹 프로그래밍 방법 1. 문제를 완전 탐색으로 풀어야하는데 경우의 수가 너무 많아서 시간내에 불가능하다. 2. 문제의 상태를 살펴보고, 공통적인 부분을 도출하여 묶어준다. 3. 메모이제이션.. 2020. 11. 24. 이전 1 2 3 4 5 6 다음 반응형
