공부정리

삼성 SW역량테스트 문제이다. *작년 이문제를 풀어 면접을 봤었다...* 링크 : https://www.acmicpc.net/problem/15686 DFS(조합)를 사용해서 가능한 치킨집을 선별하여 문제에서 요구하는 거리의 합이 가장 작은 결과값을 출력하는 문제이다. 치킨집과 배달할 집의 좌표를 저장하고 선별한 치킨집에 따라 가까운 집을 선별하여 최단거리로 갈 수 있는 조합을 계속 갱신하면 답을 얻을 수 있다. next_permutation() 함수를 사용했지만, 일반 재귀 DFS로도 구현 가능하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616..

삼성 SW역량테스트 기출문제이다. 출처 : https://www.acmicpc.net/problem/16236 이 문제는 BFS+문제의 요구사항에 맞는 구현 능력이 있다면 해결할 수 있다. 처음엔 문제를 읽어도 '뭐 어떻게 하라는 거지' 생각에 문제 이해하는데 시간이 오래 걸렸다. 필자가 언어이해력이 떨어진 것이 문제일 수도 있겠지만 어째뜬, 2번째 테스트케이스를 손으로 그려가며 문제를 이해할 수 있었다. 이 문제는, 상어의 위치, 크기, 먹을 수 있는 물고기 이 3가지를 저장하는 자료구조를 이용하여 BFS탐색을 통해 진행한다. BFS탐색을 하면서 먹을 수 있는 물고기의 위치로 모두 이동하고 그 수가 많다면 문제의 조건에 맞게끔 먼저 먹는다. 그 다음 상어의 위치를 갱신하고 그 위치에서 계속 BFS탐색을..