Geeks For Geeks

🔒 문제 💭 생각의 흐름 중복을 허용하지 않기 때문에 같은 Key 값을 발견하면 바로 root를 리턴한다. 최종 삽입위치에 노드를 생성하고 부모가 자식을 가리키는 포인터를 지정해야 하므로 자식 노드로 내려갈 때마다 부모 노드를 킵해야한다. 🔑 풀이 Node* insert(Node* root, int Key) { Node* parent = root; Node* tempNode = root; while (tempNode != nullptr) { parent = tempNode; if (Key == tempNode->data) return root; else tempNode = (Key data) ? tempNode->left : tempNode->right; } if (parent->d..

What's Iterator? Container를 순회하는 포인터. When To Use? Convenient Programming loop without [] operator or minding 'range' Reusabililty we can reuse iterator when to change data container Dynamic add & remove (1) ⭐ 범위 신경쓰기 싫다. index 극혐이다. #include #include using namespace std; int main() { // Declaring a vector vector v = { 1, 2, 3 }; // Declaring an iterator vector::iterator i; int j; cout

🔒 문제 구분자가 .이 아니라 ' ' 공백이 여러개 들어왔을 경우에 뒤집는 풀이 🔑 풀이 (C++) #include #include using namespace std; string reverseWords(string S) { int endIndex = S.length(); string result = ""; while (endIndex > 0) { while (endIndex > 0 && S[endIndex--] == ' '); int startIndex = endIndex; while (startIndex > 0 && S[--startIndex] != ' '); if (startIndex != 0) { string word = S.substr(startIndex + 1, endIndex - start..

🔒 문제 💭 생각의 흐름 배열은 선형 자료구조로 전체 길이 / 2를 기준으로 좌우 대칭을 이루고있다. 맨 첫자리 끝자리 첫자리 + 1 끝자리 - 1 index를 사용하여 대칭을 이루는 문자열을 Swapping 해주기만 하면 된다. 🔑 풀이 (C++) string reverseWord(string str){ char characterArray[str.length() + 1]; const int length = sizeof(characterArray); strncpy(characterArray, str.c_str(), length); // after strncpy null-terminate character should not be created characterArray[length] = '\0'; for..

구현 방식 2가지 1. Priority Queue. // O(n log n) for(int i = 1; i O(n * log n) ∴ O (n * log n) BuildHeap Analysis When to use? k Largest(Smallest) elements in array Implementation (C++) // make Max Heap void PriorityQueue::shiftDown(int index) { int maxIndex = index; do { index = maxIndex; const int leftChildIndex = getLeftChildIndex(index); const int rightChildIndex = getRightChildIndex(index); if (l..

🔒 문제 💭 생각의 흐름 문제를 푸는 입장에서 유형을 보지 않을 수가 없는데 조건: 'directed graph' + can connect itself ∴ Union-Find 알고리즘을 사용하기 어렵다. 총 2가지 방식으로 풀이할 수 있겠다. Topological Sort using BFS (Kahn's Algorithm) 풀이 DFS 변형 풀이 여기선 2번 방법을 선택해서 풀이해보겠다. DFS 변형 풀이법의 핵심은 다음과 같다. 전형적인 DFS 코드를 쓰되, 부모 노드 Set(지나온 부모 노드 방문여부)을 Keep 한다! DFS 를 재귀적으로 호출하면서 이전 스택으로 되돌아 가기 직전에 방문처리 되지 않은 상태로 되돌리기 위해 (부모 노드 Set 업데이트) 부모 노드 방문을 취소한다. bool dfsD..