조이의 개발 성장 다이어리

문제를 보면 입력 데이터의 개수를 보고 시간복잡도부터 계산하자 (코테의 가장 기본) 1초 = 1억번 연산 임을 인지하고 이를 토대로 시간복잡도를 계산하여, 시간초과가 나지 않을 적절한 알고리즘을 선택해야함 보통 프로그래머스의 경우 명시를 해두지 않았다면 제한 시간이 10초 라고 한다. O(1): 입력 데이터의 개수와 상관없이 항상 상수의 시간을 가지는 알고리즘 (ex. 배열의 마지막 수 꺼내오기, 해시 테이블 삽입/삭제/검색) O(logn): 크기가 커지면 커질수록 처리 시간이 절반으로 줄어드는 알고리즘 (ex. 이분탐색, 힙(우선순위 큐)) O(n): 입력 데이터의 개수만큼 시간이 소요되는 알고리즘 (ex. for문 1개, 배열/문자열 탐색, 배열/문자열 재정렬, set()으로 중복 제거) O(nlog..

우선순위 큐(Priority Queue) 란? 기존의 큐(Queue)가 선입선출(FIFO, First-In, First-Out) 구조였다면 우선순위 큐는 우선순위가 높은 데이터가 먼저 선출되는 구조의 자료구조이다. 주로 우선순위 큐는 최소값/최대 값부터 먼저 빠져나오는 힙을 사용하여 구현한다. 힙 포스팅 참고 Swift로 우선순위 큐 구현하기 최소힙/최대힙 원리를 알고 구현했으면 그걸 그대로 가져오기만 하면 된다. import Foundation struct PriorityQueue { var heap = Heap() var count : Int { return heap.count } var isEmpty : Bool { return heap.isEmpty } mutating func pop() -> T..

Swift로 힙을 구현하기 전에, 우선 힙의 개념을 정리해보고자 한다. 힙(Heap) 이란? 1) 완전 이진 트리 (왼쪽에서 오른쪽으로 차례대로 채워진 이진 트리) 2) 최소 힙 : 부모 노드의 값은 항상 자식 노드들의 값보다 작거나 같다. (보통 코딩테스트에서는 이걸 기본으로 하고, 최대를 구해야할 때는 음수로 치환해서 품. 다익스트라 알고리즘에서도 사용) -> 루트 노드가 최소값 최대 힙 : 부모 노드의 값은 항상 자식 노드들의 값보다 크거나 같다. -> 루트 노드가 최대값 * 우선순위 큐를 구현할 때 힙을 자주 쓰는 이유는, 노드의 값이 작아질수록 혹은 클수록 우선순위가 높아진다고 고려했을 때 힙에서 데이터를 추출할 때 우선순위가 높은 것(가장 작은것 혹은 가장 큰 것)부터 먼저 추출되므로 우선순위..

문제 : https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 처음 풀이 : let input = readLine()!.split(separator:" ").map { Int(String($0))! } let N = input[0] let M = input[1] var dic:[Int:String] = [:] var answer:[String] = [] for i in 1...N { dic[i] = readLine()! ..

문제 : https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 내 풀이 import Foundation let N = Int(readLine()!)! let input = readLine()!.split(separator:" ").map { Int(String($0))!} var q = (1...N).map { ($0, input[$0-1])} /* q는 아래와 같이 초기화하는 것도 가능함! (enumerated() 사용) 1) v..

본 포스팅은 '스위프트 프로그래밍 (3판) - 야곰 저' 도서와 앨런 Swift 문법 마스터스쿨 강의를 통해 공부하며 정리하는 포스팅입니다. 혹시 틀린 부분이 있거나 질문이 있으시다면 언제든지 댓글 달아주시면 정말 감사하겠습니다 :) 1. 옵셔널 1) 옵셔널이란? - 값이 '있을 수도, 없을 수도 있음'을 나타내는 표현으로, 데이터 타입 뒤에 물음표(?)를 붙여 표현함 - 변수를 선언은 했으나 값이 할당되지 않았을 때 접근할 경우 컴파일 에러가 발생하므로, 개발자의 실수로 인해 컴파일 에러가 발생할 가능성을 줄여주기 위해서 사용하는 개념 - 옵셔널은 기존 데이터 타입에 nil까지 더해 임시적으로 "값이 없을 수 있음"을 포장지로 한번 더 감싸는 것과 같다. - 즉 옵셔널 타입과 옵셔널이 아닌 타입은 ..

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17681 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 - 엄청 문제 그대로 날것으로 풀었다.. 허허 func solution(_ n:Int, _ arr1:[Int], _ arr2:[Int]) -> [String] { var arr1 = arr1.map { String($0, radix: 2)} //2진수로 변환 var arr2 = arr2.map { String($0, radix: 2)} var answer: [String] ..

혹시 틀린 부분이 있다면 지적해주시면 감사하겠습니다 :) 1. map vs flatMap vs compactMap https://limjs-dev.tistory.com/139 https://huniroom.tistory.com/entry/RxSwift-Transforming-Operator-toArray-map-compactMap 공통점 : 모두 Observable을 특정 로직을 적용하여 데이터를 바꾼다. 차이점 : - map은 변환 아이템을 Observable로 바꿔 return해주고, - flatMap은 단순히 Observable로 바꾸는게 아니라 평평하게 하나의 Observable로 바꿔준다. 예를들어 map은 Observable 이렇게 return 해주지만 flatMap은 Observable 이렇..

Disposable, Dispose RxSwift에서, 옵저버는 subscribe를 통해 이벤트를 전달받아서 처리하게 되는데, subscribe는 이후에 Disposable 을 반환한다. 또한 Disposable에는 'Dispose resource' 할 수 있는 dispose() 메소드가 제공된다. dispose의 원래 뜻은 '처분하다' 로, 이를 통해 유추해보면 이벤트에 대한 처리를 마치고 더이상 처리하지 않으니 구독을 해제해라! 라는 의미인 것으로 보인다. 정리하자면 subscribe의 반환값으로 Disposable 이 반환되고, 이벤트 처리가 끝나면 해당 구독을 유지할 필요가 없으니 구독을 해제해주는 과정이 dispose() 라고 할 수 있다. dispose를 꼭 해주어야만 하는 이유는, 구독이 끝..

Swift로 직접 자료구조 구현하기 - 덱 ✅ 간단하게 알아보는 덱 - 스택과 큐의 연산을 모두 가지고 있는 자료구조이다. - 앞, 뒤에서 삽입, 삭제 모두 가능한 자료구조 1) 뼈대 잡기 (더블 스택을 사용한 큐와 동일) struct Dequeue { var input = [T]() var output = [T]() var isEmpty : Bool { return input.isEmpty && output.isEmpty } var size: Int { return input.count + output.count } var first: T? { if isEmpty { return nil } return output.isEmpty ? input.first! : output.last! } var last:..