Algorithm/삼성 SW기출문제2 [백준] 14889 스타트와 링크 dfs(백트래킹)을 이용해서 만들 수 있는 모든 조합의 경우를 다 따지는 문제이다. 처음엔 조합을 이용한 브루트포스이겠거니 생각했지만 조합을 어떻게 구현하는지 생각이 안났다.. 해서 dfs을 가지고 순열 및 조합을 구현하는 코드를 공부 한 후에 다시 문제를 풀었다. stl라이브러리 중 next_permutation으로 구할 수 있었지만, 시간복잡도가 너무 크기 때문에 직접 재귀로 구현하는 것이 낫다고 한다. 아래사이트를 참고해서 공부했다. https://paris-in-the-rain.tistory.com/35 순열, 조합 알고리즘 - DFS로 구하기(백트래킹), C++, Python 순열, 조합은 정말정말 많이 나오는데 cpp의 stl 라이브러리 중 next_permutation으로 구할 수 있다. 하.. 2022. 2. 24. [백준] 13460 구슬 탈출 2 생각하는 과정 1. R과 B가 동시에 한쪽으로 완전히 이동해야 한다. -> R과 B의 좌표와 기울인 횟수를 담은 Queue를 하나 만들자. -> 좌표의 4방향을 탐색하는 for문에서 방향 i를 공유하여 R과 B를 이동시킬 수 있을 때까지 이동시킨다. 2. 한쪽으로 기울였을 때 R과 B가 겹치는 상황이 발생한다. -> R과 B가 움직인 거리를 비교해서 움직인거리가 적은 구슬의 좌표를 증가(혹은 감소)시킨다. 3. 2번을 잘 해결했다면 방문체크를 한 후에(아직 방문을 안했다면) next좌표를 push해준다. (이때 count증가) 이렇게 되면 R,B를 R이 0을 찾을때까지 한쪽으로 계속 기울여 가면서 최소의 count를 얻어낸다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16.. 2022. 2. 22. 이전 1 다음
