종난아! 공부하자!

#문제 https://www.acmicpc.net/problem/11048 #풀이굉장히 쉬워보이지만 은근 까다로운 문제인것 같습니다!처음에는 BFS를 사용하여 푸는 생각을 했지만, 해당 문제는 최단 거리를 움직여 구하는 것이 아니며, 모든 경우의 수를 해보아야 하고 이미 지나간 자리도 다시 한번 확인을 해야합니다.또한, N과 M이 1000이 넘어가므로 크기도 어마어마해집니다.따라서 DP(Dynamic Programming)으로 풀었습니다. DP의 경우 엄청 복잡한 알고리즘이 아닙니다.혹시나 DP를 처음 접하시는 분이라면 잠깐 새 탭을 눌러 검색하여 사전 공부를 하시는 것이 좋습니다! :) 다시 문제로 들어가서! 사탕을 최대로 모아야 하며 준규가 움직이는 방향은 오른쪽, 아래, 대각선(오른쪽 아래) 총 3..

#문제 https://www.acmicpc.net/problem/12906 #풀이은근 시간이 많이 걸렸던 문제입니다. 딱 문제를 보자마자 모든 경우의 수를 해봐야겠다! 라는 생각이 들었습니다.저는 모든 경우의 수를 돌릴 때에는 대부분 DFS로 했기 때문에 해당 문제도 그렇게 접근하려 했습니다.하지만, 원판을 내 마음대로 뽑을 수 있는 것이 아니라 무조건 맨 위에있는 원판 만 움직일 수 있으므로 풀이가 쉽지 않았습니다. 결국... 구글링... :)풀이가 많이 있지도 않았습니다... 아직 많이 풀어보지 않은 문제라 그런가 봅니다...딱 한가지 풀이가 있었는데 BFS를 이용하였습니다.(참고 사이트) BFS로 모든 경우의 수를 돌리는 것이 이해가 더 잘 오기에 BFS로 풀게 되었습니다. 큐에 넣을 때는 현재 탑..

#문제 https://www.acmicpc.net/problem/3197 #풀이문제를 보면 크게 두가지를 확인해야 합니다.우선 일마다 얼음이 어디가 녹는지 확인을 해야하고, 그 맵에서 언제 백조들이 만날 수 있는가를 확인하면 됩니다. 처음으로 제가 생각해본 방법은 가장 단순하게 하루하루 물과 근접한 얼음들을 녹게하고, 백조들이 만나는지 확인하는 알고리즘을 세웠습니다.얼음을 녹이는 것과 백조들이 만날 수 있는지 확인하는것 모두 BFS를 사용하여 풀었었습니다. 하지만 이게 왠걸...최대 크기를 완전 고려하지 않았습니다...R과 C가 모두 최대 1500...만약 위와 같은 방법으로 했을 경우, 물인 곳을 넣고 퍼지게 하는 것만 O(R * C) 걸리게 되고, 그 안에서 백조들이 만나는지 확인하는데 또 다시 O(..

#문제 https://www.acmicpc.net/problem/2234 #풀이해당 문제는 BFS를 사용하면 손쉽게 풀 수 있습니다. 우선 저는 맵에서 칸마다 벽이 있고 없고의 유무를 주었습니다.10진수로 주어진 값을 2진수로 바꾸어 어디 방향에 벽이 있는지 알아야합니다. 예로 11이 들어왔을때, 11은 1011로 나타낼 수 있고 앞자리부터 순서대로 남, 동, 북, 서에 벽이 있는지 없는지 유무를 나타냅니다.따라서 11은 남, 북, 서에 벽이 있으며 동으로 움직일 수 있다는 뜻이 됩니다. 이때, 방향을 잘 기억해 두는 것이 좋습니다.해당 방향의 순서들이 한번 더 사용할 곳이 있습니다! 이는 좀있다가 알아보도록 하죠! 또한 6(0110)과 같이 4자리가 꽉 채워지지 않는 수들은 앞에 '0'을 붙혀 4자리를..

#문제 https://www.acmicpc.net/problem/14442 #풀이BFS를 사용하여 풀어보았습니다. 처음에는 K개의 벽을 선택하고 해당 벽을 지운 후에 BFS를 돌릴려는 생각을 했으나...입력되는 맵의 크기가 1000 * 1000에다가 벽을 지울 수 있는 최대 개수가 10개...굉장히 시간초과 날만합니다... 그런데도 무식하게 진행했다는... 결국 3차원 배열에 저장하는 식으로 방향을 바꾸게 되었습니다.dist[r][c][cnt] -> r : 행 , c : 열 , cnt : 벽을 부순 개수 -> 위치(r,c)에서 cnt만큼 벽을 부셨을 때, 움직인 거리를 저장해주었습니다.최대 1000 * 1000 * 10 배열을 채우게 되므로 시간 안에 풀 수 있게 됩니다. #코드12345678910111..

#문제 https://www.acmicpc.net/problem/5213 #풀이 읽는데 힘들었고(아이언맨에... 닥터후까지 나오는..대서사기...) 굉장히 시간이 많이 걸렸던 문제였습니다.어디가 틀렸는지 제대로 찾지 못하였다가 결국 반례를 찾게 되었습니다... 구글링을 해보니 저처럼 푸신 분은 거의 없었습니다... 이걸 좋아해야하는지... 머리가 나쁜건지... 모르겠습니다... :( 일단, 타일 자체를 받는데 고민을 많이했습니다.기본 맵과는 다르게 홀수 줄에서는 N열, 짝수 줄에서는 N-1열이기 때문입니다. 저는 홀수줄은 1~2N번째 열을 입력 받았고, 짝수줄은 2~(2N-1)열을 입력 받아 칸마다 값들을 넣었습니다.또한 두 칸마다 하나의 타일이므로 2개씩 묶어 타일 번호를 지정해 주었습니다.(아래 자세..

#문제 https://www.acmicpc.net/problem/15653 #풀이해당 문제는 이전에 풀어봤던 두 동전 문제와 비슷하게 풀었습니다. 두 문제 다 두개의 물체를 한번에 움직여야 했고, 판을 움직여 특정 한개의 물체만 뽑아내는 문제입니다.안풀어 보셨다면 두 동전이라는 문제도 풀어보시는 것을 추천드립니다. :)또한, 구슬탈출이란 시리즈가 많기 때문에 다른 구슬탈출도 풀어보도록 합시다! 해당 문제에서 주의 깊게 봐야할 것은 구슬의 움직임입니다.두개의 구슬은 기울여 움직이므로 기울인 방향으로 가지 못할때(벽에 부딪히거나, 탈출구에서 빠졌을때)까지 움직입니다.또한 겹치지 않기 때문에 움직였을때 조심해야합니다. 주어진 입력 예제를 통해 확인해 봅시다!####### #...RB# #.##### #......

#문제 https://www.acmicpc.net/problem/16197 #풀이해당 문제는 BFS로 풀었습니다.보통 저는 문제에서 "어디서부터 어디까지의 최단 거리를 구해라!" 라고 한다면 BFS 방식으로 문제를 풉니다.DFS로 풀어도 괜찮습니다! 다른 블로그에서는 DFS로 풀이를 하셨더라구요. DFS로 풀다 모르시면 구글링하시면 될 것 같습니다. :) 눈 여겨 볼 조건은 "이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다." 와"두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오." 입니다.조건들을 잘 보고 생각하며 코딩을 할 수 있도록 습관을 들입시다! 첫 번째로 두 동전이 어느 칸으로 움직였을때 버튼을 누른 수를 저장해야합니다.두개의 동전이..

#문제 https://www.acmicpc.net/problem/3019 #풀이저의 머리가 역시 안좋구나...하게 만든 문제입니다. 처음 풀이 방법은 맵을 직접 2차원 배열에 넣고, 그 안에서 주어진 블럭을 계속해서 만들어 확인하는 방법이었습니다.이렇게 할 경우, 블럭마다 그리는 방법이 전부 다르기 때문에 일일이 만들어줘야하며, 이차원 배열에 계속 그렸다 확인하고 지우고, 다시 그리고 지우고를 반복하는 상황이 만들어졌습니다..뭔가 아니다 싶어서 검색한 결과 세상 똑똑하신 분들이 많구나하는 생각을 하게 되었습니다.. 일단 방법은 이러합니다. 먼저 쌓으려는 블럭의 밑바닥의 높이를 알아합니다.여기서 밑바닥은 아래 그림과 같은 것을 의미합니다.위 그림과 같이 빨간 선이 있는 부분이 밑바닥입니다.여기서 왜!? 왜..

#문제 https://www.acmicpc.net/problem/15661 #풀이이 문제의 경우, 백트래킹을 이용하여 팀을 나누고 그 중에서 2명을 뽑아내는 식으로 하였습니다. 해당 문제를 어디서 많이 보았다 했는데 예전에 풀었던 것과 거의 비슷했습니다.혹시나 하여 링크를 달아드립니다.[BOJ 스타트와 링크] : https://www.acmicpc.net/problem/14889해당 문제와 거의 비슷하지만 한가지 조건이 추가가 되었습니다.바로 전체 인원이 홀수일 수 있다는것! 해당 조건 때문에 뽑을때 고려해야 할 개수가 늘어났습니다... :(전체 인원이 5명일때, 스타트팀이 2명 링크팀이 3명 또는 스타트팀이 3명 링크팀이 2명일 경우로 나누어지게 됩니다.따라서 홀수일 때는 2명과 3명 모두 뽑아주어야 ..