백준 2842번 : 집배원 한상덕 [Java]

https://www.acmicpc.net/problem/2842 문제 탐색하기평범한 bfs문제인 것처럼 보이긴 하지만 플래 4에 들어가 있는 이유가 있을 것이다. 얼핏 봐서는 최소힙 (우선순위큐)와 같은 것을 사용해서 방문할 곳 중 높이가 현재 최대 최소에 근접한 것을 뽑으면 될 것 같지만 그렇지 않다. 이미 방문한 노드의 다음 노드를 실시간으로 높이차를 계산해서 최적해를 보장할 방법이 없다. 이미 최소힙에 들어있는 것을 실시간으로 재조정 할 수가 없다. 결국에는 모든 높이의 구간을 탐색해봐야 하는 것이다. 그러면 어떤 식으로 탐색해 볼 수 있을까? 일단 너비 우선 탐색을 통해서 모든 K를 방문하는 경로를 계산 하는 방법은 맞다. 여기서 중요한 것은 높이차를 어디까지 허용할 지 계산 하는 방법인데, 이..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 23.
• textsms

백준 12014번 : 주식 [Java]

https://www.acmicpc.net/problem/12014 문제 탐색하기문제에서는 아래와 같이 설명이 장황하게 되어있지만 결국 원하는 건 가장 긴 증가하는 수열이다. 주식을 살 때마다 맨 처음을 제외하고는 바로 직전에 주식을 샀을 때보다 가격이 올라갔을 때만 사기로 했다. 가장 긴 증가하는 수열을 구하는 방법은 두 가지 시간 복잡도로 나눌 수 있는데, 모든 수열을 찾는 O(N^2)이 걸리는 방법과, 하나의 리스트를 사용하여 인덱스를 찾아가며 교환하는 O(NlogN)이 걸리는 방법이 있다. 문제의 최대 입력을 생각해보면 100 * 10000 * 100 = 100억 이므로 시간 제한 5초안에 통과하려면 무조건 O(NlogN)이 걸리는 방법을 사용해야 한다.  O(NlogN)은 이분탐색을 통해서 구하..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 22.
• textsms

백준 1938번 : 통나무 옮기기 [Java]

https://www.acmicpc.net/problem/1938문제 탐색하기전형적인 bfs 문제에서 약간의 변형을 한 느낌의 문제이다. 이전에 프로그래머스에서도 비슷한 카카오 문제를 본적이 있는 것 같은데 그 때의 경험을 되살려보며 생각해보자. 길이가 3인 통나무를 주어진 방식대로 옮기려면 동시에 3칸을 고려해야한다. 또한 방향이 가로 또는 세로로 들어갈 수 있으므로 2가지 방향에 대한 방문을 기록해두고 너비 우선 탐색을 진행하면 답을 구할 수 있을 것이다. 회전은 중심축을 기준으로 현재 통나무가 없는 방향들을 확인하면 되는데, 이 때 중간에 하나라도 다른 나무이거나 범위를 벗어난것이 있다면 회전이 불가하니 알아두자. 답을 출력할 때는 원본 지도에 나와 있는 도착지점의 좌표와 통나무의 방향을 미리 계산..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 21.
• textsms

백준 2515번 : 전시장 [Java]

https://www.acmicpc.net/problem/2515 문제 탐색하기문제는 전시대에 그림을 폭을 겹쳐서 놓는다. 이때 관람자가 보이는 그림의 폭이 S 이상인 그림만 살 수 있고 이 때 모든 그림의 값의 최대 합을 구하는게 목표다. 처음에 들여다 봤을 때는 모두 탐색하는게 답이지 않을까? 라고 생각할 수 있는데 그렇지 않다. 입력을 보게되면 N이 최대 30만이므로 O(N ^ 2)으로 탐색하게 되면 최대 900억번 반복 탐색해야하므로 1초의 시간 제한 안에 들어올 수 없을 것이다. 그래서 우리는 다른 방법을 찾아야만 한다. 입력이 크므로 시간 복잡도를 낮춰서 최소 한번은 N을 탐색하더라도 나머지 숫자를 log를 사용하게 만들던 해야 시간 복잡도를 통과할 수 있으리라 짐작된다. 그려면 어떤 식으로 ..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 20.
• textsms

백준 15685번 : 드래곤 커브 [Java]

https://www.acmicpc.net/problem/15685 문제 탐색하기문제에서는 드래곤 커브를 세대에 따라 좌표에 그려서 정사각형의 네 꼭짓점이 드래곤 커브가 모두 방문하는 지점을 찾으면 되는 문제이다. 문제의 요구사항이 세대별로 방향을 바꿔가며 그려야해서 복잡할 수 있지만 어떻게 그릴 수 있는지 생각해보자. 0세대일 때는 x나 y좌표로 한칸 이동하면 된다. 이제 1세대 부터 문제가 생기는데, 끝 점에서 이동하여서 0세대 드래곤 커브를 이동시켜서 끝점에 붙여야 한다. 이 말인 즉슨 이전 드래곤 커브를 어떻게 그렸는지 좌표를 기록해야한다. 여기서 좌표를 기록할 수도 있고 지나온 방향을 기록해도 괜찮다. 이번 풀이 방법에서는 방향을 기록하는 방식으로 구현했다.  방향을 기록하는 방식으로 구현하려면..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 19.
• textsms

백준 9328번 : 열쇠 [Java]

https://www.acmicpc.net/problem/9328문제 탐색하기문제는 상근이가 h * w의 지도에서 열쇠와 문을 통해서 원하는 문서를 찾도록 구현하면 된다. 자칫 까다로워 보일 수 있는데 몇가지를 잘 생각해보면 비교적 구현하기 어렵지 않을 수 있다. 먼저 어떤 식으로 처리해야할지 떠올려보자. 입구는 여러 개일 수 있기 때문에 모든 입구를 매번 다 탐색할 수는 없다. 이에 따라서 테두리에 빈 칸을 두어서 항상 같은 빈칸에서 시작하도록 구현하면 된다. 이러면 입구를 찾는 방법을 떠올리지 않아도 되고 그저 bfs를 통해서 열린 부분을 탐색하면 된다. 예제 입력의 첫번째 테스트 케이스를 예로 들자면 아래와 같다. *****************.............**$**B*A*P*C**X*Y..

• format_list_bulleted Problem Solving/BOJ
• · 2025. 2. 18.
• textsms