SWexpertAcademy
-
[SWEA - 4112]이상한 피라미드 탐험SWexpertAcademy 2020. 4. 24. 18:03
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHmLraeEwDFAUH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 전형적인 BFS문제다. 하지만, 이 문제를 어렵게 만드는 것이 있다면 아마 맵을 형성하는 부분일것이다. 우선 맵을 그리기 전에 쉽게 그리기 위하여 먼저 나는 규칙성을 찾았다. 첫째로 아래로 내려가면서 제일 왼쪽을 보면 1, 2, 4, 7, 11, 16, 22 ..... 이런식으로 진행되는 수열을 확인할수 있다. 이는 공차가 i로 주어지는 경우고 이를 알았다면 vector를 통해 각 줄에 필요한 만큼..
-
[SWEA] 1868. 파핑파핑 지뢰찾기SWexpertAcademy 2020. 4. 4. 15:10
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 특징이 한가지 있다. 8방향에 지뢰가 없는 안전지대에서 탐색을하면, 숫자가 있는것까지 탐색을하지만 그 지점을 기점으로 해서 queue에 집어넣고 탐색은하지않고 그자리에서 마친다는것이다 이점을 이용해 flood Fill 하면 된다.
-
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]..
-
-