개인적으로 공부한 내용을 정리중입니다.

4358번 생태학 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; map m; //종의 갯수를 빠르게 세기위한 트라이 struct Trie { bool finish; int cnt = 0; Trie* next[200]; Trie() : finish(false) { memset(next, 0, sizeof next); } ~Trie() { for (int i = 0; i < 200; i++) { if (next[i]) delete next[i]; } } void insert(const char* key) { if (*key == '\0') { fin..

백준 9934번 음 알고리즘 분류가 트라이라서 트라이 문제일 줄 알았는데 그냥 완전 이진 트리 같다. 음 근데 문제는 전위 순회 결과에서 트리를 재구성하라는거 같다. 반대는 몇번 해봤는데 ;; 일단 K에 따라서 트리의 깊이는 미리 알 수 있는데 10으로 깊지 않다. 음 내 생각에 풀이는 임의로 트리를 만들고 순서대로 순회 하면서 도착 지점에 도달하면 주어진 인풋의 맨 앞부터 순서대로 해당 트리 노드에 넣어주면 될거 같다.... 구현했는데 예제는 맞는데 틀렸다 함....음 ㅋㅋ 음 완전 이진트리라는 조건에 뭔가 안맞게 설계한거 같다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std;..

이 문제를 스택으로 해결했었다. 그런데 음 스택으로도 다시 풀어보고, 분할 정복으로도 풀 수 있던데 두가지로 풀어보겠다. 이전에 스택했으니 일단 분할정복으로 하자. 보통 분할 정복은 절반씩 분할하는거 같다. 계속 분할해서 한개가 되고 두개로 합칠때 음? 어떻게 생각해야되는 걸까.... 음 분할해서 해당 영역의 가장 큰 넓이를 찾으면 된다고 생각한다. 그리고 이제 두개를 합치면 되는거 같은데, 그렇다면 합칠때 양쪽 중에 더 작은 높이 * 양쪽 갯수 랑 두개 영역을 비교해서 가장 큰 넓이를 선택하게 한다. 이때 합병하면서 저장해야 되는 값은 가장 작은 높이, 합친 넓이이다. 가장 작은 높이랑 갯수를 알면 왼쪽 오른쪽을 합칠때 합쳐질 넓이를 알 수 있다. 재귀함수를 사용할텐데 매개 변수로 시작,끝 인덱스를 넘..