따봉도치야 고마워

Trie 알고리즘이란? - retrieval의 약자로, 문자열 탐색에 특화된 자료구조 - 트리 자료 구조 중 하나로, Digital Tree/ Radix Tree/ Prefix Tree 라고도 불림 - 텍스트 자동완성 등에 쓰임 루트 노드는 특정 문자를 의미하지 않고 자식 노드만 가지고 있고, 각각 노드는 자식 노드와 단어의 마지막인지를 표시하는 변수를 가지고 있다. 특징 - 정렬된 트리 구조 - 자식 노드를 맵 형태로 가지고 있음 (Key-알파벳, Value-해당하는 자식) - 루트를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가진다 ex. R->E의 자식 D,O는 RE라는 공통 접두어를 가짐 Trie 알고리즘 구현 (Java) 1.먼저 TrieNode 를 만들어준다 class TrieNode{..

문제 하나의 막대기가 있다. 막대기 길이에 따라 가격이 다르다. 최고의 수익을 얻도록 막대기를 자르라. 입력 막대의 길이, 길이 별 가격 출력 최고 수익 풀이 - 길이가 4인 막대가 있다고 할 때 나올 수 있는 경우의 수는 아래와 같다 막대기를 1만큼 자른게 R1이라고 했을 때 최종 가격은 R1+R1+R1+R1 , R1+R3 , R2+R2 , R4 중 최적의 값이 된다. 여기서 R3은 R1+R2의 조합으로 볼 수 있고, R2도 마찬가지로 R1+R1의 조합으로 볼 수 있다 즉 각각의 길이에 맞는 최대값을 구해놓으면 최적의 값 계산이 가능하다. ex) R1은 더 자를 수 없으니 1이 최대 값이고 R2는 R1+R1의 조합인 2와 자르지 않은 가격인 5를 비교해 더 큰 값인 5 가 된다 R3은 R1+R2(1+5..

최적화 문제를 푸는 방법은 두 가지가 있다 1. 모든 상황을 고려해 최적의 방법을 찾는 것 -> 동적계획법 2. 그때 그때 가장 최선의 방법을 선택해 답을 구하는 방법 -> 탐욕법 동적계획법 (Dynamic Programming) - 전체 문제를 여러 개의 하위 문제로 나누고, 하위 문제들의 해결 방법을 결합해 최종 문제를 해결하는 방식 예제 1. 배낭문제 2. 막대기 자르기 . . 탐욕법 (탐욕 알고리즘, Greedy Algorithm) - 문제를 해결하는 과정에서 순간순간마다 최적이라고 생각하는 결정을 내려 진행해 최종 문제를 해결하는 방식 - 전체 문제해결의 최적의 답을 보장하진 않지만, 계산 속도가 빠르다는 장점이 있다. 위의 문제 (가장 큰 수 찾기)에서도 실제로 가장 큰 수는 99이지만, 그리..

문제 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다. 풀이1 1) 3중 for문으로 나올 수 있는 모든 경우의 합을 구해둔다. 2) 에라토스테네스 체 알고리즘으로 소수판별용 슬라이스를 만든다 3) 해당 슬라이스로 아까 구한 총합들의 소수 여부를 확인하고 answer ++ func solution(nums ..