본문 바로가기

Algorithm102

LRU cache (Swift) LRU Cache - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com cache 가 full 이면 가장 오래전에 사용한 애를 cache 에서 쫒아내야한다. O(1) 로 구현해야 한다. 필요한 조건 분석 fast lookup O(1) fast removal O(1) least recently used 기록 fast access / look up 을 생각하면 HashMap 이 생각나야 한다. fast removal / least recently used 를 생각하면 .. 2021. 1. 29.
876. Middle of the Linked List Middle of the Linked List - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 링크드 리스트의 중간 값을 들고오는 문제이다. 한바퀴 돌면서 size 를 알고 중간 index까지 한번더 순회 extra array 저장해서 count/2 둘다 딱히 정답같은 느낌은 아니다. 주먹구구 구현 class Solution { func middleNode(_ head: ListNode?) -> ListNode? { var curr = head var arr .. 2021. 1. 28.
LinkedList (Swift) 연결 리스트 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. ko.wikipedia.org 링크드 리스트 구조 연결 리스트 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 링크드 리스트는 떨어진 곳에 존재하는 데이터를 포인터를 이용해 연결해서 관리하는 데이터 구조 미리 데이터 공간을 할당할 필요가 없음 배열에 비해 다음 노드 위치를 저장할 공간 필요 배열에 있는 index가 없어서 direct access가 안됨 (접근 속도 느림) Doubly Linked List (양방향) 노드 class Node : Equatable { var prev : Node? var next : Node? var value : T init(value : T) { self.value = va.. 2021. 1. 28.
다익스트라 알고리즘 최단경로 찾기 문제 우선순위 큐를 이용한다. Swift에서 우선순위큐는 직접 만들어야 한다. min Heap 으로 만들면 최적이지만 구현의 편리함을 위해 이번 코드에서는 배열로 sort 해서 removeLast로 min값을 찾아 처리한다. //dijkstra var graph : [String: [(String,Int)]] = [:] graph.updateValue([("B",8),("C",1),("D",2)], forKey: "A") graph.updateValue([], forKey: "B") graph.updateValue([("B",5),("D",2)], forKey: "C") graph.updateValue([("E",3),("F",5)], forKey: "D") graph.updateValue.. 2021. 1. 21.
탐욕 알고리즘과 예제문제 (Swift) Greedy algorithm 최적의 해에 가까운 값을 구하기 위해 사용 여러 경우 중 하나를 결정해야 할 때 마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식 동적 계획법(DP)과 비교 길을 찾을때 동적계획법: 모든 경우의 길을 전부 확인하고 최단 경로를 찾아서 출발 탐욕법: 일단 출발하고 갈림길에 따라 최적의 경로로 생각되는 길을 선택 [출처 및 자세한 내용] 동적 계획법(Dynamic Programming)과 탐욕법(Greedy Algorithm) 0x1X28uI-8A6oGM7.jpeg가장 빨리 가는 길을 찾고 싶다. 한 가지 방법은 출발하기 전, 가는 거리와 신호등, 교통 상황 등을 전부 계산해서 최적의 길을 찾는 것이다. 머리가 깨질 듯이 전부 확인.. 2021. 1. 20.
Graph Swift (BFS, DFS) Graph 표현 Dictionary + Array var graph : [String: [String]] = [:] graph.updateValue(["B","C"], forKey: "A") graph.updateValue(["A","D"], forKey: "B") graph.updateValue(["A","G","H","I"], forKey: "C") graph.updateValue(["D","B","E","F"], forKey: "D") graph.updateValue(["E","D"], forKey: "E") graph.updateValue(["F","D"], forKey: "F") graph.updateValue(["G","C"], forKey: "G") graph.updateValue(["H",.. 2021. 1. 20.
이진탐색 Binary Search - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 탐색 알고리즘 순차탐색 해시구조 BST 이진탐색 class Solution { func search(_ nums: [Int], _ target: Int) -> Int { var head = 0 var tail = nums.count-1 while head 2021. 1. 19.
Traversing Tree (recursive, iterative) Tree traverse 할때 iterative 하게 하려면 Stack 사용 level traverse 의 경우 Queue 사용 Binary Tree 일 경우 node nil 로 loop 가능 N-ary Tree Preorder Traversal - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com /** * Definition for a Node. * public class Node { * public var val: Int * public var children.. 2021. 1. 18.
Swift Heap Heap 여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조 완전 이진 트리 (이진 탐색 트리와 다름) 중복허용 트리 좌측부터 node 추가됨 삽입 완전 이진트리 만족하게 배열의 맨 마지막에 삽입 부모노드와 비교하며 한칸씩 올림 삭제 heap 에서는 root를 삭제함 (우선순위큐) root 삭제 제일 작은 값 (배열끝값) 을 root로 옮김 child node 와 비교 (둘다 클 경우 둘 중 큰값과 swap) code import Foundation var heap : [Int] = [] //본인 index i 일때 //parent index: i/2 //left child index: 2*i //right child index: 2*i+1 heap.append(-1.. 2021. 1. 18.
이진트리 연산 Maximum Depth of Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com node count leaf node node height /** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.. 2021. 1. 16.
이진트리 순회 Range Sum of BST - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 전위 순회 부모노드를 먼저 처리한 후에 자식노드를 처리해야 할때 후위 순회 자식노드를 먼저 처리한 후에 부모노드를 처리해야 할때 (ex, 디렉토리 용량 계산) /** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public.. 2021. 1. 16.
Swift Sorting Algorithm Note 1. 선택 정렬 정렬되지 않은 맨 앞에서 부터 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾는다. 가장 작은 값을 찾으면 그 값을 현재 인덱스와 바꿔준다. 다음 인덱스에서 위 과정을 반복한다. 시간 복잡도: O(n^2) 공간 복잡도: O(n) 5 2 3 1 1 5 2 3 1 2 5 3 1 2 3 5 class Solution { func sortArray(_ nums: [Int]) -> [Int] { var nums = nums for i in 0.. [Int] { var nums = nums var tmp = 0 for i in 0.. swap // let tmp = nums[i] // nums[i] = nums[j] // nums[j] = tmp // } } tmp = nums[minIndex.. 2021. 1. 13.
LeetCode - Remove Duplicates from Sorted Array 문제 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Example 1: Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It does.. 2020. 9. 11.
Swift 다항식 덧셈 Dictionary 를 사용했다. key는 차수 expo value는 계수 coef 차수 높은걸 기준으로 돌면서 key 같으면 더해서 value를 update 해준다. 나머지 b를 더해준다. //3x^3 + 2x^2 + 1 //4x + 2 //key: expo, value: coef, expo var a : [Int:Int] = [3:3, 2:2, 0:1] //3x^3 + 2x^2 + 1 var b : [Int:Int] = [1:4, 0:2] //4x + 2 var ans : [Int:Int] = [:] //assume a degree is higher a.forEach { (key,value) in if b[key] != nil { //a와b 계수가 같은게 있다면 ans.updateValue(b[key.. 2020. 9. 11.
6 Recursive Pattern [출처] 6 Patterns Each pattern provides a basic framework one you understand the framework, you can fit all problems into one of these frameworks these patterns overlap extensively - find the pattern that works for you all patterns are based on basic recursive principles Index Iteration Breaking into Subproblems selection ordering divide and conquer depth-first search Iteration iterate over array/.. 2020. 9. 11.
LeetCode - Fibonacci Number, Climbing Stairs 문제 The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), for N > 1. Given N, calculate F(N). Example 1: Input: 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1. Example 2: Input: 3 Output: 2 Explanation: F(3) = F(2.. 2020. 9. 10.
LeetCode - Pascal's Triangle II 문제 Given an integer rowIndex, return the rowIndexth row of the Pascal's triangle. Notice that the row index starts from 0. Follow up: Could you optimize your algorithm to use only O(k) extra space? Example 1:Input: rowIndex = 3 Output: [1,3,3,1] Example 2: Input: rowIndex = 0 Output: [1] Example 3: Input: rowIndex = 1 Output: [1,1] Constraints: 0 2020. 9. 10.
LeetCode - Search in Binary Search Tree 문제 Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL. For example, Given the tree: 4 / \ 2 7 / \ 1 3 And the value to search: 2 You should return this subtree: 2 / \ 1 3 In the example above, if we want to sea.. 2020. 9. 10.
LeetCode - Reverse Linked List 🤦🏻 문제 Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both? Iteratively - O(N) Time, O(1) Space /** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init() { self.val = 0; self.next = n.. 2020. 9. 9.
LeetCode - Swap Nodes in Pairs Swap Nodes in Pairs - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes itself may be changed. Example: Given 1->2->3->4, you should return the lis.. 2020. 9. 3.
LeetCode - Reverse String Reverse String - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Write a function that reverses a string. The input string is given as an array of characters char[]. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) e.. 2020. 9. 3.

티스토리툴바