시뮬레이션 Ⅰ
시뮬레이션
2차원 리스트
자주 사용하는 모듈
순열과 조합
재귀 함수 Ⅰ
재귀 함수 Ⅱ
그래프 알고리즘 소개
플러드 필
시뮬레이션 Ⅰ - 현재 글
시뮬레이션 Ⅱ
이번 시간에는 2주동안 삼성 기출 문제와 비슷한 난이도를 가진 구현 문제들을 풀어볼 예정입니다.
시뮬레이션 1
삼성 역량테스트, A형 문제에 나오는 알고리즘 유형은 크게 4가지로 나눌 수 있습니다.
1.시뮬레이션
2.그래프 알고리즘(BFS, DFS, 플러드 필)
3.순열과 조합
4.재귀(백트래킹, 일반 재귀)
미리보기 방지
치킨 배달: 순열과 조합
파이프 옮기기 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문을 구현하면 정렬을 하지 않아도 상관 없음
필요한 내용: 중력(https://www.acmicpc.net/problem/13986)
플러드 필을 이용하여 연결된 뿌요들이 몇 개인지 확인. 이때 좌표들을 큐에 저장하면서 찾음
뿌요가 4개 이상이면 큐에 있는 좌표들을 하나씩 빼고 빈 공간('.')으로 만들어주기
중력 효과 넣어주기
1 ~ 3을 반복하다가 더 이상 연결된 뿌요가 4개 미만인 것만 있으면 루프문을 벗어남
Last updated