반응형 알고리즘37 게임 적(몬스터) 순찰 기능 만들기 - 다익스트라 알고리즘 게임 활용 방법 안녕하세요 오늘 다익스트라 알고리즘에 대한 글을 적어볼까합니다. 원래 저는 알고리즘 공부하는 것을 그렇게 좋아하지 않는데요 왜냐하면 알고리즘을 배워도 게임 개발에 어떻게 써먹어야할지 잘 안 와닿기 때문입니다. 하지만 확실히 개발하다 보면 필요할 때가 오게 됩니다. 그래서 이번에는 제가 어떤 게임을 개발하면서 어떤 부분에 이런 알고리즘 활용해서 기능을 개발할 수 있는 지와 이 알고리즘 방식에 대해 저 나름대로 설명을 풀어나갈까 합니다! 이번에 제가 만든 게임은 어떤 장소에서 순찰하는 적이 있고 그 순찰하는 적을 피해서 플레이어가 아이템을 획득해서 탈출하는 게임입니다. 여기서 중요한 부분은 아무래도 적의 움직임입니다. 적의 움직임이 너무 쉽고 단조롭다면 난이도가 하락하고 플레이어들이 덜 재밌어 하겠죠? .. 2024. 10. 20. [알고리즘/백준] 1309번 동물원 Python 파이썬 저번 문제는 혼자 힘으로 못 풀어서 글을 못 썼는데 이번 문제는 나름 풀고 성찰할 부분이 있어서 글을 적게 되었습니다. 이번 문제도 DP 문제입니다. 이번 문제는 2 X N 사자 우리가 주어지고 사자들을 배치할 때의 경우의 수를 9901로 나눈 나머지를 출력하는 문제입니다. 저번에 2133번 문제를 풀었는데 나름 방식이 유사한 문제인거 같습니다. 혹시 해당 문제를 푸셨다면 다음은 2133번을 풀어보는 것을 추천드립니다. 일단 풀이 과정으로는 몇가지의 경우의 수를 직접 그려보았습니다. 각 경우의 답에서 규칙성을 찾아보았을 때 DP[i] = DP[i-2] + (DP[i-1]*2) 식을 정의할 수 있습니다. 이를 적용해서 코드를 구현하였습니다.. 다음과 같은 코드로 통과하였습니다.. import sys inp.. 2023. 4. 24. [알고리즘/백준] 11048번 이동하기 Python 파이썬 갈수록 DP에 대한 감을 잡아가고 있는 것 같습니다. 이번에도 DP 관련 문제입니다. 준규가 (1,1) 위치에서 (N, M) 위치까지 갈 때 최대로 얻을 수 있는 사탕의 갯수를 구하는 문제로 지도가 나오길래 BFS 문제인가 흠칫했습니다. DFS든 BFS든 여러 방법으로 풀 수 있는 문제같긴 했습니다. (궁금해서 찾아보니 BFS 로는 가능하고 DFS 경우 메모이제이션을 했다면 전에 값을 구한 적이 있을 때 바로 리턴하는 부분이 있어야 하는데 이 코드에서는 끝에 도달했을 때만 리턴을 할 뿐 메모한 부분을 활용하고 있어 의미가 없다고 하네요. 시간초과 날 경우도 높고) 일단 DP 문제로 들어온거라 DP 방식을 사용해서 풀어볼려고 시도해보았습니다. (BFS와 DP 문제 구분법 : BFS는 그래프에서 간선의 가중.. 2023. 4. 21. [알고리즘/백준] 2193번 이친수 Python 파이썬 요즘도 여전히 다이나믹 프로그래밍 문제를 풀고 있습니다. 이번 문제는 위 조건에서 요구하는 이친수를 찾는 문제입니다. 그러면 무엇을 해야하는가? 전번 풀이에도 이야기했듯이 다이나믹 프로그래밍 문제를 풀 때는 규칙성을 찾는 것이 매우 중요하며 이를 찾기 위해 직접 몇가지의 경우의 수를 적어보면서 어떻게 결과가 도출되는지 과정을 살펴보는 것이었습니다. 그렇기 때문에 초반에 어떻게 결과가 도출되는지 아래와 같이 적어보았습니다. 위 풀이를 보면서 규칙성을 찾을 수 있게 되었습니다. 바로 전 2단계의 답 합이 다음 답이라는 것이었습니다. 즉 dp[i] = dp[i-1] + dp[i-2] 로 정의할 수 있습니다. 다음과 같은 코드로 통과하였습니다. import sys input = sys.stdin.readline.. 2023. 4. 19. 이전 1 2 3 4 ··· 10 다음 반응형
