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

문제 https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 풀이 3차원 방문체크를 활용한 Dijkstra 풀이 문제이해 문제를 읽고 예제를 보고 이해를 하려는데 개인적으로 상당히 난해했음. 일단 동작과정은 아래와 같음. #이라는 문에 대해서 어느 방향에서든 출발해도 상관없음. 빈칸 ‘.’에 대해 진행방향 그대로 직진만 가능. ‘!’ 칸은 거울 설치 가능한 곳으로써 해당 자리에 거울을 45도 설치 가능. 거울을 설치하게 되면 빛은 직진이 ..

문제 https://www.acmicpc.net/problem/30894 30894번: 유령의 집 탈출하기 첫째 줄에 유령의 집의 크기 $N, M$이 주어집니다.$(2≤N,M≤200)$ 둘째 줄에 유령의 집의 입구 좌표 $S_x, S_y$, 출구 좌표 $E_x, E_y$가 주어집니다.$(1≤S_x, E_x≤N, 1≤S_y, E_y≤M)$ 좌표 $(x, y)$는 위에서부터 www.acmicpc.net 풀이 3차원 방문체크를 활용한 BFS 풀이 접근법 3차원 방문배열을 활용 각 유령들은 시간에 따라 바라보는 방향이 바뀌는데 총 4가지의 서로 다른 맵이 존재함. 이 점을 활용하여 3차원 방문배열을 통해 각 방문배열마다 유령이 바라볼 수 있는 공간들에 대해 미리 전처리한 후 BFS 탐색을 수행. 소스코드 imp..

문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 풀이 파라메트릭 서치를 활용한 풀이 그리디한 접근법 A[i][j]값을 1차원 배열에 기록 후 오름차순 정렬을 통해 원하는 값 B[K]를 구하는 방식 해당 방식으로 풀이하게 될 경우 N^2만큼의 메모리가 필요할 뿐더러 시간 또한 O(N^2)만큼 걸리기 때문에 AC를 받을 수 없음 LowerBound 접근 위의 방식에서 이분탐색을 추가해서 탐색 시간을 줄여야하는데 ..