본문 바로가기

전체 글

 (207)
[알고리즘] BFS 구현 개념 너비 우선 탐색으로, Breadth-First-Search, 줄여서 BFS라고 한다. 인접한 노드들을 우선 탐색하는 방식이다. 위의 이미지에서 숫자가 탐색하는 순서라고 생각하면 된다. 탐색 노드부터 인접한 노드들을 탐색하고 -> 모두 탐색하면 그 노드들의 인접한 노드들부터 탐색하는 것이다. 같은 레벨에 있는 (같은 층에 있는) 노드들부터 탐색하는 것이라고 생각하면 된다. 🤔 오른쪽? 왼쪽? 참고로 너비 우선 탐색에서 하나의 노드에서 인접 노드들 중 오른쪽을 먼저 탐색하는지 / 왼쪽을 먼저 탐색하는지 순서는 중요하지 않다. ➡️ 같은 레벨에 존재하기 때문에, 어디를 먼저 탐색하더라도 같은 레벨에 있는 노드를 먼저 탐색해야 다음 레벨(아래)로 이동할 수 있기 때문이다. 구현 0. 그래프 생성 왼쪽과 같..
[자료구조] 그래프 알고리즘 문제를 풀면서 한번씩은 접하게 되는 개념이 BFS(너비 우선 탐색) / DFS(깊이 우선탐색)이다. 이 방식들은 그래프를 순회하는 방식을 의미한다. 그래프 그래프란, 노드(정점)와 간선으로 이루어진 자료구조이다. 정확하게 설명하자면 정점간의 관계를 표현하는 조직도라고 볼 수 있다. *트리와 그래프 노드? 간선? 은 트리 구조에서도 나오는 개념이다. 트리는 그래프의 일종이라고 할 수 있다. ✔️ 트리와 다르게 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며 ✔️ 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. 그래프는 네트워크 모델 즉 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 실생활의 다양한 예를 그래프로 표현할 수 있다. 대표적으로 지하철 노선도, 도..
[앱 심사] Kids Category도 순순히 넘어가지 않는다. 이 글을 쓰고 있는 지금 .. 월요일 오후 6시 ... 낮잠을 퍼질러 자고 일어나보니 리젝이 와 있었고 ... 사유는 다음과 같다. 비슷한 앱의 나이대를 살펴보니, 4+로 되어 있었기 때문에 나도 마찬가지로 4+로 설정했지만 위와 같은 이유로 (4세 이하의 어린이들을 위해 특별히 제작된 부분이 없는 것 같다 .. 어쩌구) 리젝을 먹었다 .. 디질랜드? 근데 맞는 말임. 4세가 어떻게 나눔카를 이용하겠어? 그래서 제출을 취소하고 관련된 곳으로 이동해서 나이를 수정했다. 그리고 다시 심사에 추가했다 .. 이번에는 제대로 통과되어라 응?? 제발~~
[자료구조] Queue(Deque) 구현 이 글은 자료구조라고 해야하는지, 알고리즘이라고 해야하는지 모르겠지만 일단 자료구조라고 했다. 앞선 글에서도 많이 언급한 것처럼 Swift에는 Queue(Deque)가 없어서 구현을 직접해야한다. 알고리즘 문제를 풀 때 시간초과 같은 오류가 발생하지 않기 위해서는? class Queue { var array: [T?] var head = 0 var isEmpty: Bool { return count == 0 } var count: Int { return array.count - head } var first: T? { return isEmpty ? nil : array[head] } var last: T? { return isEmpty ? nil : array.last! } init(_ array: [T..
[왈] Mal 어쩌구 오류 정확한 오류의 이름을 알고 싶지만 .. 지금은 해결을 해서 .. 다시 오류가 나타나면 그 때 사진 캡처하겠음 .. (두번 다시 보기 싫지만 .. 어차피 보게 될 것 ..) 오류의 원인은 모르겠고 .. 예방법도 모르지만 .. 처리방법은 안다. 후리방구가 알려줬다. 샷아웃투 후리 (넌 나비스콜링? 난 후리스콜링) 이제 해결방법은 .. 아래의 순서대로 따라서 하면 된다. 1. 엑스코드를 끈다. (당황하지 말고 울지 말고 ..) 2.워크 스페이스로 이동해서 패키지 내용을 본다. 3. 아래의 폴더 중에서 xcshareddata로 이동한다. 4. 그리고 아래에 보이는 것처럼 swiftpm 폴더를 삭제한다. 5. 그리고 다시 엑스코드로 돌아와서 클린 빌드를 하고 제대로 spm이 fetching 되는지 확인한다. 그러..
[자료구조] Queue 이전에 올린 스택의 경우 Swift에서는 배열을 스택처럼 사용할 수 있었다. (append(), removeLast() 등의 메서드를 사용해서) 그러나 큐의 경우 Swift에서 따로 지원하지 않기 때문에 만약 알고리즘 문제를 풀면서 큐를 사용할 일이 있다면 따로 만들어서 사용해야 한다. 큐는 선입선출 FIFO 구조이다. enqueue : 맨 뒤에 원소 추가 dequeue : 맨 앞에 원소 삭제 peek : 첫 번째 위치한 데이터 읽기 clear : 큐 재설정해 빈 상태되게 하기 count : 큐에 있는 요소의 수 반환 isEmpty isFull 구현 구조체와 배열로 아래와 같이 구현할 수 있다. struct Queue { private var queue: [T] = [] public var count: ..
[자료구조] Stack Swift에서 Stack을 구현하고 싶다면 배열을 사용해서 구현할 수 있다. Stack이란? c b a 위와 같은 스택 구조가 있다면 a -> b -> c 순으로 스택에 들어갔을 것이고 나올 때는 c -> b -> a 순서로 나오게 된다. 즉, 스택은 FILO 구조이다. 구조의 마지막에 추가/삭제 되기 때문에 시간 복잡도는 O(1)를 갖게 되며 그러므로 오버헤드는 발생하지 않는다. Stack 구현 아래와 같이 구조체와 배열을 사용해서 스택을 구현할 수 있다. struct Stack { private var stack: [T] = [] public var count: Int { return stack.count } public var isEmpty: Bool { return stack.isEmpty } p..
[자료구조] 연결 리스트 (양방향) 단방향 연결 리스트의 경우 아래와 같이 원하는 데이터를 찾고 싶으면 head부터 순회해야 하므로 만약 찾고자 하는 데이터가 마지막에 있다면 모든 연결 리스트를 순회해야 하는 단점이 있다. (마지막 노드가 무엇인지 모르기 때문에) 이를 보완한 것이 양방향 리스트이다. 양방향 연결 리스트 가장 첫 노드를 가리키는 head와 가장 마지막 노드를 가리키는 tail을 두고 하나의 노드에 대해서 이전 노드와 다음 노드를 모두 연결해서 양방향으로 탐색이 가능한 것이 양방향 연결 리스트이다. 그러므로 위의 단방향의 경우 마지막 노드와 가까운 데이터를 찾는 경우 head부터 하나씩 순회해야 하는 단점이 있었지만, 양방향의 경우 찾고자하는 데이터가 연결 리스트의 마지막 노드와 가깝다면 tail을 이용해서 찾으면 되고 찾고..

티스토리툴바