Jonyo Programming

[BOJ 14500(G5) 리뷰] 삼성 SW역량테스트 기출문제다. 처음엔 엄청 간단한 문제인 줄 알았다. 그냥 DFS로 구현하면 쉽게 풀릴것같아 쓱 구현해서 돌려보니 문제가 발생했다. DFS로는 이 모양을 만족할 수가 없는것이였다. 어떻게 처리할까 매우 고민했다. 이왕 하는거 논리적이고 깔끔하게 코드를 짜고싶어서 머리를 이리저리 굴려보았는데 답이 잘 안나왔다. 계속 고민하다보니 집중력이 계속 떨어져서 그냥 무식한 방법을 사용하기로 했다. DFS를하면서 두번째 블록에 위치할때, 위 모양이 나올 수 있는 경우의 수를 생각해서 그냥 인덱스로 접근해서 구해버렸다. 그나마 순열로 구현하는게 깔끔할테지만, 넥퍼뮤 사용법도 까먹고해서.. 그냥 무식하게 구해버렸다. 어쨌든 맞았으니 기분은 좋긴한데 왠지모를 찝찝함이 남..

[BOJ 1937(G3) 리뷰] 이 문제는 내리막 길 문제와 굉장히 유사하다. 언뜻 보기에는 단순한 BFS,DFS문제로 보이지만 만약 모든 경우에 대해 탐색하려 한다면 당연히 시간초과가 날 것이다. 따라서 이 문제 역시 이미 팬더가 지나갔던 길에 대해서는 다시 탐색할 필요가 없게 해야 한다. 예를들어 아래와 같은 맵이 존재할때 14 9 12 10 1 11 5 4 7 15 2 13 6 13 16 8 (1,2)인 9가 존재하는 위치에서 팬더의 최대 생존일은 9->11->15 3일이다. 따라서 만약 다른 위치에서 (1,2)를 다시 방문하게 된다면 이미 그곳에서의 최대 생존일을 알고 있으므로 다시 한번 탐색을 진행하지 않아도 된다. 이를 DP배열을 통해 관리하면 된다. 위 로직을 이해 하고 코드를 본다면 바로 ..

[BOJ 1520(G4) 리뷰] 언뜻보면 그냥 BFS,DFS문제로 보이지만 DP를 이용하여 풀지 않으면 시간초과가 난다. 따라서 목적지 까지 갔던 경로를 기억해야 하고 지금 가고있는 경로가 이미 목적지에 도착했던 경로라면 굳이 목적지 까지 갈필요가 없다. 이를 DP배열을 통해 구현했다. 목적지에 도착했을때에만 1을 반환하도록 하면 결국 DP[1][1]에는 목적지 까지 도착한 경로의 갯수만이 저장될것이다. #include using namespace std; int N, M; int board[501][501]; int dp[501][501]; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; int dfs(int r, int c) { if (r == N && c..