어흥

문제 링크: www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 1. 주의할 점 - 모든 TC가 진행되기 전, 변수를 초기화한다 - 트리가 이뤄지지 않은 Node는 무시한다 → 무조건 Tree가 없다고 하면 WA 2. 구현 - 트리의 특징인 노드 N개 → 간선 N-1개를 통해 MST를 떠올린다(MST도 똑같이 노드 N개, 간선 N-1개) - 트리가 많을 수 있기 때문에 MST의 방법중 하나인 유니온 파인드를 사용한다 - Par[] 함수를 통해 ..

문제 링크: www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 1. 주의할 점 - LCA 알고리즘에 대해 알고 있어야 한다 - O(NlgN)에 수행되는 알고리즘을 이해하도록 한다 2. 구현 - 모든 변에 대해 입력받은 후, havePar[] 배열을 통해 트리의 Root를 찾는다 - DFS() 함수를 통해 각 Node의 트리에서 높이를 구한다 - Make_tree() 함수를 통해 N번째 Node의 2^i번째 높..

문제 링크: www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net 1. 주의할 점 - A와 B의 범위가 10만개 + 짝을 이루기 때문에 Set혹은 Map을 사용한다 2. 구현 - sInfo 구조체를 통해 A와 B 물통에 남은 물의 짝을 저장한다 - Info 구조체를 통해 A, B, 수행한 명령 수를 저장하고 우선순위큐는 수행한 명령 수의 오름차순으로 정렬한다 - 현재 시점으로 3가지의 과정을 수행해보고 Set에 없다면..

문제 링크: www.acmicpc.net/problem/15971 15971번: 두 로봇 입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘에 대해 알고 있어야 한다 - O(NlgN)에 끝내도록 한다 2. 구현 - 같은 통로에 있을때까지 이동한다 → A에서 B까지 이동한다 - 1개의 변을 뺀다 → 빼는 1개의 변이 최단경로중 가장 값이 크면 움직인 거리가 최소가 된다 → 다익스트라 알고리즘 + 변의 최장 길이 저장 - Dist[] 배열을 통해 시작지점에서 각 지점까지의 최단거..

문제 링크: www.acmicpc.net/problem/1821 1821번: 수들의 합 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있 www.acmicpc.net 1. 주의할 점 - 파스칼의 삼각형을 통해 공식을 유추할 수 있어야 한다 2. 구현 - 수가 N이면, n-1C0부터 n-1Cn-1까지 총 N개의 수가 나온다. 해당 수들이 위에 배치될 숫자가 나타난 횟수다 - 조합 값을 저장해놓기 위해 Factorial[] 배열을 통해 0!~9!사이의 수를 저장한다 - setMul() 함수를 통해 n-1C0~n-1Cn-1값에 해당하는 값을 Mul[] 배열..

문제 링크: www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. 주의할 점 - 두 포인터 or DP를 이용하여 해결한다 2. 구현 - 모든 수가 3만 이하의 자연수다 → i~j까지의 합이 Target번호라면, j이후의 Arr[] 배열의 원소를 더할 필요가 없다(더하면 초과하므로) 2-1) 두 포인터 - L,R를 모두 인덱스 번호 0부터 시작한다. Sum을 통해 L과 R 사이에 존재하는 모든 원소의 합을 저장한다 - ..

문제 링크: www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 1. 주의할 점 - 계산 과정에서 int의 범위를 벗어날 수도 있다 2. 구현 - 서로 다른 자연수 N개 + N이 최대가 되도록 → 1+2+3+...N-1+N가 최대 N개. 즉, N*(N+1)/2 > num; result = sqrt(2*num); while(result){ if((long long)result*(result+1)

문제 링크: www.acmicpc.net/problem/2671 2671번: 잠수함식별 입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고 www.acmicpc.net 1. 주의할 점 - 오토마타 혹은 정규표현식에 대해 알고 있으면 편하다 2. 구현 - 정규표현식의 패턴을 설정한다 - 입력받은 문자열이 정규표현식의 패턴을 만족한다면 잠수함을, 아니라면 잡음을 출력한다 [C++] #include #include #include using namespace std; int main() { string str; cin>>str; string ptn = "(100+1+|..