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

[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번째 행에 있는 값들은 왼쪽에서부터 이동하면서 합쳐진 값을 기록한다. 이미 탐색한 길은 다시 방문할 수 없으므로 경로가 왼쪽으로부터 이동..

알고리즘/CodeTree

[CodeTree] 메이즈 러너 - Java

2024.04.12

✨ 구현 👉 조건을 만족하는 가장 작은 크기의 정사각형을 찾고 시계방향으로 90도 회전 https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 📍 고려해야할 점 참가자가 현재 있는 칸 ~ 출구까지의 거리 < 참가자가 이동할 칸 ~ 출구까지의 거리 ➔ 이동 X 출구까지의 최단거리가 더 가까워야 이동 가능 움직일 수 있는 칸이 2개 이상이라면 상하로 움직이는 것을 우선시..

알고리즘/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 활용 벽에 의해 승객에게 가지 못하거나 목적지에 가지 못하는 상황 ..

알고리즘/🗂️ 정리

😺 범위를 벗어날 경우 반대방향으로 이동하는 알고리즘 😺

2024.04.09

알고리즘을 풀면서 기억해두면 좋을만한 코드를 기록한다. 😺 상황 설명 고양이가 상하좌우로 L만큼 이동할 때 범위 밖으로 이동한다면 이동방향을 반대로 바꾼 후 이동을 계속 진행한다. 만약 L의 값이 10억일 때 for문을 10억 번 돌려 고양이가 이동하게 되는 위치를 정하는 것은 비효율적이며 시간초과가 발생한다. 고양이의 위치를 반복문이 아닌 식을 이용해서 구해보자. 🕹️ 구현 방법 🔹 오른쪽으로 이동할 때 4x6의 판에서 현재 고양이는 (2, 2)에 위치해 있다. 고양이가 만약 3칸 이동하면 범위에 벗어나지 않는다. 하지만 오른쪽으로 7칸 이동할 때 범위를 벗어나게 된다. 다음 이동하려는 칸이 범위에 벗어난다면 방향을 반대로 바꿔 이동하고, 최종적으로 (2, 1)에 위치하게 된다. 12칸 이동하면 동일한..

티스토리툴바