IT's me

2차원 배열의 합 - 동적 계획법 문제 (백준)

이 문제를 처음 보고 이게 왜 동적 계획법인가 의아했다.

그냥 아무 생각 없이 2중 for문을 돌려서 답을 찾았다.

너무 쉬운 문제라고 생각했다. 하지만 수행시간이 상당히 맘에 걸렸다.

다른 분들은 16MS가 나오는데 836MS가 떠버린 것..

수행 시간을 위해서라도 동적 계획법으로 풀어봐야겠다는 생각이들어서

나름 DP배열을 선언하고 활용하면서 문제를 다시 풀어보았다.

2차원 배열의 합(동적 계획법)

836MS에 비하면 반으로 줄었지만 16MS에 비하면 어마어마한 수치가 떠버렸다..

어떻게 풀었을지 힌트라도 얻고 싶은데.. 코드 오픈을 아무도 해놓지 않았다 ㅠ

01. 초기화

초기화를 할 때 DP배열 또한 초기화를 해주었는데

이전의 모든 값의 합을 저장하는 것이 아니라 한 행마다 따로따로 합을 계산했다.

02. 동적 계획법(다이나믹) 알고리즘

때문에 DP배열 x행의 y열을 선택하면 그 행의 y열까지의 최대 합이 들어있다.

그 합을 모두 더한 것에서 필요 없는 부분을 빼버리면 답을 구할 수 있다.

딱 보고 문제가 너무 쉬웠기 때문에 빨리 풀고 다음 문제로 넘어가야지 했는데

수행 시간 때문에 한참을 고전했던 것 같다. 완벽하게 수행 시간을 줄이지는 못했지만

계속해서 연구해봐야 할 가치가 있는 문제라고 생각한다.

DFS 알고리즘 - 영역 구하기 (백준)

확실히 DFS가 BFS 알고리즘 보다는 손이 덜 가고 쉽게 풀리는 것 같다.

이번 문제는 입력을 받을 때, 모눈 종이 역할을 하는 2차원 배열에 색칠을 해나가면서 진행했다.

좌표를 구하는 부분에서 수학 문제를 푸는 것 같아 약간 주춤했지만 어려운 수준이 아니라 패스~

영역 구하기 문제 (DFS 알고리즘)

01. 변수 선언

02. 초기화

03. DFS 알고리즘

04. 메인

최근들어 BFS, DFS 문제를 많이 풀어보고 있는데, 확실히 동적 계획법보다는 푸는 재미가 있는 것 같다.

현재 만들고 있는 퍼즐 게임에서 유용하게 쓰일 알고리즘이라 한 동안 집중해서 공부할 예정이다.

BFS 알고리즘 문제 - 숨바꼭질 (백준)

처음에는 DFS로 풀어보았는데 시간초과를 극복 할만한 대안이 떠오르지 않았다.

문제 자체가 최단으로 도착하는 방법을 찾는 것이기 때문에 BFS가 더 적합한 것 같다.

숨바꼭질 (백준) - BFS

01. 초기화, 변수 선언 등

02. 함수들

03. BFS 알고리즘

04. 메인

이제 BFS, DFS 알고리즘을 활용하여 간단한 퍼즐 게임을 만들어 보려한다.

위의 두 알고리즘이 퍼즐게임의 핵심 알고리즘으로 활용될 수 있을 것 같아

예전부터 꾸준히 공부해왔는데, 이제 실제로 활용해 볼 때가 된 것같다.