- [ 코딩테스트/프로그래머스 ][프로그래머스] 타겟 넘버(Swift)2024-08-22 16:45:45난이도: Level 2 사용 알고리즘: DFS index를 돌면서 모든 경우의 수들 중 sum이 target과 일치하면 되는 문제였다.그림(못남)처럼 dfs로 모든 경우의 수를 따라가도록 하였다. import Foundationfunc solution(_ numbers:[Int], _ target:Int) -> Int { var count = 0 func dfs(idx: Int, sum: Int) { if idx == numbers.count && sum == target { count += 1 return } if idx + 1
- [ 코딩테스트/백준 ][백준/BOJ] 1520번 내리막 길(Swift)2024-08-18 21:22:15문제 난이도: 골드 3 사용 알고리즘: DFS, DP M,N은 각각 500 이하이고 최대 250,000까지 연산이 필요하다.제한 시간은 2초이므로 200,000,000번(2억번)의 연산이 넘어가게 되면 시간초과가 된다. 대충 O(N^4)을 넘지 않으면 시간초과는 뜨지 않는다. 첫번째 풀이는 DFS에 백트래킹을 적용해서 문제풀이를 진행했다.다만 백트래킹을 적용하게 되면 셀의 모든 방향에 대하여 재귀 호출이 발생하여 시간초과가 뜬다.import Foundationlet size = readLine()!.split(separator: " ").map { Int($0)! }let y = size[0]let x = size[1]var map: [[Int]] = []var visited = Array(repeati..
- [ 코딩테스트/백준 ][백준/BOJ] 2468번 안전 영역(Swift)2024-08-15 22:24:57문제 난이도: 실버 1 사용 알고리즘: DFSimport Foundationlet n = Int(readLine()!)!var map: [[Int]] = []var heights = Set()var sortedHeights = [Int]()let directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]var visited = Array(repeating: Array(repeating: false, count: n), count: n)var mapCount = 0var result = 0for _ in 0 ..= n || y = n || map[y][x] i { dfs(x: x, y: y, height: i) mapCoun..
- [ 알고리즘 ][알고리즘] DFS(Depth-First-Search, 깊이 우선 탐색)2024-08-13 15:07:20DFS란? 그래프 탐색 알고리즘으로 그래프의 모든 정점(vertex)을 깊이 탐색하는 방법(알고리즘) DFS는 시작 정점에서 인접한 정점들을 방문하고, 인접 정점들의 인접 정점을 방문하는 방식으로 동작한다.BFS와 다르게 하나의 경로를 깊이(끝)까지 탐색한 후에야 다른 경로로 되돌아와 탐색을 진행한다. 표현 방법// 인접 리스트1 - [2, 8]2 - [1, 3, 6, 7]3 - [2, 4, 5]4 - [3, 5]5 - [3]6 - [2]7 - [2]8 - [1, 9]9 - [8]// 인접 행렬 1 2 3 4 5 6 7 8 91 [0 1 0 0 0 0 0 1 0]2 [1 0 1 0 0 1 1 0 0]3 [0 1 0 1 1 0 0 0 0]4 [0 0 1 0 1 0 0 0 0]5 [0 0 1 1 0 0..
- [ 자료구조 ][자료구조] 트리(Tree)2024-08-13 12:29:41트리란?트리는 그래프의 일종으로 계층적인 구조를 가지며 노드(Node)로 구성된다.각 노드는 데이터를 포함하고, 다음 노드들과 연결될 수 있다. 용어루트 노드(Root)- 부모가 없는 트리의 최상위 노드- 트리는 하나의 루트 노드 가짐 부모 노드(Parent)- 자식 노드를 가지는 노드로 상대적 개념- 2의 부모 노드는 1- 4의 부모 노드는 2 자식 노드(Child)- 부모 노드로 부터 가리켜지는 하위 노드- 1의 자식 노드는 2, 3- 2의 자식 노드는 4, 5 리프 노드(Leaf)- 자식 노드가 없는 트리의 말단 노드- 4, 5, 6이 해당 형제 노드(Sibling)- 같은 부모를 가지는 노드- 2, 3은 1을 부모 노드로 둔 형제 노드 레벨(Level)- 트리의 각 노드가 어느 깊이에 위치하는지 ..
- [ 자료구조 ][선형 자료구조] 덱/데크(Deque)2024-08-12 15:06:52덱(Deque)이란?덱(Deque)은 큐와 스택의 특성을 모두 가지는 자료구조이다.일반적인 큐와 달리, 덱은 양쪽 끝에서 삽입과 삭제가 가능하다. - 양쪽 끝에서의 삽입/삭제: 덱은 양쪽 끝에서 삽입과 삭제가 가능하며, 이로 인해 여러 가지 패턴의 자료처리가 가능합니다.- FIFO와 LIFO: 덱은 큐처럼 FIFO(First-In-First-Out) 방식으로도 동작할 수 있고, 스택처럼 LIFO(Last-In-First-Out) 방식으로도 동작할 수 있습니다. 구현class Deque { private var enque: [T] private var deque: [T] = [] var isEmpty: Bool { return enque.isEmpty && deque.i..
- [ 자료구조 ][선형 자료구조] 큐(Queue)2024-08-12 14:39:39큐(Queue)란?FIFO(First In First Out)으로 가장 먼저 삽입된 요소가 가장 먼저 제거되는 구조를 가진다.큐의 주요 연산으로는 Enqueue와 Dequeue가 있다. Enqueue - O(1)큐의 뒤쪽에 새로운 요소를 추가하는 연산 Dequeu - O(1)큐의 앞쪽에서 요소를 제거하고 반환하는 연산 사용 사례iOS GCD는 작업 수행을 위해 큐를 제공한다.UI 업데이트의 경우 메인 스레드에서 이루어져야 하기 때문에, GCD의 메인 큐를 사용하여 먼저 들어온 작업부터 처리하게 된다. 종류기본 큐 (Simple Queue)선입선출(FIFO, First In First Out) 방식으로 요소를 처리한다.원형 큐 (Circular Queue)배열의 끝과 시작이 연결된 형태로, 큐의 뒤쪽에서 ..
- [ 자료구조 ][선형 자료구조] 스택(Stack)2024-08-12 13:39:47스택이란?LIFO(Last In First Out)으로 가장 마지막으로 삽입된 요소가 가장 먼저 제거되는 구조를 가진다.이러한 특징을 가진 스택은 Push와 Pop을 기본 연산을 가지게 된다. Push데이터를 스택 맨 위에 쌓는 연산 Pop스택 맨 위에 데이터를 제거하고 반환하는 연산 사용 사례iOS에서 실제로 UINavigationController는 Push, Pop을 통해 뷰컨트롤러들의 스택을 관리하며 화면을 나타낸다. 그 외에도 DFS를 사용할 때 깊이 탐색을 위해 Stack을 사용하여 재귀 호출을 대체할 수 있다. 구현struct Stack { private var elements: [T] = [] init() { } mutating func push(_ element: ..
- [ 코딩테스트/백준 ][백준/BOJ] 11725번 트리의 부모 찾기 (Swift, 스위프트)2024-08-11 19:01:48문제 난이도: 실버 2 사용 알고리즘: DFSimport Foundationlet vertexCount = Int(readLine()!)!var injacent: [[Int]] = Array(repeating: [], count: vertexCount + 1)var parent: [Int] = Array(repeating: 0, count: vertexCount + 1)var visited: [Bool] = Array(repeating: false, count: vertexCount + 1)for _ in 0 .. 인접 리스트로 우선 각각 연결된 노드들을 저장했다. [[], [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]] 1 - 6,42 - 43 - 6,54- 1..
- [ 코딩테스트/백준 ][백준/BOJ] 1987번 알파벳 (Swift 스위프트)2024-08-11 18:38:17문제 난이도: 골드 4 사용 알고리즘: DFS, 백트래킹 Set을 통해 한번 방문한 알파벳을 저장해놨다.Set은 중복값이 없기 때문에 이럴 때 유용한 것 같다. 아무튼 코드 자체는 기존 dfs와 다를게 없지만, visited.remove를 통해서 방문했던 곳은 다시 삭제해주는 코드로 짜주었다.방문한 알파벳을 지워주지 않으면, direction의 순서에 따라서 먼저 들어간 곳에 따라서 최대치가 바뀌기 때문에 모든 경로를 파악하여 맥스값을 프린트해주는 방법밖에 없었다.import Foundationlet rc = readLine()!.split(separator: " ").map { Int($0)! }let r = rc[0]let c = rc[1]var map: [[String]] = []var visite..
- [ 자료구조 ][선형 자료구조] 링크드 리스트2024-08-10 13:47:03링크드 리스트란? 데이터를 순차적으로 저장하는 선형 자료구조 중 하나이다.링크드 리스트의 요소는 노드(node) 형태로 존재하는데, node 안에는 데이터와 다음 노드의 메모리 위치를 가리키는 포인터로 이루어져 있다. 주요 특징연속적이지 않은 메모리 주소 링크드 리스트의 요소인 노드는 다시 두가지 부분으로 구성된다.- 데이터(Data): 노드가 저장하는 실제 데이터- 다음 노드(next node): 다음 노드의 메모리 위치를 참조하는 포인터 이렇게 구성 된 이유는 일반 배열의 경우 연속된 메모리 주소를 가지기 때문에, 삽입과 삭제시 O(n)의 시간복잡도를 가지게 된다.하지만 링크드 리스트의 경우 삽입/삭제시에도 가리키는 다음 주소만을 추가/수정해주면 되기 때문에 삽입/삭제 자체만으로는 O(1)의 시간복잡..
- [ Swift ][Swift] LayoutSubivews2024-08-08 22:08:03개발을 하다보면, View의 너비나 높이를 알고 싶어도 ViewDidAppear 이 후에나 확인이 가능하다.그러다 layoutSubviews 메서드 내부에서는 언제든 너비나 높이를 확인할 수 있어서 자주 사용하고 있었다. layoutSubviews가 정확히 언제 호출되고 무슨 역할인지 알아보려 한다. LayoutSubviews란?layoutSubviews 메서드는 UIView의 서브뷰들의 배치와 크기가 어떻게 조정될지 결정한다. 자동 호출 시점- View의 Frame 또는 Bounds가 변경될 때- 서브뷰가 추가 또는 삭제 될 때 - 뷰가 처음 화면에 표시될 때 직접적인 호출을 하지 않아도 됨 이처럼 아직 view가 나타나지 않은 viewWillAppear 시점과 view가 나타났음을 알려주는 viewD..