합니다, 개발공부📝 합니다, 개발공부📝

Lv.1 가장 많이 받은 선물 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/258712?language=kotlin 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 구현에 가까운 문제다. class Solution { fun solution(friends: Array, gifts: Array): Int { var answer: Int = 0 val n = friends.size var nameToIndex = friends.withIndex().associate { it.value to it.index..

1. Zero Array Transformation I문제 : https://leetcode.com/problems/zero-array-transformation-i 쿼리를 돌면서 배열에서 바로 -1 처리를 하면 시간복잡도가 O(Q*N)이 되어 Time Limit Exceeded 예외가 발생하게 된다.이를 효율적으로 처리하기 위해 차이 배열(difference array) 또는 누적 배열 prefix sum 기법을 활용해야한다. https://sheep1sik.tistory.com/161 [ Algorithm ] 차분 배열 ( Difference Array ) 기법프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers...

1. Find Median from Data Stream 문제 : https://leetcode.com/problems/find-median-from-data-stream 숫자가 더해지는 연산과 더해진 리스트이 중간값을 찾는 문제이다. 리스트가 짝수인 경우에는 중간의 2자리를 더하고 결과를 Double로 반환한다. 이 문제는 단순 리스트로 문제를 풀려고하면 Time Limit Exceeded 예외가 발생한다 .우선순위 큐를 이용해서 간단하게 중간값을 구할 수 있다. 최소 우선순위 큐인 minHeap과 최대 우선순위 큐인 maxHeap을 사용하고 이 둘의 길이를 항상 반으로 유지하도록 해서 리스트를 반으로 쪼개 구성하는 방식이다. 값을 더하는 addNum()의 경우 시간복잡도는 O(logN) 공간복잡..

이진 트리 1. maximum-depth-of-binary-tree문제 : https://leetcode.com/problems/maximum-depth-of-binary-tree/ 트리의 깊이를 찾는 문제다. 먼저 DFS 방식으로 풀 수 있다. n : 노드의 갯수, h : 트리의 최대 깊이 시간 복잡도 : O(n) -> 모든 노드를 한번씩 방문 공강 복잡도 : O(h) -> 재귀 콜 스택에 최대 h개의 노드 fun maxDepth(root: TreeNode?): Int { if(root == null) return 0 var left = maxDepth(root.left) var right = maxDepth(root.right) return ..

문자열 찾기 1) longest-substring-without-repeating-characters문제 : https://leetcode.com/problems/longest-substring-without-repeating-characters/ 1. 슬라이딩 윈도우 반복되지 않는 가장 긴 문자열의 길이를 반환하는 문제다. (풀고 보니 슬라이딩 윈도우와 비슷한 방식으로 풀었다.)n = 문자열길이, k = 현재 윈도우 길이 (최대 n)이라고 가정할때, temp.contains(), temp.indexOf(), temp.substring(...) + s[i] 모두 O(k)의 시간복잡도를 갖고, 이 연산이 최대 n번 반복될 수 있다. 시간복잡도 : O(n^2) 문자열 연산이 계속 일어나므로 새로운 문자열이..

행렬 채우기 1) set-matrix-zeroes문제 : https://leetcode.com/problems/set-matrix-zeroes/0이 표시된 행렬의 열과 행을 모두 0으로 바꾸는 문제이다. 1. 모든 0위치를 찾아 저장하고 해당 열과 행을 전체 0으로 설정하는 방법 시간 복잡도 : O(m x n) + z (0의 갯수) * (O(m+n)공간 복잡도 : 최대 O(m x n) (0의 갯수를 따로 저장함)class Solution { fun setZeroes(matrix: Array): Unit { if(matrix.size == 0) return val zeros = mutableListOf>() val v = matrix.size ..

Floyd’s Cycle Detection Algorithm - 투포인터 문제   플로이드의 사이클 탐지 알고리즘이란 연결 리스트에서 사이클을 감지하는 문제에서 자주 사용되는 알고리즘으로 토끼와 거북이 알고리즘으로도 불린다. 두개의 포인터를 사용해서 리스트를 탐색하는데, 하나의 포인터는 거북이처럼 한칸씩 이동하고, 나머지 포인터는 토끼처럼 m칸씩 움직인다. (2칸) 만약 사이클이 없다면, 빠른 포인터는 끝(fast.next == null)에 도달하고, 사이클이 존재한다면 느린 포인터를 결국 따라잡게 된다. (slow == fast) 시간 복잡도 : O(n)공간 복잡도 : O(1)  1) linked-list-cycle 문제 : https://leetcode.com/problems/linked-list-c..

Clone Grpah 문제 링크 : https://leetcode.com/problems/clone-graph/description/dfs를 이용해서 deepCopy를 수행하는 문제다. /** * Definition for a Node. * class Node(var `val`: Int) { * var neighbors: ArrayList = ArrayList() * } */class Solution { fun cloneGraph(node: Node?): Node? { if(node == null) { return null } val map = mutableMapOf() return dfs(node, map) } ..