https://www.swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy [D4]

정답 풀이

1. 모든 판에 콩을 심었다고 가정하고 시작한다.

2. 콩이 심은 판 사이의 거리가 2이면 콩을 지운다.

   

   위의 그림처럼, 빨간색 원이 기준이 된다.

   기준을 중심으로 길이가 2인 판에 콩이 있으면 콩을 없앤다. 파란색 네모 부분이 길이가 2인 지점이다.

   그리고 기준을 다음 칸으로 옮겨서 같은 작업을 반복한다.

정답 코드

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE

SW Expert Academy [D2]

쉬운 문제였지만, 시간 초과가 나서 다시 풀었다.

오답 풀이

i 날에 샀다면, x(>i) 날에 팔아 이득을 챙기면 된다.

여기서 포인트는 max(이득(x)) 를 찾아야 한다는 것이다. 다음의 식을 얻을 수 있다.

sum += max(이득(x)) - 이득(i)

내가 풀이한 코드는, 루프를 두 개 돌리는 것이다. 이렇게 하면, 시간 초과가 발생한다. O(N^2)

정답 풀이

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE

SW Expert Academy [D2]

쉬운 문제이다.

풀이

i번째 빌딩에서 조망권이 확보 되는 세대는 다음과 같은 조건을 충족시킨다.

1. i번째 빌딩 높이 > i-1번째, i-2번째, i+1번째, i+2번째 빌딩 높이

2. 세대 수 = i번째 빌딩 높이 - max( i-1번째, i-2번째, i+1번째, i+2번째 빌딩 높이)

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

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

BFS로 풀었다. 계속 틀렸다고 나온다.

그래서 DFS로 다시 풀었다.

DP 로도 풀 수 있다고 한다.

예시

다음의 예시로 설명하겠다.

BFS 오답 풀이

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

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

시간 초과가 났다.

오답 풀이

다음의 예를 보자.

숫자 : 1 2 3 4 5 6

연산자 : 2 1 1 1

따라서 연산자는 다음과 같다.

+, +, -, *, /

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

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

시뮬레이션 문제이다.

시간이 많이 걸렸지만, 쉬운문제였다.

풀이

다음 톱니바퀴 상태를 예로 들자.

이를 테이블로 나타내면 다음과 같다.

위의 테이블에서 같읕 색깔의 네모로 체크 된 것이 맞닿는 부분이다.

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

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

시뮬레이션 문제이다.

풀이

1. 행을 모두 체크한다.

   • i행의 j열은 세 가지 경우로 나뉜다.

     • j+1열과 같은 높이
       • j+1열을 체크한다.
     • j+1열 높이보다 1작음
       • 왼쪽 방향으로 경사로를 세울 수 있는지 체크한다.
       • 다음 그림과 같이 1번 지점은 j+1열 높이보다 1 작기 때문에 2번 방향으로 체크한다.

     

     • j+1열 높이보다 1높음
       • 오른쪽 방향으로 경사로를 세울 수 있는지 체크한다.
       • 다음 그림과 같이 1번 지점은 j+1열 높이보다 1 높기 때문에 2번 방향으로 체크한다.

   

2. 열을 모두 체크한다.

   행을 체크하는 경우와 동일하다.

코드로 옮기는 것이 쉽지 않아 해설을 보고 해결했다.

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는 다음과 같이 진행된다.