문제https://www.acmicpc.net/problem/3020 풀이누적합을 활용한 풀이접근법N이 최대 200,000, H가 최대 500,000으로 들어오는 것을 조심해야 한다.단순히 O(NH)로 풀게 될 경우 시간초과가 발생하기 때문에 완전탐색 쪽으로는 생각하지 않았다. 그러면 어떻게 각 구간에 대해 효율적으로 탐색할 수 있을까? 처음에 떠올랐던 건 각 구간 별로 입력을 받을 때마다 갱신하면 되지 않을까였다.N개의 입력에서 갱신하는 방법에 대해 생각한 결과 각 구간 별로 누적합 원리를 활용해서 종유석 | 석순 각각에 대해 카운팅 해준 다음, 누적합을 구하는 방식으로 풀이했다.결과에 대해서는 i구간에 대해 종유석[i] + 석순[i]의 합이 개똥벌레가 부숴야하는 장애물의 개수이며, 최소값을 구한 후 ..

문제https://www.acmicpc.net/problem/1339 풀이자료구조를 활용한 그리디 풀이첫번째 접근법 (오답)다음과 같은 우선순위를 통해서 알파벳에 대한 값을 메겼습니다.자리수가 높은 알파벳 우선같은 자리수라면 개수에 따라서반례2ABBB----wrong : 186ans : 188해당 접근으로는 바로 뒷자리수에 나오는 알파벳에 따라 잘못된 결과가 측정될 수 있었습니다. 두번째 접근법그렇다면 위와 같은 반례에 대해서 어떻게 풀이를 해야할까요?처음에는 단순히 바로 뒤에 나오는 각각의 자리수에 대해서 알파벳의 개수를 측정하고, 비교하려 했는데요. 이렇게 될 경우 로직이 굉장히 복잡해지고 어떻게 코드를 작성해야할지 모르겠더라구요.코드를 아예 지우고 다시 생각을 해본 결과 다음과 같은 로직을 생각할 ..

문제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도 설치 가능. 거울을 설치하게 되면 빛은 직진이 ..