본문 바로가기

알고리즘 문제 풀이

(15)

[삼성 기출 문제] 백준 16236 아기 상어 문제 링크 어떻게 풀까? 시뮬레이션과 BFS가 함께 공존하는 혼돈의 문제입니다. 문제의 조건에 맞게 세세하게! 아주 세세하게! 잘 만들어야 합니다.개인적으로, 시뮬레이션이면 구조체를 활용하는 방법을 추천드립니다. 문제에 굉장히 햇갈리는 조건들이 많이 있습니다. 1. 아기 상어는 입력에서 9로 주어진다. (어려운 조건은 아니지만, 이것 때문에 고생을 많이 해서 올립니다.)2. 아기 상어는 처음에 크기가 2이다.3. 아기 상어는 자기보다 작은 물고기만 먹을 수 있다.4. 아기 상어는 자기보다 크기가 큰 물고기가 있는 칸은 지나갈 수 없다.5. 아기 상어는 다음과 같은 조건에 맞춰서 이동한다.- 아기 상어가 먹을 수 있는 물고기가 없으면 엄마에게 도움을 요청한다! (귀엽..)- 먹을 수 있는 물고기가 1마리라..

[삼성 기출 문제] 백준 15683 감시 문제 링크 어떻게 풀까? 이 문제는 여러 개의 카메라를 돌려서 카메라의 영역에 들어오지 않는 부분(사각 지대)을 찾는 문제입니다.시뮬레이션이면서 완전 탐색의 성격을 모두 갖추고있죠! 카메라를 돌리는 것에서 다양한 방법이 있을 수 있습니다.문제를 풀기전에 1. 카메라를 어떻게 돌릴지, 2. 카메라가 비추는 영역을 어떻게 표시할지 에 대해서 생각해 봅시다. 첫 번째로, 카메라를 어떻게 돌릴까? 입니다. 보시면, 카메라는 총 5가지 종류가 있습니다.1번 카메라는 90도씩 돌린다고 하면 총 4개의 다른 부분을 보는 영역을 만들 수 있겠죠! 이렇게 4개의 방향을 만들 수 있죠!이와 비슷하게 2번은 2개, 3번은 4개, 4번도 4개, 5번은 1개의 서로 다른 방향을 만들 수 있습니다. (csize)또한, 화살표의 ..

[삼성 기출 문제] 백준 14890 경사로 문제 링크 어떻게 풀까? 이 문제의 핵심은 '경사로를 어떻게 놓으면 될까?'에 대한 결정을 하는 것입니다. 문제에경사로의 가로 길이가 2라고 하겠습니다. 땅의 상황은 위와 같다고 하겠습니다. 아래와 같은 경우는 경사로가 설치된 곳에 중복으로 경사로를 설치했기 때문에 나타나는 문제입니다! 이 문제를 해결하기 가장 좋은 방법은 해당 좌표에 이미 경사로가 설치되었는지를 나타내는 bool 배열을 이용하는 것입니다. 해당 지점에 최초로 경사로를 만들면, 해당 자리를 true로 만듭니다. 다음에 또다시 해당 지점에 경사로를 만들려고 한다면, 경사로를 만들 수 없는 것입니다! 위의 그림을 봅시다. 위의 그림은 경사로가 지어지는 도중에 겹쳐지는 곳이 있어서 결국 경사로를 짓지 못한다는 처리를 해줘야합니다. 하지만, 경..

[삼성 기출 문제] 백준 14888 연산자 끼워넣기 문제 링크 클릭시 문제로 이동합니다. 어떻게 풀까? 다행히도 연산자의 우선 순위가 모두 같기 때문에, 앞에서부터 차례차례로 처리하면 됩니다! 그리고, 더하기, 빼기, 곱하기, 나누기 연산의 개수가 나옵니다.그렇다는 것은, 현재 계산된 수에서 다음 수를 더하기, 빼기, 곱하기, 나누기 중 하나를 선택하고, 다음 수와 계산한 뒤에, 이렇게 계산된 수와 최댓값, 최솟값을 비교해서 계속 갱신해줍시다. 이렇게 모든 경우의 수를 다 구해서 저장된 최댓값과 최솟값을 출력하면 문제의 답을 출력할 수 있습니다! 3 3 4 5 1 0 1 0 위 예제를 통해서 한번 살펴봅시다. 처음에 더하기의 개수가 존재하기 때문에, 더하기의 개수를 하나 깎은 후에 3과 4를 더합니다. 다음에 더하기와 빼기의 개수가 0개이므로, 이 부분들..

[삼성 기출 문제] 백준 14502 연구소 문제 링크 클릭시 이동합니다. 어떻게 풀까? 문제를 크게 2 부분으로 나눠야 합니다. 1. 벽을 3개 세우는 부분2. 바이러스를 퍼뜨리는 부분 1번은 dfs를 이용해서 조합을 이용해서 해당 좌표에 벽을 세운다 or 안세운다 의 동작을 통해서 모든 구역에 벽을 3개씩 세워보는 방법을 이용합니다. 그리고 벽을 3개 세웠을 때, bfs를 이용해서 2번을 동작해서, 바이러스의 개수를 세서 이 최댓값을 출력하면 풀이는 완료됩니다! 2차원에서 조합을 이용하는 방법을 알아봅시다! n = 3이라고 하겠습니다. 시작은 (0,0) 입니다.우선, (0,0)에 벽을 세울지 안 세울지 정합니다. 우선 세운다고 가정하겠습니다. 그럼, 열의 크기를 1 늘려준 뒤에 해당 위치에서 다시 위의 과정을 반복합니다.이번에는 안세운다고 하겠..

[삼성 기출 문제] 백준 3190 뱀 문제 링크 클릭시 이동합니다! 어떻게 풀까? 대표적인 시뮬레이션 문제입니다.시뮬레이션에서 가장 중요한 것은 순서를 아주 잘 파악해야 한다는 것입니다. 이 문제의 경우에는 순서가 다음과 같습니다. 1. 몸길이를 늘린다.2. 사과가 있으면 사과가 없어지고, 꼬리는 움직이지 않는다.3. 사과가 없다면 몸길이를 줄여서 꼬리가 위치한 칸을 한 칸 비운다. 입니다. 위에 안나와 있어서 햇갈리는 부분은 바로 머리의 회전 입니다. 입력에서 보면, 머리 회전에 관해서 X와 C가 나오는 것을 볼 수 있습니다.그리고, X가 끝난 후에 회전하는 것을 알 수 있습니다! 죽는것은, 벽에 닿거나 뱀의 몸에 닿는 경우이죠. 즉, 모든 조건을 추가하면, 1. 몸길이를 늘린다.2. 사과가 있으면 사과가 없어지고, 꼬리는 움직이지 않는다..

[삼성 기출 문제] 백준 12100 2048 (easy) 문제 링크 클릭시 문제로 이동합니다. 어떻게 풀까? 해당 문제는 크게 2 부분으로 나눌 수 있습니다. 1. 재귀를 이용하여 블록을 위/아래/왼쪽/오른쪽 으로 최대 5번 이동시키는 부분2. 이동시켜서 최댓값이 어떻게 되는지 알아내는 부분 이 중, 1번은 2차원 배열 restore[][]를 이용하면, 기존의 맵을 저장하고 복구하면서 맵을 5번까지 이동시키는 방법으로 구현할 수 있습니다. 가장 중요한건 2번이죠! switch를 쓰면 비슷한 방법을 4번 반복해야하기 때문에, 짧게 이를 해결하는 방법을 소개해드리겠습니다.(물론, 실전에서 이 방법까지 생각하려면 힘들겠지만, 그래도! 여긴 블로그니까요!) 우선, 기본적으로 블록을 이동시키는 방법은 덱을 이용하는 것입니다.덱의 맨 뒤의 수와, 현재 맵에 적혀있는 블록..

[삼성 기출 문제] 백준 13460 구슬 탈출 2 문제 링크 클릭시 문제로 이동합니다. 어떻게 풀까? 우선, 맵의 크기를 확인해 봅시다! 10 * 10의 맵의 크기를 가집니다. 그리고, 빨간 공과 파란공 2 가지 경우가 있죠. 그 말인 즉슨! 4 차원 배열을 통해서 [빨간공의 행][빨간공의 열][파란공의 행][파란공의 열] 형태로 visit 처리를 만들 수 있고,이를 통해 bfs를 이용하면 구슬을 빼낼 수 있는 최단 시간을 출력할 수 있습니다! 큐 에는 빨간공의 위치와 파란공의 위치를 넣으면 되겠죠! 10번이 넘어가면 -1을 return 하면 되겠군요! 그럼, 판을 상, 하, 좌, 우로 움직일 땐 어떻게 하면 될까요?그저 공의 위치를 저장해 놓고, 오른쪽으로 이동하면서 벽이 만나는 경우 그 전의 위치에다가 공을 위치시키기만 하면 됩니다!아래의 경우를 보..

이전 1 2 다음

티스토리툴바