studlog

파라메트릭 서치란 최적화 문제를 결정 문제로 바꿔 이분 탐색을 이용해 해결하는 방법이다. 여기서 결정 문제란 예 혹은 아니오 형태의 답이 나오는 문제를 말한다. 예를 들어 외판원 문제를 최적화 문제와 결정 문제로 표현하면 아래와 같다.optimize(G) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 최단 경로의 길이를 반환한다.decision(G, \(x\)) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 길이가 \(x\)이상인 경로가 있는 있는가?최적화 문제의 답은 보통 실수, 정수이므로 답의 경우의 수가 무한개이지만, 결정 문제의 답은 예 혹은 아니오 이므로 답의 경우의 수가 2개이다.왜 결정문제로 바꿔서 푸는가?최적화 문제를 결정 문제로 바꾼 후 결정 문제를..

A circular queue can be implemented using array and linked list. To implement a circular queue using a linked list, you must use a circular linked list where the rear node is connected to the front node.Time Complexity AnalysisTime ComplexityEnqueue : \(O(1)\)Dequeue: \(O(1)\)Space Complexity : \(O(n)\) as the queue is size of \(n\)Circular Queue Implementation Using An LinkedList in C++Header I..

A circular queue is an extended version of a regular queue. Unlike a linear queue, the last element of a circular queue connects back to the first element, forming a circular structure. This is useful for efficiently managing fixed-size data buffers.Advantages of Circular QueuesEfficient Space Utilization: The circular nature allows reusing spaces once occupied by dequeued elements, avoiding the..

A doubly linked list is a data structure consisting of nodes, where each node contains three fields:Data: The value or information stored in the node.Prev: A pointer to the previous node in the list.Next: A pointer to the next node in the list.This structure allows traversal in both forward and backward directions, providing greater flexibility compared to a singly linked list.Advantages of Doub..

둘러쌓인 영역 찾기문제점경계와 인접한 영역은 어떻게 필터링할 것인가? 해결 아이디어경계에 있는 'O'에서 BFS를 수행해 경계와 인접한 영역을 찾는다.queue> q;for (int y = 0; y  관련 문제[Leetcode] Surrounded RegionsBFS에서 방문 체크의 상태가 2차원 배열인 경우문제점트리(map, int>)를 사용해 상태를 관리할 경우 메모리 및 시간 초과. 해결 아이디어2차원 배열 상태를 문자열로 변환하여 해시 키 값(unordered_map)으로 사용해 방문 체크를 한다. 관련 문제[BOJ 1525] 퍼즐방문할 수 없는 구역이 있는 경우방문할 수 없는 구역이란?(정점(\(X\), \(Y\))을 기준으로 거리 \(D\) 이하의 정점들의 영역) 해결 아이디어다익스트라 알고리..

상속 가능한 클래스는 메서드 오버라이딩이 가능한데요. 스위프트는 런타임에 vtable(virtual method table)을 참고해 어떤 메서드를 호출할지 결정합니다. 스위프트 OptimizationTips 문서에 따르면 런타임 성능을 올리는 방법 중 하나는 클래스 혹은 메서드에 final 키워드를 붙여 동적 디스패치(런타임 메서드 바인딩)를 줄이는 것이라고 합니다. 소스 코드를 raw SIL로 변환해 final 키워드에 따라 vtable의 차이를 눈으로 보려고 합니다.SIL in the Swift CompilerAt a high level, the Swift compiler follows a strict pipeline architecture.스위프트의 빌드 과정 중 컴파일 단계에서는 엄격한 절차가 ..

Subscription을 공유하여 동일한 데이터 스트림을 여러 곳에서 재사용해 리소스 사용을 최적화 해보자.RxSwift와 비교하기 [rxswift] Connectable Observable OperatorsObservable을 공유하게 하는 연산자 Observable은 구독자가 추가되면 항상 새로운 시퀀스를 만든다. 서버와 통신하거나 파일을 읽는 경우에 서로 다른 구독자가 같은 observable을 공유할 수 있도록 하여younggyun.tistory.comsharePublisher는 주로 구조체로 정의되어 있으며, 함수의 인자로 전달되거나 다른 속성에 할당될 때마다 스위프트에 의해 복사된다.struct Publisher : Publishershare()는 Publishers.Share 클래스의 인스턴..

개요Git 훅은 Git 작업 흐름 중 특정 이벤트가 발생할 때 실행되는 스크립트이다. Git 훅은 클라이언트 훅과 서버 훅으로 나눌 수 있다. 클라이언트 훅은 커밋이나 머지 이벤트가 발생할 때 실행되고 서버 훅은 푸시할 때 실행된다.기본적으로 Git은 .git/hooks에 있는 훅 스크립트를 사용한다. 기본 훅 디렉토리에는 Git이 기본으로 제공하는 훅이 있다. 기본 훅들은 sample 확장자를 가진 형태인데 sample확장자를 지우고 sh 명령어로 실행할 수 있다. pre-commit 훅에 SwiftLint 적용하기pre-commit 훅은 커밋 과정 중 가장 먼저 호출되는 훅으로 커밋 전에 실행된다. 이 훅을 사용해 코드 스타일, 코드 포맷, 테스트 등을 자동으로 실행하여 커밋 전 개발자가 실수한 것이..

Main event loop메인 이벤트 루프(Main event loop)는 메인 스레드의 런 루프이다. 메인 이벤트 루프는 애플리케이션이 시작될 때 생성된 애플리케이션(UIApplication) 객체에 의해 자동으로 생성되고 실행된다. 런 루프는 두 가지 종류의 입력 이벤트를 받을 수 있는데 메인 이벤트 루프는 유저로부터 입력 소스(Input Source) 이벤트를 받는다. 메인 이벤트 루프는 다른 런 루프와 다르게 멈추지 않는다. 따라서 입력 이벤트 핸들링과 애플리케이션의 상태와 뷰 업데이트를 계속해서 처리한다. 운영체제(iOS)는 유저로부터 입력받은 저 수준의 이벤트를 도착한 순서대로 이벤트 큐(Event Queue)에 넣는다. 애플리케이션 객체는 이벤트 큐에서 이벤트를 한 개 뽑아 이벤트가 발생한..

Automatic Reference Counting in Swift스위프트의 참조 타입 인스턴스는 힙 메모리에 저장되고 Automatic Reference Counting (or ARC) 방식으로 관리된다. ARC 방식은 단순한데 어떤 한 참조 타입의 인스턴스는 refCount라는 참조값을 가지고 이 인스턴스가 참조되면 참조값을 늘리고 더 이상 참조되지 않으면 참조값을 줄인다. 만약 참조값이 0이 되면 인스턴스의 생명이 끝난 것으로 판단하여 메모리에서 해제한다. ARC스위프트의 인스턴스는 생성자를 통한 초기화부터 마지막 사용될 때까지 메모리 위에 있다. 인스턴스의 참조 여부를 수동으로 계산해 retain 연산과 release 연산을 추가해야 하는 Objective-C의 Memory Reference Co..