CS26 [ 백준 - 2116 ] 주사위 쌓기 난이도 : G5Link : https://www.acmicpc.net/problem/2116Tag : 시뮬레이션/구현 문제 탐색하기 - 주사위의 윗면과 다음 주사위의 아랫면을 같은 숫자로 하여 긴 사각 기둥을 만든다.- 한면의 숫자의 합이 최대가 되도록 주사위를 쌓아야한다. 시도 1 ( 성공 😲)떠오른 문제 해결 방법일단 문제의 정답에서 관심을 가져야할건 주사위의 최댓값만 관심있다는 것이다. 한면을 최대로 만들기 위해서는 붙인 다음 회전만 시키면 되기때문에 그냥 옆면들의 최댓값을 다 더하면 된다.그렇다면 어떻게 옆면에 최댓값을 넣을 수 있을까?바로 옆면에 활용하지 못하는 아랫면과 윗면에 붙어야하는 값을 최솟값으로 설정해야한다는 것입니다.처음에는 단순히 윗면만을 고려하려고했었습니다. (전 주사위의 윗면.. 2025. 4. 18. [ 백준 - 5212 ] 지구 온난화- 5212 ] 지구 온난화 난이도 : S2Link : https://www.acmicpc.net/problem/5212Tag : 시뮬레이션/구현 문제 탐색하기 - R*C 크기의 지도에는 'X' (땅) , '.' (바다) 가 존재한다.- 50년 후에, 인접한 세 칸 또는 네 칸에 바다가 있는 경우 해당 땅은 모두 잠겨버린다.- 50년 지난후에 지도를 출력해라(단, 지도는 모든 섬을 포함한 가장 작은 직사각형이다.) 시도 1 ( 성공 😲)시간복잡도⏰차례대로 모든 위치를 배정하면 가능합니다. 모든 섬의 상하좌우를 탐색하며 해당 땅이 바다에 잠겨버리는지 확인해야합니다.지도의 최대 크기는 10*10 이므로 모든 위치를 1초에 탐색하기에 충분합니다. ( 1줄어든 지도또한 상, 하, 좌, 우를 살펴보며 해당 열 또는 행에 '.'(바다) 만.. 2025. 4. 16. [ 이론 ] - Greedy 알고리즘 미래를 고려하지 않고 오직 현재 시점에 가장 좋은 선택을 한다Greedy(탐욕) 알고리즘이라는 이름과는 다르게 멋지다?라고 생각하는 Greedy 알고리즘에 대해 배워보겠습니다. 그리디 문제의 대표적인 예시를 살펴보면 쉽게 이해가 됩니다.6800원이라는 금액을 최소한의 동전을 사용해서 나타낸다면 500원*13개, 100원*3개로 총 16개 됩니다.금액이 큰 것부터 최대한 많이 사용하고, 다음 큰 동전을 최대한 많이 사용하는것을 반복하면 됩니다.매번 뒤의 동전은 상관없이 최대한 많이 바꾼다는 것입니다.즉, '현재 내릴 수 있는 최선의 선택에만 집중한다.'가 그리디 알고리즘의 핵심 전략입니다. 그렇다면 이 방식이 항상 최고의 결과를 보장할까? 결론은 항상 보장하지 못합니다.마시멜로 이야기를 예로들면, 1시간뒤.. 2025. 4. 11. [ 백준 - 2529 ] 부등호 난이도 : S1Link :https://www.acmicpc.net/problem/2529Tag : BFS 문제 탐색하기 - 부등호 k개의 방향에 맞게 k+1 자리의 정수를 선택하여 문자열을 만들면됨.- 선택된 문자열의 숫자값이 최대 최소 값을 출력해야한다.- 숫자는 중복해서 선택할 수 없다.시도 1 (실패)시간복잡도부등호 k개의 최대 개수는 9개이므로 숫자를 선택해서 넣을 수 있는 경우의 수는 9! = 362880모든 경우의 수를 계산하여도 시간내에 충분하고 실제로는 중간에 넣을 수 없는 숫자일 경우 바로 종료하면 되기 때문에 계산해야할 경우의 수가 더 적을것으로 기대됩니다. 선택 알고리즘모든 경우의 수를 탐색할 것이고, 매번 실행시 남아있는 숫자들중에 선택하면 되기 때문에 탐색, 그중에서 DFS를.. 2025. 4. 10. 이전 1 2 3 4 5 6 7 다음
