https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 유니온 파인드 문제를 풀면서 로직까지 다 짜고서, 채점을 했는데 틀렸다고 나왔다... 그래서 반례가 있나해서 질문게시판에서 반례들 찾아서 다 넣어보고, 로직이 잘못됐나해서 다시 확인하고 다른 사람 코드도 보고... 정답 코드도 찾아서 봤다... 근데 전혀 내 코드에 틀린 로직은 없었다... 그래서 뭐가 문제지 하면서 억까당하다가 범위가 잘못됐나..깊이 저장이 ..

https://www.acmicpc.net/problem/17352 union_root(1,3)-> parent = [0,2,3,3,4] 부모 노드를 정의한다. find_root(1) -> [0, 3, 3, 3, 4] find_root(2) -> [0, 3, 3, 3, 4]으로 정의되어서 1과 4의 root가 달라서 1 4를 출력한다. public void union_root(int x, int y){ x=find_root(x); y=find_root(y); if(x!=y){ parent[x]=y; } } public int find_root(int x){ if(x==parent[x]) return x; return parent[x]=find_root(parent[x]); } 그래서 union_root는..

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 이 문제는 세그먼트 트리를 구현하면 된다. 트리를 구간 곱으로 초기화하고, 리프노드를 바꿔야 할 때는 노드 갱신 메서드를 사용해서 바꿔서 계산해준다. 구간 곱을 계산하는 메서드를 구현하는 과정에서 처음에 구하려는 구간 곱의 범위 밖에 있는 경우에 리턴 값을 0으로 해서 구간 곱이 모두 0이 되어서 안되었다. 그래서 이유가 뭔가 생각했는..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이 문제도 운동(1956)문제와 같은 플로이드 워셜을 이용한 문제이다. 로직은 1956과 거의 똑같기 때문에 간단하게 동작 방식만을 설명하자면, 시작 지점과 도착 지점 사이의 중간지점 즉, 거쳐가는 지점이 있다고 가정하고, 최단거리를 구하는 것이다. 다익스트라가 특정 정점에서 특정 정점으로 가는 최단거리였다면 그걸 전체 정점에서 전체 정점으로 가는 최단거리라고 생각하면 된다. 정답 코드는 아래와 ..

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 다익스트라 알고리즘으로 특정 정점에서 다른 특정 정점까지의 최단거리를 확인하였다. 그렇다면 모든 정점에서 모든 정점으로 가는 최단거리는 어떻게 구할까? 이때 사용하는 알고리즘이 플로이드 워셜이다. 플로이드 워셜은 모든 정점에 대해서 모든 정점으로 가는 최단거리를 중간 지점 노드를 사용하여 계산한다. 음의 간선 사이클이 존재하지 않는다면 음의 가중치를 가진 경우에도..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 이 문제는 세그먼트트리를 이용하는 문제이다. 세크먼트 트리는 주어진 쿼리를 빠르게 처리하기 위한 자료구조로 여기서는 구간합을 구하는 용도로 사용되었다. 예를들어 1~10까지의 수가 있고 이중에서 몇몇 값들을 바꾸어서 구간의 합을 구하는 경우에 아래의 그림과 같은 세그트리를 만들 수 있다. 각각의 노드에는 구간의 합을 저장하여 필요에 따라 ..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 생각하기 너무 힘들었다.. 그래서 다른 사람의 해결책을 보면서 원리를 이해했다. 이 문제에서의 핵심은 메모리를 관리하는 것이다. 그래서 동전의 사용을 dp로 저장하였다. 동작 방식은 먼저 0부터 k까지의 수를 만드는 과정을 기록할 배열을 둔다고 생각한다. 예를 들어 n=3 k=10이고 1,2,5가 동전으로 주어졌다고 생각해보자.(설명에서 헷갈리는 것을 줄이기 위해 동전을 one,two,..

https://www.acmicpc.net/problem/24313 24313번: 알고리즘 수업 - 점근적 표기 1 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다. www.acmicpc.net 이 문제는 점근적 표기법에 대한 문제이다. 시간복잡도의 빅오 함수를 정의하는 것인데, 처음에는 너무 쉽다 생각해서 바로 구현하여 돌렸는데, 91퍼에서 틀려서 뭐가 문제인가 생각하게 만든 문제이다. 이유는 생각보다 간단했다. 내가 생각한 로직은 g(n0)>=f(n0)이 성립하면 된다고 생각했다. 하지만 여기서 생각할 것은 f(n)=fn && a1