문제 https://school.programmers.co.kr/learn/courses/30/lessons/49191 풀이 처음에 문제를 막 읽었을 때는 조금 어려워 보이지만, 문장을 살짝 다르게 해석해보자. ‘정확하게 순위를 매길 수 있는 선수의 수’를 알아야 하는데 정확하게 순위를 매긴다는 것은 어떨 때 성립할까? 특정 선수 A가 존재할 때, A와 서로 승패를 알 수 없는 선수 B가 존재하면 정확하게 순위를 매길 수 없는 것이다. 반대로 A가 다른 모든 선수들과 확실하게 승패의 결과를 알 수 있다면, 정확하게 순위를 매길 수 있다. 문제에서는 경기 결과를 제공해주므로, 선수들의 실력을 간접적으로 알 수 있다. 실력을 수치화 해서 관리할 수 있으면 좋지만, 그럴게 할 수 없는 조건이고 그럴 필요도 없다. 단순하게 선수들간의 ‘승’, ‘패’ 결과를 그래프로 관리해주면 된다. 승리 그래프와 패배 그래프를 따로 만들어서, 경기 결과를 그래프로 표현하고, 각 선수마다 이 선수가 승리할 선수, 패배할 선수의 수를 세어주면 된다. 특정 선수가 다른 모든 선수들과 확실하게 승패의 결과를 알 수 있다는 것은, 결국 승리할 선수와 패배할 선수의 합이 현재 선수를 제외한 나머지 선수의 수와 같은 것이기 때문이다. ...

Swift Concurrency는 Swift 5.5에서 도입된 기능이다. Foundation을 import 해야 쓸 수 있는 GCD와 다르게, Swift 언어 자체에 내장된 동시성 모델이다. Swift Concurrency는 크게 두 가지 부분으로 나뉘어진다. async, await 로 작성하는 새로운 동시성 모델 애플리케이션을 여러 동시성 태스크로 분할하는 Actor 이 포스트에서는 Swift Concurrency의 도입 배경을 알아본다. GCD의 한계 GCD는 Objective-C에서부터 사용해온 애플이 만든 비동기 API다. Queue 기반으로 작업을 스케줄링 하고, 스레드 위에서 추상화 되어있기 때문에 스레드를 직접 생성하거나 관리할 필요가 없다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17678 풀이 단순 구현으로 풀 수 있는 문제다. 문제를 단순화하면 조건에 맞는 최대 값을 구하는 문제이므로 바이너리 서치도 쓸 수 있겠다. 우선 시간을 다루는 문제에서는 시간, 분을 분으로 통일하는 경우가 더 시간을 다루기 쉬워지는 경우가 많다. 예를 들어서 셔틀의 첫 도착 시간인 9:00을 540으로 바꾸는 것이다. 그리고 timetable 배열의 길이가 최대 2000이므로 모든 배열을 순회해도, 심지어 $O(n^2)$시간으로 순회해도 아무런 걱정이 없다. 따라서 앞 번호부터 순서대로 버스에 태우면 된다. 이제 마지막 버스인 경우에 콘이 탈 수 있는 여유가 있다면, 마지막 버스의 도착 시간을 리턴하면 되고, 만약 여유가 없다면, 마지막 버스에 마지막으로 타는 사람보다 ‘1분’ 일찍 나오면 된다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12907 풀이 DP 문제다. 순열인지 조합인지 조심하면 쉽게 풀 수 있다. 문제에서 예시로 든 1, 2, 5원이 있을 때를 생각해보자. (5도 마찬가지지만) 2는 1의 배수이다. 따라서 순열로 하면 ‘3’을 만드는 경우에 1+1+1, 1+2, 2+1 이라는 세 가지 방법이 나오게 된다. 하지만 이 문제는 조합 문제이므로 중복을 제거해야한다. 그러면 중복을 어떻게 제거해야 할까? 작은 동전부터 순서대로 만들면 된다. 이 방법이 조합 DP의 가장 기본적인 방법이다. 가장 작은 동전을 써서 만들 수 있는 조합을 다 만든 다음 DP 테이블에 저장한다. 작은 순서대로 (오름차순으로) 조합을 더한다. 이런 식으로 하면 중복을 방지할 수 있다. 위 예제로 따지면 1원짜리 동전을 먼저 써서 1+1+1을 우선 만들고, 다음에 2원을 써서 1+2를 만든다. 작은 순서대로 하므로 알고리즘 상에서 2+1 같은 방법을 만들지 않는다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42627 풀이 우선 순위대로 문제를 처리하므로 힙을 써야하는 것은 명확하다. 하지만, 이 힙을 어떻게 다루느냐가 더 중요한 문제이기 때문에 사실상 힙보다는 단순 구현 문제에 가깝다. 코드 import heapq def solution(jobs): jobs.sort(key = lambda x: x[0]) waitQueue = [] finished = 0 currentTime = 0 jobIdx = 0 totalReturnTime = 0 while finished < len(jobs): while jobIdx < len(jobs) and jobs[jobIdx][0] <= currentTime: requestTime, duration = jobs[jobIdx] heapq.heappush(waitQueue, (duration, requestTime)) jobIdx += 1 if waitQueue: duration, requestTime = heapq.heappop(waitQueue) currentTime += duration returnTime = currentTime - requestTime totalReturnTime += returnTime finished += 1 else: currentTime = jobs[jobIdx][0] return totalReturnTime // len(jobs)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/64062 풀이 처음 문제를 읽어보고 바이너리 서치를 이용해야겠다고 생각했다. 결정해야 할 값을 건널 수 있는 최대 인원수로 맞춰놓고 바이너리 서치를 이용하여 찾으면 되기 때문이다. 바이너리 서치를 이용한 알고리즘은 다음과 같다. 바이너리 서치를 통해 찾고 싶은 값은 징검다리를 건널 수 있는 최대 인원 수이다. 징검다리 하나의 내구도가 최대 2억이므로 1에서 2억까지의 범위 내에서 인원 수의 최대값을 찾는다 값이 유효한지 체크하는 방법은 징검다리에서 현재 인원 수가 밟은 수를 뺀 다음 0 이하의 징검다리 돌들이 연속되는 경우가 k개 이하면 통과, 초과면 통과시키지 않는다. 바이너리 서치 결과를 리턴한다. 이 코드의 시간 복잡도는 $N$이 stones 배열의 크기, $M$이 돌 내구도의 최대값이라 했을 때 $O(N \log M)$이다. 돌 내구도의 최대값은 2억이고, 2의 30제곱이 약 10억이므로 30번 이내에 찾을 수 있다. 최대 20만 크기의 배열을 30번 정도 반복한다고 생각하면 충분히 시간 복잡도가 나온다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/64064 풀이 일정 크기의 배열(혹은 컬렉션)을 만들어서 매칭되는지 확인해야 하는 문제다. DFS를 사용해서 모든 경우의 수를 만들기는 쉽지만, 그 경우의 수가 문제에서 제시하는 조건에 맞는지 확인하는 것은 어렵다. 따라서 알고리즘을 약간 수정해서 좀 더 효율적이고 만들기 쉬운 알고리즘을 만들어야 한다. 알고리즘은 다음과 같다: 주어진 banned_id 배열 원소 하나하나에 대응가능한 id를 user_id에서 뽑아서 후보 set에 넣는다. 1번을 재귀적으로 진행한다. set에 담는 이유는 id가 중복되면 안되기 때문이다. 후보 set이 완성되면, 정답 set에 저장한다. set은 set에 담을 수 없으므로 frozenset을 이용한다. 정답 set의 개수를 리턴한다. 코드 def compare(strA, strB): if len(strA) != len(strB): return False for char in zip(strA, strB): if char[0] != char[1] and char[1] != '*': return False return True def dfs(user_id, banned_id, index, candidateSet, idSet): if index == len(banned_id): idSet.add(frozenset(candidateSet)) return for id in user_id: if id in candidateSet: continue if compare(id, banned_id[index]): dfs(user_id, banned_id, index + 1, candidateSet + [id], idSet) def solution(user_id, banned_id): idSet = set() dfs(user_id, banned_id, 0, [], idSet) return len(idSet)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42884 풀이 그리디 문제다. 그리디는 따로 정석 구현이 있는 알고리즘이 아니라 일종의 컨셉이지만, 배열 + 그리디면 잘 알다시피 정렬이 중요한 경우가 많다. 단순하게 생각해보자, 문제에서 주어지는 것은 시작 위치와 종료 위치다. 그냥 종료하는 위치를 기준으로 오름차순 정렬한 후에 앞에서부터 탐색을 한다. 현재 자동차의 종료 위치에 카메라를 설치하고, 다음 자동차를 살펴본다. 다음 자동차의 시작 위치가 이전 자동차의 종료 위치(즉 카메라가 설치된 위치)보다 앞에 있으면 다음 자동차도 설치된 카메라를 만나게 된다. 그렇지 않다면 또 그 자동차의 종료 위치에 카메라를 설치하면 된다. ...

앱은 종료된 뒤에도 데이터를 유지하기 위해 파일 시스템을 사용한다. iOS, macOS 같은 애플 플랫폼에서는 APFS(Apple File System)라는 파일 시스템을 쓴다. 애플은 사용자 파일과 앱 내부 파일을 분리해서 관리하는 것을 목표로 한다. 개발자 문서에서는 파일 시스템의 목표를 다음과 같이 제시한다. 사용자 파일은 쉽게 찾을 수 있도록 한다. 앱 내부적으로 사용하는 파일은 사용자 눈에 띄지 않도록 한다. 많은 파일 시스템처럼 APFS도 디렉토리 구조를 통해 계층적으로 파일을 관리한다. 모든 디스크가 ‘단일 파일 컬렉션’을 구성한다는 점이 특징이다. 즉, 여러 디스크를 연결해도 사용자에게는 하나의 계층에 있는 것처럼 보인다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12987 풀이 n의 값이 최대 10000, s의 값이 최대 1000000의 값을 가질 수 있으므로 모든 경우의 수를 DFS로 탐색하는 것은 매우 비효율적이다. 하지만 수학적 직관을 이용해 생각해보자. 예시로 주어진 s = 9, n = 2인 경우에서도 {4, 5}가 최고의 집합이다. 만약 s = 5, n = 2인 경우에는? {2, 3}이다. s = 10, n = 2인 경우는 {5, 5} 이다. 집합 원소들이 최대한 고르게 되어있을 때 원소들의 곱이 최대가 된다는 것(= 최고의 집합이라는 것)을 알 수 있다. 그러면 이 직관을 증명해보자. ...