백트래킹 | 백준 1799번: 비숍 Java

https://www.acmicpc.net/problem/1799 반갑다. 오늘은 백준 1799번 비숍 문제를 풀어보며 체스의 고수가 되어보자.이 문제에서는 백트래킹을 이용해서 체스 챔피언이 될 수 있는 사고력을 기를 수 있다. 전략을 세워보자문제를 푸는 큰 틀은 N-Queen 문제와 동일하다. 각 좌표에서 이전의 사례들을 참고하여 놓을 수 있는지 없는지를 판단하면 된다. 참고 : 백준 N-Queenhttps://www.acmicpc.net/problem/9663 다만, 한 가지 다른 점은 비숍만을 이용할 수 있기 때문에 대각선에 위치해있는지 판단하면 된다.추가적으로, 비숍은 대각선, 즉, 본인의 타일과 색이 같은 타일로만 이동할 수 있기 때문에 타일 색으로 분리해서 따져본다면 최적화를 할 수 있다.똑..

• format_list_bulleted Algorithm/백준(BOJ)
• · 2025. 7. 6.
• textsms

백트래킹 | 백준 18809번 : Gaaaaaaaaaarden Java

https://www.acmicpc.net/problem/18809 반갑다. 오늘은 백준 18809번: Gaaaaaaaaaarden 문제를 보자. 전략을 세워보자문제에서 유추할 수 있는 요구사항은 다음과 같다.- 주어진 배양액을 뿌릴 수 있는 위치에 모두 소비할 때까지 뿌린다.- 뿌린 자리에서 매 초 인접한 땅으로 배양액이 퍼져나간다.- 동시에 두 배양액이 만난 시점의 자리에 꽃이 피어나고 두 배양액은 사라진다. 그럼 우리가 작성할 기능은 다음과 같이 추출할 수 있다.- 배양액을 뿌리는 기능- 배양액을 퍼트리는 기능- 두 배양액이 만났는지 체크하여 꽃으로 체크하는 기능자, 코드로 옮겨보자1. 입력과 전처리코드가 길어질 것 같아 입력을 받는 부분은 init() 함수로 분리했다.N, M, G, R 변수를..

• format_list_bulleted Algorithm/백준(BOJ)
• · 2025. 7. 5.
• textsms

Greedy | 백준 2170번 : 선 긋기, 한 붓 그리기로 공부하는 그리디 C++

https://www.acmicpc.net/problem/2170 반갑다. 오늘은 백준 2270번, 선 긋기 문제를 같이 풀어보자.이 문제를 해결하고 나면 C++로 그리디하게 한 붓 그리기 하듯 선분을 병합하는 방법에 대해 감을 잡을 수 있을 것이다. 전략을 세워보자선분들이 막 섞여 있다. 겹치기도 하고, 따로 떨어지기도 한다.우리는 펜을 최소한으로 들어서, 선을 모두 그어야 한다.목표는 간단하다 — 총 얼마나 그었는가. 핵심은 다음과 같다:정렬한다. 시작점 기준으로.겹치면 병합한다. 떨어졌으면 그 전 구간 길이 저장.끝까지 갔다면 마지막 구간 길이 더한다.즉, "펜을 떼지 않고 한 번에 그을 수 있는 구간"의 직선 길이 합을 구하는 것이 오늘의 목표 되시겠다. 자, 코드로 옮겨보자1. 입력과 전처리선분..

• format_list_bulleted Algorithm/백준(BOJ)
• · 2025. 6. 18.
• textsms

다익스트라, 유니온 파인드 | 백준 1939번: 중량제한 자바

문제https://www.acmicpc.net/problem/1939 문제 설명N개의 섬이 존재하고 섬을 잇는 섬 간 연결 정보와 이동할 수 있는 최대 중량이 주어질 때, 시작 섬에서 도착 섬으로 이동시킬 수 있는 최대 중량을 구하는 문제입니다.접근 방법두 가지 접근 방식으로 문제를 해결했습니다.1. 다익스트라(dijkstra)최대 노드의 수가 10,000개 이고, 시작 노드가 고정되어 있으므로 다익스트라 알고리즘을 이용하여 최대 중량 값을 구할 수 있을 것으로 생각하고 구현했습니다. cost(이동 시 최대 중량)이 높은 순으로 탐색을 진행했습니다.PriorityQueue pq = new PriorityQueue((o1, o2) -> o2.cost - o1.cost); 또한, 이동 경로의 가장 작은 중량..

• format_list_bulleted Algorithm/백준(BOJ)
• · 2025. 5. 17.
• textsms

Heap | 백준 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) Java

문제https://www.acmicpc.net/problem/14698 문제 설명슬라임을 합성하기 위한 에너지가 주어지고, 두 슬라임을 합성했을 때 소비되는 전력은 두 슬라임을 합성하기 위한 에너지의 곱입니다. 이때, 모든 슬라임을 합성하여 하나의 슬라임이 나올 때까지 합성할 때까지 소비되는 전력의 최소값을 mod연산하여 산출하는 문제입니다. 모든 전력을 산정하는 방법은 각 슬라임 합성 시 소비된 전력의 곱입니다. 접근 방법끝까지 합성하고 난 후에 생기는 슬라임의 에너지의 양이 2 × 1018 이하라는 것이 보장된다.모든 테스트 케이스에 대한 N 의 총합이 1, 000, 000을 넘지 않음이 보장된다.라고 했으므로, 각각의 합성된 슬라임은 long의 범위를 넘지 않는 다는 것을 뜻합니다.하지만, 모든 합..

• format_list_bulleted Algorithm/백준(BOJ)
• · 2025. 5. 13.
• textsms

TopologySort | 백준 1005번: ACM Craft 자바

문제https://www.acmicpc.net/problem/1005 문제 설명어떤 건물을 짓기 위해서 반드시 지어야 하는 건물이 있습니다.만약 건물 C를 짓기 위해서 A, B를 지어야 한다면 A C, B C 와 같이 관계가 주어집니다.이때, 목표 건물 W를 짓기 위해서 필요한 최소 비용을 구하는 문제입니다.접근 방법테스트 케이스 T, 건물의 개수 N, 건물 간 관계의 개수 K, 각 건물을 짓기 위해 필요한 비용 D[i] 가 주어집니다.건물을 짓기 위해 필요한 건물이 건설되지 않는다면 목표 건물을 짓지 못하기 때문에 반드시 선행 건물이 지어져야 합니다.따라서 indegree가 0이 되는 순서에 따라 정렬되는 위상정렬 알고리즘이 적합하다고 생각했습니다. 기억할 점위상 정렬 알고리즘을 코드로 구현할 때, 사..

• format_list_bulleted Algorithm/백준(BOJ)
• · 2025. 5. 3.
• textsms