본문 바로가기
반응형

알고리즘91

[BOJ-5052] 전화번호 목록 (C++) 백준 5052 - 전화번호 목록 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 문제 설명 - 전화번호 목록이 주어지고, 이 전화번호 목록이 일관성을 유지하는지 판단하라. - 일관성을 유지한다면 YES, 유지하지 않는 다면 NO를 출력한다. - 일관성을 유지한다는 것은, 한 전화번호가 다른 전화번호의 접두이인 경우가 없다는 것이다. (911과 91125426이 있다면, 911은 91125426의 접두어이기 때문에 일관성이 없다.) 입력 값 - 테스트 케이스 개수 : t (1 t; for.. 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.
반응형

티스토리툴바