컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 해결 알고리즘 LCA 기초 문제 소스 코드 #include using namespace std; const int MAX = 50000; vector tree[MAX+1]; int parent[MAX+1], depth[MAX+1]; bool visited[MAX+1]; void set_tree(int cur, int d){ visited[cur] = true; depth[cur] = d..

https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net 문제 해결 알고리즘 세그먼트 트리 기본 문제 소스 코드 #include using namespace std; const int MAX = 100000; int arr[MAX+1], tree[4*MAX+1]; int init(int start, int end, int node){ if(start == end) retur..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 문제 해결 알고리즘 플로이드 와샬 응용 문제 플로이드 와샬로 각 노드에서 노드로 가는 배열들을 모두 구한 후 그 배열에서 INF값이 아닌 값들의 개수를 따로 구해주어서 그 값보다 작거나 같은 값의 개수가 그 값과 같다면 자신의 키가 몇 번째인지 알 수있는 학생이다. 소스 코드 #include using namespace std; const int INF = 1e9; int N, M; int arr[..

Union-find란? 합집합을 찾는 알고리즘이다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해 두 노드를 같은 집합으로 합치거나, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별해주는 알고리즘 크루스칼 알고리즘에도 쓰이는 중요한 그래프 알고리즘 알고리즘 사례 위와 같이 모두 떨어져있는 집합 각각 6개씩 있다고 가정하자. 각각의 부모노드는 자기자신이다. 여기서 2와 3를 연결했다고 해보자. (이 때 i값이 작은쪽이 부모노드가 된다고 가정한다 보통 작은 쪽이 부모노드가 되는 게 일반적) 이제 1과 2를 연결해보자. 위의 표를 보면 알 수 있듯이 합집합으로 되어있는 노드들의 부모노드 값들이 전부 조상노드로 향하는 게 아니라는 걸 알 수 있다. 그렇기 때문에 합집합으로 다 연결을 했다고..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 해결 알고리즘 Union find 문제 parent 배열이 무조건 그 노드의 조상노드를 가리키는 게 아니기 때문에 조상 노드 비교 해줄 때는 find_parent 함수를 써줘야한다. 소스 코드 #include using namespace std; int n, m; int parent[1000001]; int find_parent(int x){ if(x..

https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍으로 푸는 문제 next_permutation으로 일일히 순서대로 구하면 K가 최대 10억이기 때문에 시간초과를 받는다. a문자의 개수와, z문자의 개수로 이중배열을 선언해준다. dp[a문자의 개수][z문자의 개수] = dp[a문자의 개수 - 1][z문자의 개수] + dp[a문자의 개수][z문자의 개수-1] 위의 식대로 dp배열을 만들어주고 K가 a가 하나 적은 dp값보..

https://www.acmicpc.net/problem/21757 21757번: 나누기 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어 www.acmicpc.net 문제 해결 알고리즘 수열의 누적합 배열을 만들어 준 후에 수열의 총합을 구하고, 총합이 0인 경우와 아닌 경우 두 가지로 나눠서 풀어줘야한다. 0인 경우는 마지막 0빼고 나머지 0의 개수에서 3개를 뽑는 조합으로 개수를 구해주면된다. 0이 아닌 경우는 다이나믹 프로그래밍을 이용해서 풀어줄 수 있는데 총합에서 4를 나누면 공차가 나오고 그 공차대로 늘어나는 길이 4의..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 해결 알고리즘 벨만 포드 알고리즘 음의 사이클의 존재 여부를 판단하는 문제. 출발점이 어디든 음의 사이클 존재만 판단하면 되므로 한 번만 벨만 포드 알고리즘을 돌리면 된다. (굳이 모든 출발점에서 음의 사이클 존재 여부 판단할 필요 X, 시간 초과남) if(d[cur_node] != INF && d[next_node] > d[cur_node] + cost) 보통의 벨만 포드 알고..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 문제 해결 알고리즘 벨만 포드 알고리즘 INF값은 충분히 크게 잡아주어야한다. 오버 플로우가 나기 때문에 int 대신 long long 자료형을 써주어야한다. 소스 코드 #include #define ll long long using namespace std; const ll INF = 1e9; const int MAX = 6001; l..

https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 www.acmicpc.net 문제 해결 알고리즘 세그먼트 트리에 인덱스 값을 넣는데 이 때, 인덱스에 해당하는 배열 값과 항상 비교해서 작은 배열 값의 인덱스 값을 리턴해준다. 소스 코드 #include using namespace std; const int MAX = 100000; int arr[MAX+1], tree[4*MAX+1]; int ..