https://www.acmicpc.net/problem/14889

삼성 코딩 테스트 기출 문제이다.

시뮬레이션 + 조합 으로 해결하였다.

풀이

플로우는 다음과 같다.

1. 팀을 배분한다.
2. 배분한 팀 각각의 능력치의 합을 구한다.
3. 두 팀 간의 능력치 차이를 구한다.

우선, 팀을 배분하는 방법부터 보자.

총 6명이 있다고 하자 : 1번, 2번, 3번, 4번, 5번, 6번

6명이므로 3명 / 3명으로 팀을 나누어야한다.

1번은 5명 중 2명과 팀을 이룬다. 즉, ₅C₂

https://www.acmicpc.net/problem/15685

삼성 코딩 테스트 보러 가서 풀지 못한 문제이다. 시뮬레이션 문제이다.

풀이

우선 규칙을 찾아야한다.

시작점이 (4,2), 첫 시작방향이 북쪽(1), 차원이 3차원을 그림으로 그려 확인해보자.

이를 숫자를 이용해 테이블로 나타내면 다음과 같다.

위의 테이블에서 알 수 있듯이, n차원의 요소들은 n-1차원의 요소들을 그대로 가지고, +1씩 더한 요소들을 추가적으로 가진다.

여기서 중요한 것은, 남쪽 방향(3)은 다음 차례에서 동쪽 방향(0)으로 추가된다

https://www.acmicpc.net/problem/4991

삼성 알고리즘 시험 보러 가서 못 푼 문제이다.

1. 다시 푸는데 오랜 걸렸다. ( 2018.08.01 ) : 조합 + BFS
2. 다시 푸는데 30분도 안걸렸다. ( 2018.10.01 ) : DFS

첫 번째 풀이

1. 치킨집 K개 중에 M개를 고르는 경우의 수를 구한다. (조합)
2. 선택되지 않은 치킨집은 빈 칸으로 만든다.
3. 각 집을 출발점으로 가장 가까운 치킨집까지의 거리를 구한다 (BFS)

첫 번째 풀이 예시

• 다음과 같이 치킨집이 3개가 있다고 하자.
  • 0번 치킨집
  • 1번 치킨집
  • 2번 치킨집
• 최대 2개의 치킨집을 선택하는 경우의 수는 다음과 같다.
  • 0번, 1번 — A
  • 0번, 2번 — B
  • 1번, 2번 — C
• A를 생각해보자.
  • 2번이 선택되지 않았기 때문에, 2번 치킨집을 폐업 시킨다.
  • 각 집의 위치에서 BFS를 실행한다. 이는 각 집에서 가장 가까운 치킨 집과의 거리를 구하기 위함이다.
• B, C도 위와 같은 작업을 반복한다.

두 번째 풀이

1. 치킨을 선택하여 List에 저장한다. (DFS)
2. 각 집에서 선택된 치킨집 까지의 거리를 계산한다.

치킨집이 A, B, C, D 네 개 있고, 최대 3개 선택을 한다고 했을 때, DFS는 다음과 같이 진행된다.

https://koitp.org/problem/SDS_TEST_SPACE/read/

오답

BFS 로 풀었을 때는 메모리 초과가 뜬다.

해결

시뮬레이션으로 풀면 해결된다.

• 1번
  • 돌아가지 않고 직접 가는 경우이다.
  • 시작점과 도착점 사이의 절대값을 구한다.
• 2번
  • 돌아가는 경우이다.
  • 행과 열의 대소 비교를 통해 구한다.

https://koitp.org/problem/SDS_TEST_SURVIVOR/read/

풀이

이차원 배열을 순차탐색하여, 해당 index와 주변 8개의 값을 체크한다.

쉬운 문제인데, 오랜만에 알고리즘 문제를 푸니 오래걸렸다.