Algorithm/Algorithm (문제풀이)

🔒 문제 🧠 아이디어 그래프상 간선과 정점이 주어지고 시작점 - 목적지 - 간선비용을 입력받는 전형적인 최소 비용 경로 문제. 단 경로 과정을 모두 킵해야 하므로 다익스트라 알고리즘 상에서 특정 지점에 도착하기 직전 지점을 배열에 담아 보관하고 시작점에 도달하기 까지 목적지로부터 거꾸로 출력해내기만 하면 되겠다. 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader import java.lang.StringBuilder import java.util.* import kotlin.collections.ArrayList fun dijkstra(startVertexNum: Int, distances: Array, preVert..

🔒 Problem 🔑 BFS approach Create two queue with bread-first search to all nodes. To handle null case, if null, don't add left & right nodes to queue BFS Code (Kotlin) import java.util.LinkedList import java.util.Queue class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null } class SameTree { fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean { // 1. queue 2개 초기화 및..

🔒 문제 💭 생각의 흐름 라이브러리에서 CircularQueue 를 제공하거나 이미 구현해놓은 코드가 있다면 CircularQueue 안에서 iterator를 쓰면 좋겠다고 생각은 했지만 java, kotlin 에서 CircularQueue를 제공하지 않으므로 그냥 사이즈의 최대 크기를 넘어가는 시점에는 mod(%) 연산으로 index를 조정하는 방식을 택했다. 출력 결과에 '

🔒 문제 💭 생각의 흐름 중복을 허용하지 않기 때문에 같은 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..

🔒 문제 🧠 생각의 흐름 입력값에 "위치가 같은 두 점은 없다" 라는 부분에서 중복 값 저장은 신경쓸 필요가 없다는 것을 알 수 있다. 총 2가지로 풀이할 수 있다. (1) 일단 모든 숫자를 리스트나 배열에 담고 정렬하자 y 기준 정렬 -> x 기준 정렬 (stable) (2) SortedSet을 사용하자 ✔️ => 애초에 담길 때 부터 우선순위에 의해 자동 정렬이 되는 자료구조로 정렬의 우선순위인 'comparator' 만 정의해주면 된다. 🔑 풀이 import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util..

🔒 문제 🔑 풀이 (C++) #include #include #include #define MIN_VALUE 0 #define MAX_VALUE 255 using namespace std; bool has_only_digits(const string s){ // dot(.) == "\000" return s.find_first_not_of( "0123456789" ) == string::npos && (s != "\000"); } /* The function returns 1 if IP string is valid else return 0 You are required to complete this method */ int isValid(string s) { if (count(s.begin(), s.en..