본문 바로가기
반응형

분류 전체보기110

문자열 탐색 자료구조 - 트라이(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.
최소 비용 신장 트리 - 프림(Prim) 알고리즘 프림(Prim) 알고리즘 프림 알고리즘이란? - 최소 비용 신장 트리(MST)를 찾는 알고리즘 - 시작 정점에서 출발하여 신장 트리를 확장하는 알고리즘 - 시간 복잡도 : 인접 행렬 사용 시 O($V^2$) 우선 순위 큐, 인접리스트 사용 시 O(ElogV) - 간선의 숫자가 노드의 숫자보다 적은 경우 크루스칼을, 많은 경우 프림을 사용하면 좋다. 프림 알고리즘 실행 과정 - 1. 시작 정점을 선택한다. - 2. 해당 정점과 연결 된 정점 중 선택되지 않은 간선들을 우선순위 큐에 넣는다. - 3. 우선순위 큐에서 값이 제일 작은 간선을 뽑아 연결한다. - 4. 2~3번 과정을 반복한다. - 초기 상태(1을 시작 점을 설정) - 1과 연결된 간선 중 가장 작은 값인 2를 선택하고, 1과 2를 연결한다. -.. 2020. 11. 23.
반응형

티스토리툴바