PS 일지

문제길이 $n$인 정수 배열 $\texttt{nums}$가 주어지며, 배열의 각 원소는 $1$ 이상 $n$ 이하이다. $(n \le 10^5)$$1$ 이상 $n$ 이하의 정수 중, $\texttt{nums}$에 포함되어 있지 않은 수들을 리스트에 담아 반환해라. 추가 조건1. 리턴할 리스트를 제외하고 추가 공간 사용 x2. 시간복잡도 $O(n)$으로 해결 시도추가 조건대로 풀어보기 위해 많은 생각을 해봤다. 1. 해시셋을 써봐야겠다 -> 추가 공간 사용함2. 1부터 하나씩 배열에 있는지 볼까? -> $O(n^2)$임3. 정렬하면 공간을 안 쓰고 할 수 있을 것 같다. -> $O(n\log{n})$임4. 각 비트가 몇 번 나왔는지 볼까? -> $O(n\log{n})$이고 공간도 더 씀 한 시간 정도 고민해..

문제$0$과 $1$로만 이루어진 문자열 $s$가 주어진다.문자열의 인덱스 $i$에서 $[i+\texttt{minJump}, i+\texttt{maxJump}]$ 범위 내의 값이 $1$인 인덱스로 점프할 수 있다.단, 인덱스가 문자열의 경계를 넘어가서는 안 된다. 인덱스 $0$에서 $s.\texttt{length}-1$로 점프할 수 있는지 알아보자.풀이거꾸로 생각해보자. 인덱스 $i$로 도달할 수 있을 조건이 무엇일까?$[i-\texttt{maxJump}, i-\texttt{minJump}]$ 범위에서 도달 가능한 인덱스 $j$가 적어도 하나 있어야 한다. $\texttt{reach}[i]$를 인덱스 $i$로 도달 가능하면 true, 아니면 false라고 정의하자. 인덱스 $i$를 반복문으로 순회한다면, ..

문제정수 배열 $arr$과 $1$ 이상의 정수 $d$가 주어진다.인덱스 $i$에서 아래 조건을 만족시키면 인덱스 $j$로 점프할 수 있다.$arr[j] $\max(i-d, 0) \le j \le \min(i+d, \texttt{arr.length})$$\min(i, j) 풀이인덱스 $i$로 점프할 수 있는 조건을 해석하면 다음과 같다.인덱스 $i$의 양쪽으로, 거리 $d$ 이하의 $arr[i]$보다 큰 가장 가까운 원소거리 조건만 빠지면, 스택을 응용하는 문제로 변한다.즉, 점프를 통해 인덱스 $i$를 방문할 수 있는 곳은 좌우 각각 한 군데로 정해진다.가장 가까운 원소가 아니더라도 점프를 할 수 있지만, 그 경우에는 항상 최적이 아니다.간단한 반례를 들면, $i 거리 조건을 모두 만족한다면, $k$에서..

문제두 정수 배열 $arr1, arr2$가 있다.$1 \le i \le |arr1|, 1 \le j \le |arr2|$인 $i, j$에 대해,$arr1_i$와 $arr2_j$의 Longest Common Prefix 중 가장 큰 값을 구해보자.풀이두 배열의 크기 제한이 모두 $50,000$이기 때문에, 완전 탐색을 하면 시간 초과가 날 것 같다.배열의 원소를 정수가 아니라 문자열로 본다면, 문자열 집합에서 특정 문자열을 검색하는 문제로 바꿀 수 있다.문자열 집합에서 검색을 지원하는 자료 구조인 트라이를 사용해보자.$arr1$의 모든 원소를 트라이에 삽입해놓고, $arr2$의 원소를 하나씩 트라이에서 검색한다.검색할 때는, 검색 문자열과 일치하는 최대 깊이까지 내려가면 된다.코드class TrieNode..

문제정렬된 두 정수 배열 $nums1$, $nums2$ 가 주어진다.두 배열의 중앙값을 $\log$ 시간복잡도로 구해보자.풀이문제를 살짝 변형해서, 두 배열의 $k$번째 원소를 구해보자.$k$번째 원소를 어떻게 구할까?아직은 모르지만, $k$번째 원소의 값을 $v$라고 하자.어떤 값 $x$가 $v$보다 작다면 두 배열에서 인덱스가 $k$ 미만이다.따라서 $x$를 매개 변수로 두고 이분 탐색을 진행하며 가능한 $x$의 범위를 빠르게 좁혀나갈 수 있다.두 배열에서 어떤 값 $x$의 인덱스는 이분 탐색으로 빠르게 구할 수 있다.코드class Solution { public int upperBound(int[] arr, int x) { int s = 0, e = arr.length, m = (..

BOJ의 서비스 종료 소식을 접하고 많은 생각이 들었다. 어떤 분야에 이렇게 열정을 쏟아서 공부해본 적이 처음이었다.문제 하나를 풀 때마다 느껴지는 성취감 자체가 당시의 나에겐 가장 큰 즐거움이었다.알고리즘 문제 풀이에 재미를 느끼게 해줬다는 것 외에도 많은 것을 줬던 것 같다. 처음 시작할 때는 스터디에 들어가서 열심히 배우는 입장이었지만, 나중에는 내가 스터디의 멘토로서 지식을 공유할 수 있었다. 같이 팀 대회에 출전하여 머리도 꽁꽁 싸매보고, 이틀 밤낮에 걸쳐가며 하나만 붙잡고 풀어도 보고, 문제가 잘 안 풀릴 때는 짜증도 내보고, 대회에 직접 문제를 출제도 해봤다. 내가 처음 냈던 문제가 처음 풀렸을 때의 기분은 아직도 잊을 수 없다. 여러 활동을 한 덕분에 감사하게도 그 안에서 다양한 사람들을..

문제https://www.acmicpc.net/problem/5214$N$개의 역과 $M$개의 하이퍼튜브가 존재하며, 하이퍼튜브 하나는 역 $K$개를 서로 연결한다.$1$번 역에서 $N$번 역으로 가는데 방문하는 최소 역의 수를 구해보자. 풀이하나의 하이퍼튜브가 연결하는 $K$개의 역을 서로 모두 이어주게 된다면, 간선이 $\dfrac{K(K-1)}{2}$개 생기게 된다.아래는 2, 4, 5, 7, 8, 9번 역을 연결하는 하이퍼튜브를 그래프에 추가시킨 그림이다.이 방식대로 그래프를 구성한다면 전체 간선은 $O(MK^2)$만큼 생기게 되고, 이는 메모리나 시간의 제약으로 인해 불가능한 풀이가 된다.하이퍼튜브 하나를 그래프의 새로운 가상의 정점으로 본다면 어떨까?하나의 하이퍼튜브로 인해 추가되는 간선은 $..

시작하기 전에그래프에서 최단 경로를 찾는 알고리즘은 크게 세 가지가 존재한다고 알고 있었다. Dijkstra- 시작점이 존재해야 함. 그래프의 간선 가중치가 음이 아닌 정수일 때만 가능Floyd-Warshall- 모든 정점 쌍 사이의 최단 경로를 구할 때 사용, 음수 가중치 및 음의 사이클 판별 가능Bellman-Ford- 시작점이 존재해야 함. 음수 가중치 및 음의 사이클 판별 가능 Claude 선생님과 함께 알고리즘 복습을 하던 중에 SPFA라는 것을 접하게 되었다.SPFA 또한 그래프에서 최단 경로를 찾는 알고리즘이며, 이를 알기 위해선 Bellman-Ford를 먼저 알아야 한다.여기서는 Bellman-Ford의 원리만 간단히 설명하겠다.Bellman-Ford정점이 $N$개인 그래프의 어떤 최단 경..

문제https://www.acmicpc.net/problem/9376두 명의 죄수가 $H \times W$ 크기의 감옥에 갇혀 있다.감옥을 구성하는 격자 칸은 빈 칸('.'), 벽('*'), 문('#'), 죄수('$')로 이루어져 있다.두 죄수가 모두 감옥의 바깥으로 탈출하기 위해 열어야 하는 문의 최소 개수를 구하는 문제이다.풀이문의 개수가 충분히 적다면 문의 열림/닫힘 상태를 관리하는 비트마스킹 + BFS로 해결할 수 있으나, 이 문제에서는 먹히지 않는다. 답이 나올 수 있는 경우를 두 가지로 나눠보았다.1. 두 명의 죄수가 만나지 않고 각각 탈출하는 경우각 죄수를 시작점으로 두고 다익스트라 혹은 0-1 BFS로 탈출하는 최단 경로를 구한다.2. 두 명의 죄수가 만나서 같이 탈출하는 경우첫 번째 죄수..

🔗 백준 2042번 - 구간 합 구하기 문제를 보자. 세그먼트 트리를 입문하면서 처음 만나게 되는 문제로 유명하다.여기서는 세그먼트 트리를 사용하지 않는, $O(M \sqrt{N})$ 풀이를 소개하려 한다.아이디어원래 세그먼트 트리에선, 구간을 반씩 쪼개어 총 $O(N\log{N})$개의 구간 합을 관리하는 아이디어를 사용한다.구간을 쪼갠다는 아이디어 자체는 같다. 여기서는 길이가 동일한 구간을 $O(\sqrt{N})$개 만들어서 각 구간의 길이 또한 $O(\sqrt{N})$이 되도록 관리한다.보통 구간 하나하나를 버킷이라 칭한다. 적용각 버킷별로 합을 저장하는 배열을 만들어 놓자.만약 위 그림처럼 특정 구간의 합을 구하려고 할 때,초록색 부분만 하나하나 직접 더해주고 파란색 부분은 미리 구해놓은 ..