이번 시간에는 2주동안 삼성 기출 문제와 비슷한 난이도를 가진 구현 문제들을 풀어볼 예정입니다.
시뮬레이션 1
삼성 역량테스트, A형 문제에 나오는 알고리즘 유형은 크게 4가지로 나눌 수 있습니다.
시뮬레이션
그래프 알고리즘(BFS, DFS, 플러드 필)
순열과 조합
재귀(백트래킹, 일반 재귀)
문제 유형은 한가지씩만 나오는 것이 아니라 이 네 가지를 적절히 섞어서 출제하고 있습니다. 요즘 추세는 역량 테스트에서는 까다로운 1+2 문제가 나오는 편이고, A형은 1, 2, 3이 섞어서 나오는 편으로 역량 테스트보다는 쉬운 편입니다. 그리고 역테, A형 모두 가끔가다 4번 유형이 나오는 편입니다.
이번 시간에는 쉬운 문제 2개, 그리고 앞에 두 문제보다 좀 더 까다로운 문제를 2개 풀어보겠습니다.
아래에 힌트를 적어 두었으므로 혼자 문제를 풀지 못하겠다면 문제 유형과 힌트를 참조하고, 힌트로도 풀지 못하겠다면 풀이를 보시면 됩니다.
미리보기 방지
치킨 배달: 순열과 조합
파이프 옮기기 1: 재귀
상어 초등학교: 시뮬레이션
Puyo Puyo: 플러드 필, 중력
치킨집의 좌표를 모두 저장하고, 이중에서 m개 선택하기(조합 사용)
집의 좌표를 모두 구해서 m개의 치킨집 중에 가장 가까운 거리를 구해서 더해주기
현재 파이프의 끝 위치가 [x, y]라면
→ 방향은 [x, y+1]에 벽이 없어야 함
↘ 방향은 [x+1, y], [x, y+1], [x+1, y+1]에 벽이 없어야 함
↓ 방향은 [x+1, y]에 벽이 없어야 함
파이프가 목적지 [n-1, n-1]에 도착하면 정답에 1을 더해줌
이것을 이용하여 재귀 함수를 구현
(x, y)에서 상하좌우 자리만 인접
입력 값을 받을 때, 2차원 리스트로 입력 값을 받음
(0, 0)부터 (n-1, n-1)까지 for문을 돌려 좋아하는 학생이 가장 많은 칸을 찾음(queue에 저장함)
2번이 여러 개라면 for문을 돌려 인접한 칸중에서 비어있는 칸이 많은 칸을 찾음(while(!q.empty)를 이용하여 2번에서 저장한 queue에서 원소를 뽑아내서 확인하기)
본문에 나온 3번 조건은 우리가 이미 (0, 0)에서 시작해서 행의 번호가 가장 작은 칸, 열의 번호가 가장 작은 칸에 맞게 for문을 구현하면 정렬을 하지 않아도 상관 없음