'알고리즘/BOJ' 카테고리의 글 목록

[BOJ] 2457 공주님의 정원

2024.04.22

✨ 그리디 & 정렬 https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 📍 고려해야할 점 날짜를 비교하기 위해 입력으로 주어진 정보를 대소비교 가능하게끔 정수로 바꾸기 3/1 ~ 11/30 까지만 확인하면 된다. 꽃이 지는 날에는 꽃을 볼 수 없다. 입력으로 주어진 날짜를 꽃이 핀 날짜가 이른 순, 만약 핀 날짜가 같다면 진 날짜가 이른 순으로 정렬시켜야 한다. 🕹️ 풀이 과정 못 풀어서 풀이를 보고 다시 풀었다. Olympia..

알고리즘/BOJ

[BOJ] 1202 보석도둑 - Java

2024.04.19

✨ 우선순위 큐 & 정렬 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 📍 고려해야할 점 훔칠 수 있는 보석 가격의 최대의 합을 구해야 한다. 보석의 개수

알고리즘/BOJ

[BOJ] 1238 파티 - Java

2024.04.18

✨ 그래프 👉 다익스트라 (최단경로 탐색 알고리즘) https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 📍 고려해야할 점 각 학생들의 집에서 파티 장소까지 오고 가는 데 걸리는 최단 시간 구하기 도로들은 단방향 👉 길마다 걸리는 시간이 다르므로 오고 가는 길 또한 다름 ! N명의 학생들 중 오고 가는 데 가장 많은 시간을 소비한 학생 출력 🕹️ 풀이과정 집에서 파티 장소까지 가는 데 걸리는 최단 시간 + 파티 장소에서..

알고리즘/BOJ

[BOJ] 2169 로봇 조종하기 - Java

2024.04.16

✨ DP https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 📍 고려해야할 사항 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만 위쪽으로는 이동 X 한 번 탐사한 지역은 재탐사 X (1, 1)에서 (N, M)까지 갈 때 탐사한 지역들의 가치의 최댓값 구하기 🕹️ 풀이 방법 우선 0번째 행에 있는 값들은 왼쪽에서부터 이동하면서 합쳐진 값을 기록한다. 이미 탐색한 길은 다시 방문할 수 없으므로 경로가 왼쪽으로부터 이동..

알고리즘/BOJ

[BOJ] 14503 로봇청소기 - Java

2024.04.11

✨ 구현 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 📍 고려해야할 점 주변 동서남북 4칸 중 청소되지 않은 빈 칸이 없는 경우 즉, 모두 청소되었다면 바라보는 방향을 유지하고 한 칸 후진 가능하면 후진한다. 문제에서 0123 = 북동남서라는 조건을 제시했다. 후진할 시 방향이 북➔남, 남➔북 / 동➔서, 서➔동으로 이동하기 때문에 현재 바라보는 방향이 0, 1(북, 동)이라면 +2를 해줌으..

알고리즘/BOJ

[BOJ] 19238 스타트 택시 - Java

2024.04.11

✨ 구현 & BFS(최단거리) https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 📍 고려해야할 점 택시의 위치에서부터 승객까지의 최단거리를 구한다. 👉 시간초과 주의 ! 최단거리가 동일한 승객들이 존재할 경우 그 중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이라면 열 번호가 가장 작은 승객에게 이동한다. 👉 PriorityQueue 활용 벽에 의해 승객에게 가지 못하거나 목적지에 가지 못하는 상황 ..

알고리즘/BOJ

[BOJ] 17837 새로운 게임2 - Java

2024.03.19

✨ 구현 https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 📍 고려해야할 점 한 좌표 안에 여러 개의 말이 들어갈 수 있다. ➔ 이동하려는 칸에 말이 존재한다면 그 위에 말이 올라감 한 말이 이동할 때 위에 올려져 있는 말까지 모두 이동한다. 여러 개의 말이 들어갈 때 좌표의 색깔에 따라 정렬 기준이 존재한다. 좌표의 범위를 벗어나거나 좌표 칸이 파란색일 때의 조건을 유의해야한다. 🕹️ 풀이과정 어떤 자료구조로 활용할지 정하기만 하면 쉽게 풀..

알고리즘/BOJ

[BOJ] 17485 진우의 달 여행 (Large) - Java

2024.03.12

✨ DP https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 📍 고려해야할 점 왼쪽 대각선, 아래, 오른쪽 대각선 3가지 방향으로 이동한다. ✨✨ 같은 방향으로 두 번 연속으로 움직일 수 없다. ✨✨ 🕹️ 문제 풀이 현재 위치를 기준으로 그 전 단계에 사용했던 연료의 양을 계속 알고 있어야 한다. 그 전 단계에 사용했던 연료의 양과 현재 위치에 있는 연료의 양의 합을 구해서 최소의 연료를 사용할 수 있는 경우..

티스토리툴바