문제https://www.acmicpc.net/problem/3584 풀이해시 + 그래프 탐색접근법“공통 조상” 이라는 키워드만 보고서는 유니온 파인드를 생각했습니다.그러나 “가장 가까운 공통 조상(Nearest Common Ancestor)”을 구하는 문제로써 Union-Find로 구할 시 루트노드가 나오기에 다른 방식으로 접근했습니다. 두 정점의 부모 노드만 탐색하면 되었기에 일반적인 그래프 탐색을 통해서 접근했습니다. (시간복잡도↓)트리 자료구조로는 인접리스트를 활용했고, 자식 노드가 아닌 부모 노드를 탐색해야 했기에 부모를 기준으로 자식노드를 담는게 아닌 자식 노드를 기준으로 부모 노드를 담았습니다.list.get(부모).add(자식) → list.get(자식).add(부모)a와 b 노드의 공통되..

문제https://www.acmicpc.net/problem/3109풀이그리디 + DFS접근법처음 접근은 완전탐색 방식으로 접근했습니다.문제를 해석해보면 왼쪽 열에서 오른쪽 열까지 벽(x)을 제외한 나머지 통로들에 파이프를 설치하여 연결할 수 있는 길의 개수를 구하는 문제입니다.주어진 조건에 의한 행동은 3가지로 다음과 같습니다.오른쪽 상단 대각선오른쪽오른쪽 하단 대각선또한 겹치게 설치 할 순 없다는 조건이 있습니다.탐색해야하는 경우의 수는 그럼 총 N개로 시작 열의 격자칸 개수만큼 탐색을 해야합니다.또한 백트래킹을 통해서 완성된 길에 대해서는 기록을 하고, 끝까지 도달하지 못하는 경우에는 원상복귀를 시켜야 한다고 생각했습니다.위와같은 로직을 구현하기 위해서 처음 0,0에서 탐색을 시작하여 길이 완성될 ..

문제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이 되면 카운트 본격적으로 투 포인터..