알고리즘
-
[백준] 4485번 - 녹색 옷 입은 애가 젤다지? - 자바(JAVA)알고리즘/백준 2022. 5. 16. 00:01
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 해석 젤다의 전설 게임의 화폐 단위는 루피이다. '도둑 루피'라 불리는 검은색 루피도 존재하여 이것을 획득하면 오히려 소지한 루피가 감소됩니다. 현재 주인공 '링크'는 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있습니다. 즉, 시작점은 (0,0)에 위치 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 합니다. 이동은 상..
-
3124. 최소 스패닝 트리 - 자바(JAVA)알고리즘/SW Expert Academy 2022. 5. 16. 00:01
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하세요. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말합니다. 입력으로 주어지는 그래프는 하나의 연결 그래프임이 보장됩니다. 문제 풀이 전 설계 스패닝 트리를 계산하는 알고리즘으로는 프림 알고리즘과 크루스 칼 알고리즘이 존재합니다. 본 문제에서..
-
[백준] 1854번 : k번째 최단경로 찾기알고리즘/백준 2022. 5. 15. 01:17
https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 문제 해석 항상 최단경로로 이동하는 것을 별로 좋아하지 않는다. 또한 너무 시간이 오래 걸리는 경로도 좋아하지 않아 적당한 타협안인 'k번째 최단경로'를 구하길 원합니다. 도시는 항상 1번부터 시작합니다. 첫째 줄에 n, m, k가 주어집니다. n은 김 조교가 여행을 고려하고 있는 도시들의 개수 m은 도시 간에 존재하는 도로의 수 입니다. ..
-
[백준] 1600번 : 말이 되고픈 원숭이 - 자바(JAVA)알고리즘/백준 2022. 5. 14. 00:01
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 해석 말은 격자판에서 체스의 나이트와 같은 이동방식을 가집니다. X 표시한 곳은 말이 갈 수 있는 위치이며 말은 장애물을 뛰어넘을 수 있습니다. 하지만 원숭이는 능력이 부족해서 k번만 말처럼 움직일 수 있고 ,그 외에는 그냥 인접한 칸으로 움직일 수 있습니다. 인접한칸은 상하좌우를 의미합니다. 원숭이는 맨 왼쪽위에서 시작해서 맨 오른쪽 아래로 가려고 합니다. 최소한의 동작으로..
-
[백준] 2636번 : 치즈 - 자바(JAVA)알고리즘/백준 2022. 5. 13. 00:01
https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 문제 해석 정사각형 칸으로 이루어진 보드가 존재합니다. 그 위에 회색으로 표시된 부분은 치즈를 의미합니다. 치즈는 공기 중에 놓으면 녹게 되며 한 시간이 지나면 녹게 됩니다. 테두리 부분인 c부분이 한 시간이 지나면 녹게 되며 다음과 같은 그림이 됩니다. 이때 치즈가 모두 녹아 없어지는데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈 조각이 놓여있는 칸의 개수를 구하세요 문제 풀이 전 설계 공기와 ..
-
[백준] 1516번 : 게임 개발 - 자바(JAVA)알고리즘/백준 2022. 5. 12. 00:01
https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 해석 모든 건물이 완성되기 위한 시간을 구해야 합니다. 건물에는 순서가 존재할 수 있습니다. 예를 들어 A건물을 지어야지 B건물을 지을 수 있는 경우가 존재하기 때문에 이점을 고려해야 합니다. 건물의 수와 각 건물의 짓는 데 걸리는 시간과 해당 건물을 짓기 위해 지어져야 하는 건물들의 번호가 주어집니다. 짓기 위해 지어야 하는 건물은 여러 개가 존재할 수 있습니다. 각 줄은 -1으..
-
[프로그래머스] 2019 KAKAO BLIND RECRUITMENT - 무지의 먹방 라이브 - 자바(JAVA)알고리즘/프로그래머스 2022. 5. 11. 00:01
https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 문제 해석 회전판에 먹어야 할 N개의 음식이 존재합니다. 각 음식에는 1부터 N까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요됩니다. 무지는 다음과 같은 방법으로 음식을 섭취합니다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다. 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 ..
-
[백준] 10282번 : 해킹 - 자바(JAVA)알고리즘/백준 2022. 5. 10. 00:01
https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 문제 해석 네트워크 시설의 한 컴퓨터가 해킹되었습니다. 서로 의존하는 컴퓨터들은 점차 하나씩 감염되기 시작합니다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면 b가 감염되면 일정 시간 뒤에 a도 감염됩니다. 하지만 b가 a를 의존하지 않는다면 a가 감염되더라도 b는 안전합니다. 컴퓨터 번호와 각 의존성이 주어질 때 , 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하세요 문제 풀이 전..