문제 링크 우주선이 $i$번째로 이동한 거리를 $k{i}$라고 했을 때, 수열의 첫째 항과 마지막 항이 1이고 $k{i+1} = k{i} - 1$ 또는 $k{i}$ 또는 $k_{i} + 1$가 되는 상황에서 최소 이동 횟수를 묻는 문제이다! 문제를 푸는 핵심 첫 번째는 바로 $k{i}$의 최댓값에 대해 생각하는 것이다. 수열 $k{i}$는 이웃하는 항과의 차이가 항상 $0$ 또는 $1$이어야 하므로, 다음과 같은 특징이 성립한다. > $k_{i}$의 최댓값이 $n$이라면, 우주선은 적어도 $1 + 2 + \cdots + n + (n-1) + (n-2) + \cdots + 1 = n^2$만큼의 거리를 이동했어야 한다! 따라서, 가능한 $n$의 최댓값은 $\sqrt{y - x}$ 의 정수 부분이 될 것이다. 한편, 위와 같이 우주선이 $(2n - 1)$번의 움직임으로 $n^2$만큼의 거리를 이동하

알고리즘 분류에 애드 혹이라는 분류가 있어, 궁금해서 풀어 본 문제였다! 처음에는 애드 혹도 알고리즘의 종류인 줄 알았는데, 내가 아는 의미가 아니라 문제를 해결하기 위해 알려진 알고리즘을 적용하는 것이 아니라 정말 '알아서 생각해서 풀어야 하는 문제'를 일컫는 말이었다. 문제는 1부터 $n$까지의 수열을 두 번 뒤집었을 때, 이를 원상복구시키려면 어떻게 뒤집어야 하는지를 묻는다. 알려진 공식이나 방법을 적용할 수 없어서, 우선 여러 개의 예시를 생성하는 방식으로 접근하였다! 그러다 보니, 수열을 뒤집으면 뒤집힌 구간 내부에 있는 숫자들은 인접한 숫자와의 차이가 1 또는 -1이지만 그 경계에 있는 숫자는 인접한 숫자와의 차이가 다르기 때문에, 이 점들을 표시하기로 하였다! 그런데 처음

문제 링크 예전에 책에서 얼핏 본 것 같은 문제라 생각보다 간단하게 해결할 수 있었다! 위 사진과 같이 주어진 히스토그램을 반으로 나눈 후, 아래의 3가지 경우로 나누어서 분할 정복을 이용하여 문제를 해결하면 된다. > 1. 정답이 되는 직사각형이 왼쪽 부분에만 있다. > 2. 정답이 되는 직사각형이 오른쪽 부분에만 있다. > 3. 정답이 되는 직사각형이 왼쪽과 오른쪽에 걸쳐 있다. $i$번 직사각형부터 $j$번 직사각형까지 고려한 답을 $solve(i, j)$라 하면, $mid = \lfloor\frac{i + j}{2}\rfloor$라고 하였을 때, 1번과 2번의 경우는 $solve(i, mid)$와 $s

문제 링크 아이디어 자체는, 그래프의 SCC(Strongly connected components)를 찾아서 전체 개수를 저장하고 각각의 SCC를 정점으로 갖는 새로운 그래프를 만들어서 해결하면 되는 문제일 것 같다는 생각이 들었다! SCC 찾기 그래프의 SCC를 찾는 방법은 이 블로그를 참고했는데, 나중에 템플릿으로 만들어 두면 좋을 것 같다! 아이디어는 하나의 정점에 대해 DFS를 하되, 방문한 순서를 저장하고 스택에 넣으면서, 방문한 정점이 이미 방문했으나 SCC로 분류되지 않은 정점이면 cycle을 발견한 것이므로 cycle에서 최초로 방문

문제 링크 LIS(Longest Increasing Subsequence) 문제는 다이나믹 프로그래밍으로 해결할 수 있는 유명한 문제들 중 하나로, 다이나믹 프로그래밍을 이용한다면 $dp(i)$를 $i$번째 원소를 마지막 값으로 갖는 LIS의 길이로 정의한 뒤 $dp(n)$을 구해주면 되는데, 이때 $dp(i)$를 구하기 위해 $i$번째 원소 앞에 있는 배열의 원소와 $dp(j)$ 값을 스캔해야 하므로 시간 복잡도는 $O(n^2)$가 된다. 하지만 이 문제는 수열의 원소 개수가 최대 1,000,000개이므로 이 알고리즘을 사용한다면 시간 초과가 발생할 수밖에 없다. 이 문제를 $O(n log n)$의 시간 복잡도로 해결하는 알고리즘이 존재하는데, 바로 수열에 있는 수들을 각각 검사하면서, LIS가 될 수 있는 후보 수열을 저장하는 배열을 업데이트하는 방식으로 동작한다. 주어진 배열을 $A$, LIS가 될

문제 링크 동전 던지기의 결과를 알려주고, 동전이 앞면이 나올 확률에 대해 물어보는 문제라서 베이즈 정리를 활용할 수 있을 것 같았다! 결과적으로 베이즈 정리를 활용하여 확률분포를 구하고 적분을 통해 계산하는 것은 시간 초과가 나서 실패했지만, 그래도 계산 과정이 맞고 오랜만에 베이즈 정리 문제를 풀어봤으니까 이것도 써 봐야겠다! 베이즈 정리를 이용해서 확률 분포 구하기(시간 초과) 베이즈 정리의 모습인데, 여기서 동전의 확률 $p$와 $q$는 연속확률변수이므로 확률밀도함수에 대해서 쓰면 아래와 같다! 먼저 사건 $A$를 동전을 $n1$번 던질 때 앞면이 $m1$번 나온 사건으로 정의하고, 동전 1의 사전 확률 분포는

문제 링크 간단한 DP 문제로, 어떤 수열이 주어졌을 때 $i$번째부터 $j$번째까지의 부분 수열이 팰린드롬인지 찾는 것인데 문제가 여러 개 주어진다! 부분 수열의 크기가 1 이하일 때는 항상 팰린드롬이 되고, 큰 입력에 대해서는 $i$를 하나 늘리고 $j$를 하나 줄이면서 그 결과를 2차원 배열에 저장하면 쉽게 해결할 수 있다.

문제 링크 DP만 쓰면 되는 문제인데, 난이도가 플래티넘 V로 나에게는 어려운 편인 문제였다! 당연히 안 되겠지만, 완전 탐색으로 푼다면 결국 각각의 사건에 대해 1번 경찰차가 출동하면 되는지, 2번 경찰차가 출동하면 되는지를 판단하면 되니까 최대 $2^{1000}$가지의 경우가 존재할 것이다. 여기서 중복된 계산이 여러 번 나오면 DP를 적용하면 되는데, 처음에는 최적 부분 구조(optimal substructure)가 성립하는지에 대한 의심을 해 보았다! > $w$개의 사건을 해결하는 최적의 선택을 $A$라고 했을 때, 여기서 새로운 사건이 추가되었을 때 $(w+1)$개의 사건을 해결하는 최적의 경로는 $A$를 포함하는가? 이것이 사실이라면 새로운 사건이 추가될 때마다, 1번 경찰차 혹은 2번 경찰차가 출동하는 두 가지 경우만 고려하면 되기 때문에 매우 쉽게 문제를 풀 수 있겠지만 그렇지 않다. !

문제 링크 TSP(Traveling Salesman Problem)이라고 불리는 유명한 문제이다. NP-Complete의 대표적 문제로 아직 다항 시간 내에 해결할 수 있는 알고리즘이 없다! 모든 경로를 순열로 만들어 일일이 탐색한다면 $O(n!)$의 시간이 소요되는데 이 문제에서는 시간 초과가 발생한다. 다이나믹 프로그래밍을 이용하면 시간 복잡도를 줄일 수 있다. 정점 집합 $V$의 부분집합 $S$와 정점 $j(j \neq 0)$에 대하여, $C(S, i)$를 다음과 같이 정의하자. > $C(S, j)$ : 집합 $S$의 정점을 한 번씩 모두 방문하고 정점 $i$에서 종료되는 경로의 최소 비용 이때 구하고자 하는 답은 다음과 같다. > $answer = \displaystyle\min_{i \in V, i \neq 0 }{[C(V, i) + dist(i, 0)]}$ 초깃값은 다음과 같이 설정할 수 있

앞으로 여기에 올릴 템플릿 코드는 Github에서도 볼 수 있고, 매우 중요한 내용이 아니면 최신 코드는 이 블로그가 아니라 Github에서만 유지할 예정이다! 그래프를 탐색하는 가장 기초적인 알고리즘인 DFS와 BFS이다! DFS는 보통 재귀 함수로 구현되고, BFS는 보통 Queue 자료 구조를 통해서 구현되고, 이번에는 DFS와 BFS를 크게 4가지 경우로 나누어서 템플릿을 만들어 보았다. 내가 주로 지키려고 노력하는 코딩 스타일에 영어로 Comment를 달아놓았다...! > 1. 그래프의 세부 구현이 정해지지 않은 경우 > 2. 그래프의 인접 행렬(adjacency matrix)이 **2D arr

알고리즘 오픈채팅방에 들어가기 최근에 운동도 하고 아르바이트도 해 보고 여러 가지 바쁜 일들이 많아서인지 오랜만에 블로그 글을 쓰는 것 같다! 여느 때처럼 집에서 뒹굴거리며 시간 날 때 가끔 알고리즘 문제 풀이를 하던 나는 어느 날 학교 에브리타임을 보다가 이런 글을 보게 된다. 군 복무를 마치고 다음 학기까지 집에서 쉬고 있던 나는 공부를 해야겠다는 생각을 해도 지금이 아니면 쉴 시간이 없다는 생각이 앞섰다. 지금이 아니면 쉴 시간이 없을 거라는 생각에, 놀 수 있을 때 놀자는 생각에는 변함이 없지만 이 글을 보고 매일 1문제 정도라면 큰 부담 없이 참여할 수 있을 거라는 생각에 쪽지를 보내고 오픈채팅방에 들어갔다! ![](https://velog.velcdn.com/images/smilelee