본문 바로가기

Algorithm/Study24

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.
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.
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.
Swift - Graph Implemetation Swift Algorithm Club: Graphs with Adjacency List Learn how to implement directed and undirected graphs in Swift using adjacency lists. www.raywenderlich.com Adjacency List 구현 인접리스트 구현 방식 Storing an array of arrays Storing an array of linked-lists Storing a dictionary of arrays 인접 리스트 구현 #1 Vertex import Foundation public struct Vertex { var data: T } extension Vertex: Hashable { public var hashV.. 2020. 7. 20.
Java 중복유무 순열 조합 import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; public class main { static int[] arr = {1, 2, 3, 4}; public static void main(String[] args) { int n = arr.length; //순서있는 모든 경우의 수 LinkedList perArr = new LinkedList(); int[] perCheck = new int[n]; for (int r = 0; r 2020. 7. 11.
Swift - 순열(Permutation) 1,2,3,4,5,6,7,8,9 중에서 중복되지 않고 3개를 뽑는 모든 경우의 수를 만들어라 예를들어 [1,2,3] [1,2,4] ... [9,8,7] 코드 import Foundation func permutation(_ arr : [Int],_ output : [Int],_ visited : [Bool],_ depth : Int,_ n : Int,_ r : Int){ var arr = arr var output = output var visited = visited if depth == r { // stack.append(output) print(output) return } for i in 0.. 2020. 7. 11.
Swift - BFS iteration on Binary Tree [1,3,2,5,3,null,9] func bfs(_ root: TreeNode?) -> Int { if root == nil { return 0 } var maxWidth = 0 var queue : [TreeNode] = [] queue.append(root!) while(!queue.isEmpty){ var count = queue.count maxWidth = max(maxWidth,count) while(count > 0){ var tmp = queue.removeFirst() print(tmp.val) if(tmp.left != nil){ queue.append(tmp.left!) } if(tmp.right != nil){ queue.append(tmp.right!) } count -= 1 }.. 2020. 7. 9.
Swift 배열 처리 String 과 Int 를 넘나드는 데이터 타입 변경 배열 반대로 순회 배열을 String으로 리턴 코드 import Foundation var arr1 : [Int] = [3,2,3,1,2,8,6,4,3,5,2,3,2,1] var arr2 : [Int] = [9,7,5,4,3,4,2,1,3,5,0,5,4,3] var answer : [Int] = [] var carry = 0 for i in (0.. 2020. 7. 4.
📕 잠깐 내가 이해한게 맞는지 정리 Dynamic Programming Greedy Back Tracking Branch and bound Greedy는 반례가 있어서 적용 안되는 경우가 있다. - 0-1 knapsack problem Greedy가 적용되지 않는 경우 Dynamic Programming 을 쓴다. Dynamic Programming 이 적용되지 않을 때 BackTracking을 쓴다. - Dynamic Programming 은 2^n의 부분집합을 검사하니까 오래걸리는데 이걸 Backtracking이 Tree 형태의 pruned state space tree 로 promising 하는 경우만 check 한다. Backtracking 에서 발전된게 Branch and bound 이다. 그리디는 local 한 최적해를 구하고 .. 2020. 6. 19.
😈 Greedy & Prims Algorithm (feat MST) 탐욕 알고리즘이란 답을 하나씩 고르는데 미리 정한 기준에 따라 매번 가장 좋아 보이는 답을 선택한다. *동적 프로그래밍과 마찬가지로 최적화 문제를 푸는데 사용된다. 동적 계획법과 다른점 동적 계획법 1. 재귀 관계식을 세워서 2. 입력 사례를 더 작은 입력사례로 분할 탐욕법 1. locally 최적의 경우 선택 2. 적절성 검사 3. 해답 점검 *전체적으로 최적인 해를 구하지만 항상 최적인 해를 얻는다는 보장이 없다. --> 최적인 해답을 얻는지 확인하는 절차가 반드시 필요하다. 거스름 돈 문제 : 동전의 개수가 최소가 되도록 거스름돈을 주는 문제 빈손으로 시작한다. 액면가가 가장 높은 동전을 집어 손에 올린다. (선택과정) 손에 있는 거스름 돈의 총액이 거슬러 주는 액수를 초과하는지 확인한다. (적절성.. 2020. 6. 18.
01. 배열과 문자열 Hash table 효율적인 탐색을 위한 자료구조 key-value 방식 구현방법 키의 해시 코드를 계산한다. (키의 개수는 무한한데 int 의 개수는 유한하기 때문에 서로다른 두 개의 키가 같은 해시코드를 가리킬 수 있다.) hash(key) % array_length 같은 방식으로 해시코드를 이용해 배열의 인덱스를 구한다. (서로다른 두개의 해시 코드가 같은 인덱스를 가리킬 수 있다.) 배열의 각 인덱스에는 키와 값으로 이루어진 연결 리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 충돌에 대비하여 반드시 연결 리스트를 이용한다. (충돌 : 서로다른 두 개의 키가 같은 해시 코드를 가리킬때, 서로다른 두 개의 해시 코드가 같은 인덱스를 가리킬때) 값을 찾을 때 주어진 키로부터 해시 코드를 계산하.. 2020. 6. 9.
문제해결 전략 - 30. 최단 경로 알고리즘 최단경로 문제 주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제 가중치가 있는 그래프에서의 최단 경로를 찾는 알고리즘을 다룬다. 최단 경로를 구성하는 정점들의 목록을 구해주는 것이 아니기 때문에 실제 경로를 계산하기 위해서는 별도의 정보를 저장해야 한다. 다양한 그래프의 종류와 특성에 따라 최적화된 많은 최단 경로 알고리즘이 존재한다 음수 간선의 중요성 음수 간선을 지나가면 전체 경로의 길이가 짧아진다. 음수 사이클이 있을 경우 경로의 길이는 음의 무한대로 발산 할 수 있다. 그래서 최단 경로를 찾을 수 없으며 음수 사이클이 존재한다는 것만 확인할 수 있다. 단일 시작점과 모든 쌍의 알고리즘 단일 시작점 알고리즘 : 너비 우선 탐색과 비슷하게, 하나의 시작점에서 다른 모든 .. 2020. 5. 29.
문제해결 전략 - 29. 그래프 너비 우선 탐색 그래프 너비 우선 탐색 너비 우선 탐색은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘 구현 방법 각 정점을 방문할 때 마다 모든 인접 정점들을 검사한다. 이중 처음 보는 정범을 발견하면 이 정점을 방문 예정이라고 기록한 뒤 별도의 위치에 저장한다. 인접한 정점을 모두 검사하고 나면 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문한다. 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정된다. 특징 깊이 우선 탐색과 달리 너비 우선 탐색에서는 발견과 방문이 같지 않다. 모든 정점은 아래와 같은 세 상태를 순서대로 거친다. 아직 발견되지 않은 상태 발견되었지만 아직 방문되지 않은 상태(정점들의 목록이 큐에 저장되어 있음) 방문된 상태 시간 복잡도 깊이 우선 탐색과 같다. 모든 정점을 한 번.. 2020. 5. 22.
문제해결 전략 - 28. 그래프 깊이 우선 탐색 그래프 탐색 알고리즘 그래프의 모든 정점을 특정한 순서에 따라 방문하는 알고리즘 트리보다 구조가 훨씬 복잡하기 떄문에 탐색 과정에서 얻어지는 정보가 중요하다. 탐색과정에서 알 수 있는 정보 어떤 간선이 사용되었는지 어떤 순서로 정점들이 방문되었는지 깊이 우선 탐색(Depth-first search) 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 해당 간선을 무조건 따라감 더이상 갈곳이 없는 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 이동 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도한다. 지금까지 거쳐온 정점들을 모두 알고 있어야 하는데 재귀호출을 이용하면 간단히 구현.. 2020. 5. 14.

티스토리툴바