TheoryWhat is Inversion??한국어로는 역전이라고도 한다.배열 $A=Array$ 에 대해 $i, j$ 는 $0 역전은 아래를 만족함.$A[i] 다시말해, Number of Inversion 은 이 역전의 개수를 세는 문제이다.How to count Number of Inversion?필자는 Merge sort로 구현하는 아이디어를 떠올렸다. 정렬하는 과정에서 카운팅 하는 것이 쉽다는 힌트를 보고 왜 그런가 정말 오래 고민했다.아무튼, Merge Sort를 할 때는 항상 아래의 과정을 따른다.각 요소를 합치는 과정에서 가장 작은것부터 비교가 이루어지며, $Array2$에서 이를 활용해 만약 $Array1$의 다음으로 선택할 가장 작은 요소가, $Array2$의 그것보다 크다면, $Array..
![[LCA] 최소 공통 조상 알고리즘](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdna%2FBc5yb%2FbtsPdKz5CCb%2FAAAAAAAAAAAAAAAAAAAAAAwTL2kVVENIyoW0Q-r_DiA_M2HvVDvKDIF4nLqGDf7X%2Fimg.png%3Fcredential%3DyqXZFxpELC7KVnFOS48ylbz2pIh7yKj8%26expires%3D1772290799%26allow_ip%3D%26allow_referer%3D%26signature%3DbpGpOvBvVOW90dPCmFd88tGP9%252BM%253D)
Lowest Common Ancestor트리에서 두 정점이 주어질 때 가장 가까운 공통 조상을 찾는 알고리즘시스템, 생물학 등 다양한 분야에서 활용될 수 있으며, 계층이 있는 구조에서 갈래를 찾는데에 사용이 될 수 있다.알고리즘처음 생각한 방법계층 구조가 확실하다면 해당 정점들의 정보를 통해 루트로 각각 한칸씩 올라간다.이후 두 정점이 한 칸씩 올라가며 방문한 노드에 다시 방문한 경우 그 정점이 최소 공통 조상이라고 판단이 방법은 O(N)의 시간 복잡도로 한 번 실행할 때에 나쁘지 않은 방법으로 보였다.푼 문제 : 3584번가장 가까운 최소 공통 조상다만 LCA 라는 이름의 문제로 넘어가니 위에서 푼 문제를 쿼리처럼 여러번 사용해야해서 시간 복잡도 O(N) 알고리즘으로는 해결할 수 없었다.최적화된 방법시..
문제치즈가 있을 때 공기와 닿은 치즈는 녹아서 사라진다.치즈의 맵이 주어질 때 사라지는데 걸리는 시간과 사라지기 직전에 있던 치즈의 숫자를 출력하라.Solution최외곽은 항상 공기라고 볼 수 있기 때문에 최외곽에서 그래프 탐색 알고리즘(BFS/DFS)를 돌려 공기를 구하고 치즈가 공기와 닿았는지 직접적으로 확인하면 되는 간단한 문제였다.solution code#include #include #include #include #include using namespace std;int n,m;int map[101][101];bool visit[101][101];int dx[] = {-1,1,0,0};int dy[] = {0,0,-1,1};void init(){ for(int i=0; i> n >> m;..
문제길이가 N인 수열이 주어질때 수열의 합을 구하려 한다.아래의 조건에 따라 수열을 변경할 수 있다.어떤 위치에 있는 숫자든 2개를 골라 수를 묶을 수 있다.묶은 수는 곱하여 합을 구하게 된다.예) 0 1 4 3 2 5 -> 4와 5를 묶은 경우 합을 구하면 0 + 1 + 2 + 3 + (4*5) 가 된다.이 때 이 묶기 연산을 적절히 사용하여 최대의 합을 구하여라.입력 : 수열의 크기 N 이후 N개의 줄에 -1000~ 1000 사이의 값출력 : 2^31이 넘지않는 답Solution그냥 그리디 하게 경우의 수를 나누면 쉽게 해결되는 문제이다.아래의 경우의 수로 나누어 연산을 진행하였다.2이상의 양수 (곱하면 무조건 이득)음수 ( 곱하면 양수가 되므로 무조건 이득)0 (0이 존재하면 남는 음수를 제거할 수..
문제두 문자열 A와 B 가 주어질 때 좋은 문자열을 유지하며 A에서 B로 아래의 규칙을 따르며 변환할 수 있을까?좋은 문자열의 규칙 1. ab 는 좋은 문자열이다. 2. 만약 문자열 [S]가 좋은 문자열이라면, 오른쪽과 왼쪽 끝에 각각 a와 b를 추가한 문자열 a[S]b 또한 좋은 문자열이다. 3. 만약 문자열 [S]와 [T]가 좋은 문자열이라면 이들을 붙여 쓴 [S][T] 또한 좋은 문자열이다.변환 규칙은 간단하다. 인접한 두 문자만을 교환할 수 있다.ex) aabb -> abab (O) aabb -> baba (X)문자열의 길이는 최대 10만이다. SolA와 B 모두 좋은 문자열임이 확신되어 있고 규칙 상 A와 B의 부분 문자열들 또한 좋은 문자열을 유지해 어떻게 변환해도 좋은 ..