Algorithm/Algorithm (문제풀이)

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..

🔒 문제 💭 생각의 흐름 MST (Minimum Spanning Tree) + Undirected Graph => 2가지 방법! Kruskcal Prim✔️ mstSet: 방문된 MST 원소의 집합 not visited Set: 아직 방문하지 않은 노드 번호 - 비용 집합 find minimum cut vertex : mstSet과 not visited Set을 최소 비용으로 연결하는 노드 찾기 mstSet -> 어차피 weight의 총합을 구하는 것이므로 방문 순서를 저장할 필요가 없겠다 -> unorderd_set not visited Set -> 배열로 생성시 따로 visited Boolean 배열이 필요하므로 map 자료구조 사용 ⭐ find minimum cut vertex -> not vist..

🔒 문제 💭 생각의 흐름 문제를 푸는 입장에서 유형을 보지 않을 수가 없는데 조건: '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..

이론 정리한지 1년이 넘어서 풀어보는 예제 🔒 문제 위상 정렬 순서에 맞는 answer vector를 리턴하라. 🔑 풀이 class Solution{ public: vector topoSort(int V, vector adj[]) { int * indegree = new int[V]{0}; std::vector answer; // initialize indegree array for (int i = 0; i < V; i++) { for (const auto& adjacentVertex : adj[i]) { indegree[adjacentVertex]++; } } std::queue queue; // indegree 0 찾고 넣기 for (int i = 0; i < V; i++) { if(indegree[..