오딩이

출처 : https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 🔍Solve 순조부의 전형적인 순열 문제입니다. 순열은 서로 다른 n개 중 r개를 택하며, 순서를 고려합니다. 주의해야 할 점은 n이 12를 넘어가면서(12!) 시간 복잡도가 폭발적으로 증가합니다. 해당 문제는 n이 8까지이므로, 무리없이 돌릴 수 있었습니다. 운동 키트의 증량 증가량을 담은 배열을 선언하고 해당 배열을 순열 함수를 돌립니다. permutation의 매개변수는 ..

최장 증가 수열 : Longest Increasing Subsequence 📌 최장 증가 수열이란? 어떤 배열이 있을 때, 배열의 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출한 것입니다. 예를들어, [4, 2, 3, 1, 5, 6]이라는 배열이 있을 때 LIS는 [2, 3, 5, 6]이 됩니다. 점차 증가하는 배열은 [4, 5, 6] 또는 [2, 3, 5, 6] , [3, 5, 6] 등 여러 부분집합이 있을 수 있지만, 그 중 부분집합의 최대 배열을 의미하므로 LIS는 [2, 3, 5, 6]이 됩니다. 🔍 가장 먼저 생각해 볼 수 있는 풀이는 완전탐색(Brute-Force)입니다. 수열의 모든 부분 집합을 구하여 그 부분 집합이 증가 수열인지를 판단합니다. 완전탐색으로 풀 경우 부..

출처 : https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 🔍 Solve BFS를 사용하여 풀었습니다. 문제에서 주의해야 할 점은 공기와 접촉된 치즈는 한 시간이 지나면 녹아 없어지지만, 치즈 안에 있는 구멍에 인접한 치즈는 녹지 않는다는 점이었습니다. 따라서 치즈가 아닌, 공기의 위치를 BFS로 탐색하여 치즈를 녹이는 방법을 선택했습니다. 치즈가 모두 녹기까지 시간이 얼마나 걸렸는지를 배열에 저장하기 위해 기존 공기가 0, 치즈가 1의 값을 가졌던 것을..

출처 : https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 🔍 Solve 다이나믹 프로그래밍으로 풀기 전, 완전 탐색으로 풀었을 때 시간 초과가 났던 문제입니다. 완전 탐색으로 풀었을 때 우선순위가 큰 것부터 선택하고 인접한 곳들을 지우는 방법으로 풀었습니다. isSelect배열을 선언하여 지워지는 곳은 1로, 선택된 곳은 2로 저장하였고, isSelect배열이 0이 아닌 수로 꽉 차면 break를 해주었습니다. 해당 방법은 테스트 케..