케이스윔의 개발 블로그

문제 정의로봇 청소기의 주어진 작동방법을 통해서 청소하는 영역의 개수를 구하는 프로그램을 작성하는 것이다.로봇 청소기는 다음과 같이 작동한다.현재 위치를 청소한다.현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며,..

문제 정의벽을 3개 세워서 연구소의 바이러스(2)가 최대한 작게 퍼지도록 하여서, 안전영역 크기의 최대값을 구하는 문제이다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14502) 문제 풀이 이 문제도 저번에 풀다가 실패해서 며칠만에 다시 푸는 문제다. 지도의 크기는 8*8보다 작으므로 3개의 벽을 모두 세워보고 바이러스가 퍼지지 않는 안전 영역을 구해서 최대값을 갱신하도록 한다. 이 문제는 꽤 오래전에 풀었던 문제라서 DFS를 잘 활용하지 못해서 못풀었던 것 같기도하고.. 벽을 세운다음 바이러스를 퍼지게하고, 그 때마다 안전영역의 크기를 구하도록 구현한다. 몇시간을 잡고 있었는데 벽을 세우는 DFS를 완전히 구현하지 못했다. 내가 생각하는 로직으로는 구현이 잘..

문제 정의직사각형 보드를 왼쪽, 오른쪽, 위쪽, 아래쪽으로 기울이는 4가지의 동작을 통해서 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지를 구하는 문제이다. 단, 파란 구슬이 구멍을 통해 나오면 안된다. 문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/13460) 문제 풀이2048(Easy)이랑 비슷한 문제 인 것 같다. 대신 최소 몇번인지를 구해야하므로, 계속해서 여러 방향으로 탐색을 하다가 빨간 구슬이 구멍을 통해 빠져나가면 탐색을 그만하도록 한다. 며칠 전에 풀다가 잘 안풀려서 다시 풀었는데, 그 때와 똑같이 잘못된 방식을 구현해버려서 시간이 너무 많이 소요됐다. DFS와 백트래킹을 통해서 계속해서 여러 경우를 탐색하는데, 빨간 구슬과 파란 구슬의..

문제 정의매초마다 이동하는 뱀을 계산하는 문제이다. 이동한 칸에 사과가 있을 경우에는 한칸 몸을 늘리고, 아닐 경우는 늘어나지 않고 주어진 초마다 주어진 방향으로 이동해서 벽 또는 자기자신의 몸과 부딫힐 때까지 이동한다.문제 출처 : 백준 온라인 저지(https://www.acmicpc.net/problem/3190) 문제 풀이문제를 읽자마자 난해하고 어렵다고 생각했다. 뱀은 1초마다 이동을 하고 주어진 초가 되면 방향을 바꿔야 한다. 뱀의 길이를 저장하기 위한 변수가 필요하다. 오른쪽으로 향하는 함수와 왼쪽으로 향하는 함수를 통해서 초마다 이동시키면서 문제를 풀면될 것 같다. 문제가 충격적이다. 설명이 너무 부족하게 되어있다. 방향은 오른쪽과 왼쪽으로 주어져서 한 행안에 머무는건가 생각했는데, 진행방향..

문제 정의 N*N의 보드에 주어진 숫자만을 통해서 2048 게임 방식을 따라 최대 5번 이동해서 만들 수 있는 가장 큰 블럭의 값을 구하는 프로그램을 구현하는 것이다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/12100) 문제 풀이움직일 수 있는 방향은 상하좌우 총 4개이다. 최대 5번 이동해서 숫자를 크게 만들기 위해서는 4개의 방향에서 중복을 허용해서 순서를 가지는 5개의 방향을 고르는 모든 경우를 탐색하고, 만들어지는 최대 숫자를 출력한다. 총 4의5승의 경우가 나온다. 모든 경우에 밀어줘서 다 계산을 했는데 내가 고려하지 않은 부분이 너무 많았다. 처음에 짠 코드에서는 i와 i+1만 비교를 해서 옆에 있는 수와 같은지만 확인을 해버렸다. 8 0 0 8 ..

문제 정의한 행 또는 한 열의 한쪽 끝에서 다른쪽 끝까지 지나갈 수 있는 길의 개수를 구하는 문제이다. 주어진 조건에 맞춰서 경사로를 세워서 길을 지나가게 할 수 있다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14890) 문제 풀이일단 N의 범위가 2에서 100이므로 꽤 큰 편이다. 우선 다 같은 수를 가지는 한 행, 한 열의 경우는 경사로가 필요없이 지나갈 수 있는 길이므로 for문을 통해 간단히 체크를 할 수 있다. 체크를 하는 과정에서 만약 같은 높이가 아니라 낮아지거나 or 높아진다면 그 때 경사로를 놓아본다. 경사로의 길이가 L이므로 한 칸씩 높이를 보면서 L만큼 길이가 있고, 경사로를 통해 지나갈 수 있는 길이 되는지를 판단할 수 있다. 이 문제를..

문제 정의총 N개의 시험장이 있고, 각 시험장에 있는 응시자의 수가 A[i] 일 때, 총감독관은 한 방에서 감시할 수 있는 응시자가 B명이고, 부감독관은 C명일 때, 필요한 감독관 수의 최소값을 구하는 프로그램을 구현하여야 한다. 문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/13458) 문제 풀이어려워보이진 않은 것 같은데.. 정답 비율은 24%로 낮은 편인 것 같다. 각 시험장에 응시자를 감독할 수 있는 최소한의 감독관 수를 구해야 하는데 각 시험장에 총감독관은 오직 1명이고, 부감독관은 여러 명이 있어도 된다는 조건이 있다. 예제 입출력을 보면 대부분 총감독관이 적은 응시자를 감독할 수 있긴한데, 둘 중에 더 큰 감독관을 먼저 배치해서 필요한 감독관의 수를 ..

문제 1*1인 정사각형을 여러 개 이어서 붙인 도형을 폴리오미노라 하는데, 이 폴리오미노를 4개 붙인 것을 테트로미노라 한다. N*M인 종이 위에 테르토미노를 하나 놓아서 각 칸의 적혀진 수의 최대 합을 구하는 문제이다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14500) 문제 풀이삼성 sw 역량 테스트 문제집에 있는 문제들만 풀고 있는 중인데, 이 문제는 다른 문제와 다르게 N, M의 값이 500이하라서 완전탐색이 불가능 할 것 같다는 생각이 들었다. 다 놓아서 가장 큰 값을 구하려면 500개에서 4개를 뽑아야하기때문에 방법을 좀 더 생각해봐야겠다. 우선순위 큐를 사용해서 BFS를 하면 큰 값들을 찾아갈 수 있지 않을까.. visited[i][j]를 둬서 ..