전체 글
-
-
7396. 종구의 딸이름 짓기SWexpertAcademy 2020. 3. 6. 08:02
목표가 매우명확하게, 최 좌측 상단에서, 최 우측 하단으로 간다 라고 정해져있기 때문에, 하, 우로 가는 방향만이 필요했다. 다만, 여기서 주의할 점은 아이디어 부분이다. BFS로 했을때 가장큰 이점은 노드를 기점으로 동일한 가치를 가진 자식들을 전부 탐색한다는것이다. 다만, BFS를 쓸때 순차에 가치를 두지않고 바로바로 Queue에 넣고, 빼고를 반복하게 되면 이러하 순서에 대한 가치를 잃어버릴 가능성이 크다. 나같은경우, 동등한 가치의 queue를 전부 소진하면서, 그 가치에대한 최솟값만을 다음 값으로 넘길수 있게 해주었다.
-
5684. [Professional] 운동SWexpertAcademy 2020. 3. 5. 11:22
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRxnnah2sDFAUo&categoryId=AWXRxnnah2sDFAUo&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 사실 완전탐색을 해도될지 굉장히 고민이 많이됬던 문제다. 그럼에도 불구하고 N값이 400까지인 제한조건과, 자기자신으로 돌아가는 경우가 존재하기에 BFS방식을 통한 완전탐색으로 문제를 풀었다. 사실 제일 좋은 방법은 Dijkstra방식을 통해, 각 지점에서 모든 다익스트라를 구하는것 아닐까 싶지만, 들어오는 도시간 거..
-
[SWEA] 4534. 트리 흑백 색칠SWexpertAcademy 2020. 2. 29. 15:30
https://swexpertacademy.com/main/solvingProblem/solvingProblem.doSW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com아무리봐도 완전탐색으로 풀수없는 문제라고 생각했다일단, 완전탐색을 하게될 경우 시간복잡도는 자식노드들에 따라 기하급수적으로 늘어나는데, 예를들어가장큰 부모노드에서, 자식노드까지 가는 모든 경우의 수를 다 탐색하는 상황을 생각해보면,노드를 내려갈때마다 전부탐색해야하는 굉장히 복잡한상황이 나오면서, 트리이기 때문에 그러한 방향성 역시일정하지 않다는 문제점이 존재한다. 그래서, Dynamic Programming 을 생각했고, 처음에 생각한것은Dp[index]..
-
[BOJ - 12886] 돌 그룹백준알고리즘 2020. 2. 27. 00:39
https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다. 강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다. 크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 www.acmicpc.net 문제 논리자체는 딱.. 그 세자리 숫자에 관한 Memoization을 통해 BFS를 써주면되겠다! 라는 생각이들지만, 이러한 생각은 문..
-
[BOJ - 1405] 미친 로봇카테고리 없음 2020. 2. 27. 00:33
https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다. www.acmicpc.net 논리 과정 자체는 굉장히 간단한 문제다. DFS를 통해 이동할수 있는 모든 과정을 탐색해나가는 과정일뿐이지만.. 약간 약점이라고할수 있는 자릿수 관련된 문제가있는데.. 도저히 cout, cin으로 해결하기 힘들거같아서 scanf/printf 방식을 사용했다.
-
[BOJ - 16933] 벽 부수고 이동하기3백준알고리즘 2020. 2. 27. 00:30
https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 벽부수고 이동하기 4처럼 조금 이전 시리즈들과 다른문제는아니나, 하나 추가된것이 낮과 밤이라는 조건이 추가가됬다는것이다. 구조체를 구성하고, 낮과 밤일때 매커니즘을 다르게 만들어서 BFS를 진행했고 특이한점이 한가지 있다면, 밤일때 이동하고자 하는벽이 있는상태에 아직 벽을뚫을수 있다면 그자리에서 한턴기다리는 방식을 선택했다.
-
[BOJ - 16946] 벽 부수고 이동하기 4백준알고리즘 2020. 2. 27. 00:14
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다. www.acmicpc.net 이 문제에 대한 가장 간단하고 전형적인 완전탐색 방법은 모든 벽에서 모든 빈공간을 탐색해나가는 것이라고 생각했다. 하지만, 최대 벽의 개수가 1000x1000개인 100만개정도의 숫자가되는데, 이러한..