문제https://www.acmicpc.net/problem/1967 풀이깊이 우선 탐색(DFS) 활용한 풀이접근법각 노드에서 순회(dfs)방문체크를 통해 한쪽 깊이로만 탐색더 이상 탐색이 불가능한 노드에 도착 시 최대값 비교 및 갱신문제에서 “트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우” 라는 문맥을 통해서 두 노드 사이를 순회하여 제일 높은 가중치를 구하면 되겠구나 라는 생각을 함. 해당 문제를 풀며 조금 생각이 필요했던 부분은 특정한 노드에서 부모노드로 순회를 하게되는 경우였음.이번에 접근한 방식으로는 클래스 배열을 활용하여 부모노드에 대해 기록을 한 뒤 순회를 하도록 구현하였음. (자세한 부분은 아래코드를 참조)소스코드import java.io.*;import..

문제 https://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 풀이 투 포인터를 활용 Solving 문제에서 주어지는 수열에서 구간합이 M이 되는 조합의 경우의 수를 구하는 문제입니다. 그리디하게 접근하여 풀이를 하게되면 2중 for문으로 시간복잡도가 O(N^2)이 됩니다. 그리디한 풀이는 다음과 같습니다. 각 수열의 i번째 원소에서부터 i+1번 이후의 수열을 누적 누적합이 M이 되면 카운트 본격적으로 투 포인터..

문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 누적합 및 자료구조를 활용한 풀이 접근법 A수열과 B수열에서 나올 수 있는 모든 부 배열을 누적합을 활용하여 구함 Map 자료구조를 활용하여 해당 누적합 값이 기존에 들어가있다면 value증가, 없다면 put A의 부 배열 개수만큼 반복문을 돌면서 목표값 T - A[i](부 배열 원소) 값이 B 부 배열 M..

문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이 Dijkstra를 활용한 풀이 접근법 조건 - 첫번째 컴퓨터는 슈퍼컴퓨터로써 반드시 복구해야합니다. - 슈퍼 컴퓨터로부터 나머지 N-1개의 컴퓨터까지 최단 경로로 통신이 가능해야합니다. - 양방향 그래프 풀이 간단한 데이크스트라를 통해 슈퍼 컴퓨터를 시작노드로 나머지 노드까지의 최단경로를 우선순위 큐를 통해 탐색. 탐색하는 과정에서 방문체크를 같이 진행. 이전..