문제 출처 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 알고리즘 분류시뮬레이션그래프 탐색 풀이중간에 나무를 만날 때마다 나무를 베고 지나간다.우리는 매 칸을 방문할 때, 나무를 몇 번 더 벨 수 있는지, 그리고 어떤 방향에서 왔는지를 기록해줘야 한다.그러기 위해, 방문하는 칸의 좌표와 나무를 벨 수 있는 횟수, 방향을 나타내는 4차원 배열을 선언한다.이제 BFS를 해줘야 한다. 시작 방향은 위쪽이다.직진을 하는 경우, 다음 칸이 범위 안에 존재해야 한다.범위 안에 존재하는데 현재 칸이 나무인 경우, 나무를 벨 수 있는 횟수(K)가 1회 이상이라면 나무를 베고 지나간다. 이 때, 나무를 벨 수 있는 횟수가 K ..

문제 출처 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 알고리즘 분류최단 거리 알고리즘 풀이dp[A][B]면 A보다 B가 키가 더 크다는 것이고, dp[B][A]면 A보다 B가 키가 더 작다는 뜻이다.M가지의 키 정보를 기록하고 플로이드-워셜 알고리즘을 사용하여 N명 전체의 키의 상관관계를 기록한다.i번째 행에서는 i번째 사람보다 키가 큰 것이 확실하다면 1 이상의 숫자가 기록될 것이고, 그게 아니라면 -1일 것이다.i번째 열에서는 i번째 사람보다 키가 작은 것이 확실하다면 1 이상의 숫자가 기록될 것이고, 그게 아니라면 -1일 것이다.이를 이용해서 i번째 사람보다 키가 큰 사람과 키가 작은 사람의 수를 구할 ..

문제 출처 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 알고리즘 분류다이나믹 프로그래밍그래프 탐색백트래킹 풀이먼저 창고에 존재하는 모든 화학 물질 용기를 조사한다. 이는 BFS로 처리할 수 있으며, BFS를 수행하면 직사각형이 나올 텐데 이 직사각형의 높이와 너비를 기록해둔다.창고를 조사한 후에는 최대 20개의 직사각형 형태의 화학 물질 용기가 나올 것이며, 이를 HXW 크기의 행렬이라고 가정한다.이제부터는 모든 화학 물질 용기를 섞는 최소의 횟수를 구해야 하며, 이 때 연쇄 행렬 최소 곱셈 알고리즘(이하 MCM, Multiple Chain Matrix Algorithm)이라는 걸 사용한다.그러기 위해서는, 먼..

문제 출처 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 알고리즘 분류수학그리디 알고리즘 풀이N을 P로 나눈 몫을 S, 나머지를 R이라고 한다.R의 개수만큼 S + 1을 곱하고 P - R의 개수만큼 S를 곱한 값이 받을 수 있는 사탕의 최대 개수가 된다. 코드더보기import java.io.*;import java.util.*;public class Solution { static long Answer; public static void init() { Answer = 0; } public static void settings(long N, long P) { long S = N / P; long R =..

문제 출처  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 알고리즘 분류문자열정렬 풀이문자열 S의 길이를 N이라고 한다.i번째 문자로 시작하는 문자열 S의 부분 문자열 N개를 배열에 추가하고 오름차순 정렬한다.정렬된 배열에서 K번째에 위치한 문자열이 정답이 된다. 코드더보기import java.io.*;import java.util.*; public class Solution { static String Answer; public static void init() { Answer = ""; } public static void settings(int N..

문제 출처 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 알고리즘 분류백트래킹 풀이회사에서 시작해서 최대 10명의 손님을 방문한 후 집으로 도착하는 경우의 수는 10! = 3,628,800가지이다.백트래킹을 사용해서 최대 10명의 손님을 방문하는 모든 경우의 수를 탐색하며 이동하는 거리를 계산한다.모든 손님을 방문했다면 마지막 손님의 위치와 집의 위치 사이의 거리까지 더한 값이 회사에서 출발하여 모든 고객에게 냉장고를 방문하고 집에 도착했을 때 걸린 이동 거리가 된다.이 이동 거리의 최솟값을 구한다. 코드더보기import java.io.*;import java.util.*;public class Solution ..

문제 출처 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 분류 다이나믹 프로그래밍 풀이 점수의 개수가 총 100개이기 때문에, 경우의 수는 2^100가지이므로 백트래킹으로는 풀 수 없다. 따라서 DP로 해결해야 한다. 먼저 0점은 처음부터 가능하므로 DP[0] = true로 초기화한다. 그리고 다음 점수를 입력받으면 현재 점수의 Index * 100(== i)점부터 DP[i]가 true라면 DP[i + 점수] 역시 true가 된다. 첫 번째 테스트 케이스를 보자면, 처음에 2점을 입력받았으므로 DP[0 + 2]는 true가 된다. 그리고 다음 3점을 입력받았으므로 DP[2 + 3], DP[0 + 3]..