오픈채팅방
https://www.welcomekakao.com/learn/courses/30/lessons/42888?language=java
2019 카카오 신입 공채 1차 코딩 테스트
풀이
HashMap으로 이름 변경 이력을 저장한다.
( key : id / value : name )
records 배열을 순회하며 리턴할 배열을 생성한다.
구슬탈출2
https://www.acmicpc.net/problem/13460
삼성 기출문제이다. 해설을 보고 이해하였다.
풀이
- 완전탐색이고 최소 횟수를 구하는 것이므로, BFS를 사용한다.
- 삼성 기출 문제 ‘2048’ 에서 블록 이동이 문제 해결의 관건이듯이, 이 문제 역시 공을 이동하는 것이 문제 해결의 관건이다.
구슬 이동 방법 : 상대 공을 무시하고 각자 공을 이동시킴
- B가 구멍에 빠지는 경우 : 큐에 넣지 않고 넘긴다
- B와 R이 겹치는 경우 : B와 R의 초기 상태를 확인해서 이동한다.
- 예를 들어, 동쪽으로 이동하는 경우, 초기에 B가 R의 왼쪽에 있었다고 하자.
- 그렇다면, B를 R의 왼쪽으로 한 칸 이동시켜야한다.
2048
https://www.acmicpc.net/problem/12100
삼성 기출문제이다. DFS 문제이다. 블록을 이동하는 것이 어려운 문제였다.
풀이
블록을 5번 이동 시키는 것은 다음 그림과 같이 DFS로 구현한다.
문제의 핵심은 블록을 이동하는 것이다. 블록 이동을 구현하기 위해 Queue를 사용한다.
뱀
https://www.acmicpc.net/problem/3190
삼성 기출문제이다. 쉬운 문제였다.
풀이
핵심은 뱀의 이동 흔적을 남기는 것이다. 이를 위해, Queue를 사용하였다.
뱀이 머리만 이동할 경우
- 이동할 위치를 Enqueue
뱀이 완전히 한 칸 이동할 경우
- 뱀의 시작점(Queue에 가장 먼저 Enqueue된 요소)을 Dequeue
시험감독
https://www.acmicpc.net/problem/13458
삼성 기출문제이다. 매우 쉬운 문제였다.
풀이
문제에서 주어진 대로 풀면 된다.
처음에 틀렸다.
ans 변수를 int로 선언하였을 때는 틀렸다고 나온다.
long 형으로 선언하였더니 맞았다.
코드
주사위 굴리기
https://www.acmicpc.net/problem/14499
삼성 기출문제이다. 쉬운 문제이다. 문제 이해만 잘 하면 된다.
풀이
문제의 핵심은 주사위를 ‘옮기는 것’ 아니라, ‘굴리는 것’이다.
다음 그림과 같이 처음 상태에서 동, 서, 북, 남으로 굴림에 따라서 방향에 대한 값이 바뀐다.
회전하고 문제에서 주어진 대로 풀면 된다.
사다리 조작
https://www.acmicpc.net/problem/14499
삼성 기출문제이다. DFS 문제이다.
어려웠다. 해설을 보고 이해를 했지만, 직집 해결해보기 위해 며칠 동안 붙잡고 있던 문제이다.
풀이
- 사다리를 어떻게 코드로 표현해야 하는지 파악한다.
- 사디리는 어디에 둘 수 있는지 파악한다.
- 탐색을 어떻게 진행할지 생각한다.
사다리를 코드로 표현하는 방법은 다음 그림과 같이 이차원 배열을 이용한다. 사다리를 1과 2로 표현한다.
사다리를 둘 수 있는 곳의 조건은 다음과 같다.
- i행의 j번째의 값과 j+1번째의 값이 0 : 연속되지 않고, 사다리를 둘 수 있는 빈 칸 이라는 의미
- j+1<=n : 동일한 행에 사다리를 둘 수 있다는 의미
테트로미노
https://www.acmicpc.net/problem/14500
삼성 기출문제이다. 매우 어려운 문제였다.
처음에, 도형의 모든 경우의 수를 하나 하나 놓아봐서 최대값을 구해야하는지 생각했다.
하지만, DFS로 해결할 수 있다.
풀이
다음 그림과 같이 DFS를 이용하여 최대한 깊이 탐색한다.
ㅗ 모양을 제외한 모양은 DFS로 탐색이 가능하다. 4개의 탐색(깊이 3) 까지 마쳤을 때, 최대값을 계산한다.
로봇청소기
https://www.acmicpc.net/problem/14503
삼성 기출문제이다.
매우 어려운 문제였다. 문제 이해 자체가 어렵다.
BFS로 해결할 수 있다.
풀이
현재 위치를 청소한다.
현재위치에서 바라보는 방향의 왼쪽 방향을 확인한다.
( 이 작업을 4번 진행한다. 그렇다면, 현재위치의 동서남북 모든 방향을 확인 할 수 있다.)
청소를 해야할 구역이고, 아직 방문하지 않았으면 방문한다.
네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진한다.
네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
다음 그림에서와 같이 처음 시작은 (7,4) 에서 시작하고, 방향은 북쪽(0)을 바라보고 있다고 하자.
최종 움직임은 다음과 같이 그려질 것이다.
감시
https://www.acmicpc.net/problem/15683
어려웠다. BFS로 시도하였지만, 실패하였다.
해설을 보고 DFS로 풀었다.
풀이
- 이전 감시 상태를 가져와 복사한다. (깊은 복사)
- 감시 가능 지역을 표시한다.
- 다음 cctv를 탐색한다.
탐색 순서를 설명하기 위해 다음 표를 보자.
위의 표에서 감시 카메라는 A, B, C 세 개가 있다.
A와 B 는 상하 / 좌우 를 감시할 수 있고, C는 상하좌우를 감시할 수 있다.
탐색 순서는 다음 그림과 같이 나타낼 수 있다.