본문 바로가기

삼성SW역량5

13460 구슬 탈출 2 삼성 SW 역량 문제. 방향이 4방향이니까, 한 방향에 대해서 깊히 생각해보고 구현하면 나머지는 비슷한 방법이다. 그래서 코드도 비슷하지만, 길어진 코드가 되었다. 총평 - 모든 경우의 수를 세는 dfs는 잘 구현했다. - dfs 기저조건에서, 최솟값을 구하는 방법을 이제는 낯설어 하지 말자. - 결국, 시뮬레이션의 디테일한 구성사항을 논리적 오류없이 구현해야하는 것이 중요했다. - 반례들을 몇 십 차례 적용해 본 결과로 논리적 허점을 찾고, 수정하여 답을 얻었다. - 문제였던 곳은, 빨간공과 파란공이 같은 선 상에 있을 때, 움직인 후 겹치지 않게 처리하는 부분이었다. 이 부분을 알고리즘 처음 짤 때부터, 신중히 생각하고 만들었으면, 더 좋았을 것 같다. #include int N, M; char a[.. 2019. 10. 6.
16236 아기상어 시뮬레이션 문제를 해결해보자. 맵이 주어지고, 탐색을 할 경우에 dfs를 쓸 것인지, bfs를 쓸 것인지 고민이 된다. bfs가 dfs를 아우르는 개념이라서 보통 bfs를 쓰면 되는데, 특히 최단경로 문제(가중치가 없을 때)일 때는 bfs를 써야한다. 이 때, visited[][] 대신, dist[][]를 이용하면서 최단경로도 저장하고, 방문했는지도 체크할 수 있다. 처음에 문제를 이해하느라, 시간을 많이 썼지만 차근차근 이해하고, 배운 개념을 써먹으면 문제가 풀린다. 시간복잡도는 모든 물고기 O(V)에 대해 한번 잡아먹을 때마다 다음 잡아먹을 물고기 모두를 탐색해야 하므로 O(|V| + |E|)가 걸린다. O((20 x 20) x (20 x 20 + 19 x 20 x 2) ) = 464,000이 걸린다.. 2019. 9. 29.
16234. 인구이동 삼성 SW역량 테스트 기출문제. BFS를 사용하는 완전탐색 문제이자, 주어진 규칙을 잘 구현하는 시뮬레이션 문제이다. 문제 그대로만 하면 된다. BFS의 결과로 최소 신장트리(Minimum spanning tree)가 나오는데, 그 트리가 바로 하나의 연합이다. 처음에 문제를 보고, 하루에 연합이 2개이면 인구이동도 2번인가 했었는데 아니었다. 하루에 인구이동이 일어났으면 연합의 개수에 상관없이 그냥 인구이동이 한번 추가 되는 것이다. 무튼, 연합이 만들어지면, 그 node들을 하나의 vector에 저장해놓고, 인구이동값을 각 node에 대입해주면 된다. 그래서 코드는 크게 bfs()와 immigrate()로 나뉜다. #include #include #include #include using namesp.. 2019. 9. 28.
17143. 낚시왕 시뮬레이션 문제. 처음엔 쉬울 줄 알았지만, 하나하나 구현하며 오류가 많아 실제로 푸는데는 꽤 오래걸렸다. 해결방법은 문제에 주어진 대로 코드를 쭉 구성해가면 된다. 우선, 시간복잡도를 계산했을 때, 0 낚시왕이 모든 열을 걸어가는 시간 O(N) 1 낚시하는 시간(모든 행을 살핌) O(N), 2 맵을 다시 만드는 시간 O(N^2), 3 모든 상어에 대해 O(N^2) 3-1 상어가 이동하는데 걸리는 시간 O(N) 따라서 최악은 O(N^4)이 걸린다. 100x100x100x100 = 1억이므로 시간 내에 해결이 가능하다고 생각했다. 상어가 있는 물을 w[101][101]로 만들고, 1. 낚시왕이 오른쪽으로 한 칸 이동한다. C(column)을 바꾸어가며, 2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일.. 2019. 9. 24.
14889. 스타트와 링크 사람은 총 N명, 최대 20명 이를 순열로 늘어 놓아서 앞에는 스타트팀, 뒤에는 링크팀으로 하면 중복계산도 상당히 많고, 총 경우의 수는 20! = 상당히 큰 수이다 >>>>>>>>>>>> 1억 당연히 시간초과가 난다. 문제를 풀면서 자연스럽게 생각할 수 있는 것은 사실 조합이다. 20C10 는 10! 보다 작을 것이라는 것을 예측할 수 있는데 실제로 그 결과는 10!(3백만)보다 훨씬 작다. 18만정도이다. 여기에 각 팀 스코어를 계산해야하는 시간이 (N/2) x (N/2) 이므로 100이라고 하면, 1800만 < 2초 안에 가능하다. 내가 맨 처음에 한 것은, 예를들어 1, 2, 3을 뽑았으면 총 1, 2, 3, 4, 5, 6 인 set에서 1, 2, 3을 뽑는 것이다. 즉 4, 5, 6을 만드는 것.. 2019. 9. 21.
728x90