앞선 로그라이크 맵 생성 방식 글을 통해 현재 가장 보편적으로 사용되는 로그라이크 맵 생성 알고리즘 중 하나가 BSP 알고리즘이라는 것을 알았습니다. 그래서 이제, 이를 직접 구현해보며 공부해보려고 합니다. 먼저, BSP 알고리즘을 이용한 랜덤 맵 생성 알고리즘의 절차는 다음과 같습니다. 공간을 두 개로 계속해서 나눈다. (나눈 공간을 트리로 구성) 나눈 공간에 공간을 벗어나지 않는 크기의 방을 만든다. 방끼리 서로 이어준다. 1. 공간을 두 개로 계속해서 나눈다. BSP 알고리즘이 실질적으로 사용되는 단계로 이름에서도 알 수 있듯이 Binary Space Partitioning, 즉 공간을 두 개로 나누어 트리로 저장하는 알고리즘입니다. BSP 알고리즘 자체는 어떤 모양의 공간으로든 나눌 수 있지만 저..

풀이이전에 풀었던 2048 (Easy) 문제의 풀이 방법에서는 모든 경우의 수를 탐색하여 답을 도출했다면 2048 (Hard)는 10회의 이동으로 확장되었기 때문에 적절히 가지치기를 하여 시간을 줄여 답을 도출해야 합니다. 그럼, 어떤 경우를 가지치기해주어야 할까요?  블록들을 이동시켰는데 이전과 같은 모습일 경우단순하게 생각해봤을 때 가장 먼저 떠오르는 방법입니다. 어떤 한 경우에 대하여 상하좌우를 모두 구하기 때문에 상하좌우 중 같은 모양을 가진 경우가 발생하면 애초에 탐색할 필요가 없습니다. 중복된 경우를 탐색하기 때문입니다.  구한 최댓값이 이전에 구한 것보다 작을 것이라는 게 예상되는 경우이 경우는 저도 백준 질문 검색에서 얻어낸 해답입니다. 예를 들어 처음에 최대 10회 이동에 대해 탐색하였더..

풀이모든 경우의 수에 대해서 검사를 해봐야 어떤 경우에 가장 큰 수가 만들어지는지 알 수 있는 문제입니다.그래서, 풀이 방법은 ‘백트래킹’을 이용하여 모든 경우의 수를 검사하는 것입니다. 백트래킹 자체의 구현은 어렵지 않지만 각 수들을 move 하는 것에 시간이 좀 걸렸던 문제였습니다.위, 아래 이동은 row를 이동하면서 갱신해야하고왼쪽, 오른쪽 이동은 column을 이동하면서 갱신해야합니다. 각 칸에 대하여 선택된 칸 뒤에 남아있는 칸을 순서대로 검사하면서 남아있는 칸이 0이면 넘어가고, 0이 아니면 선택된 칸(0이 아니면)과 합치거나 혹은 선택된 칸(0이면)에 그 칸의 값을 이동시켰습니다. 선택된 칸과 남아있는 칸이 합쳐졌다면 다음 칸으로 넘어가서 같은 과정을 반복하면 되지만, 만약 선택된 칸이 0이..

* 개인적인 기록용입니다.https://www.acmicpc.net/problem/1541 왜 그리디인가?‘+’와 ‘-‘ 그리고 ‘수’로 구성된 식이 있을 때 그 식을 최소로 만드는 계산법을 찾는 것인데, 만약 식에서 ‘-‘를 빼는 것으로 생각하면 ‘-‘ 식 계산 후에 더하는 식이 또 있다면 필연적으로 결과값이 점점 커지게 됩니다. 그래서 최솟값이 절대 될 수 없습니다. 하지만 ‘-‘를 음수로 바꾸는 것으로 생각한다면 ‘-‘ 뒤의 더하는 식들을 이용하여 최솟값을 만들 수 있게 됩니다! 즉, 음수는 절댓값이 클수록 더 작은 값임을 이용하는 것이죠. 예를 들어, 10+20-30+40+50+60-70과 같은 식이 있다면 다음과 같이 묶어주어 10+20-(30+40+50+60)-70 계산하면 최솟값이 됨을 알 ..