코딩테스트

[백준] 로봇 청소기

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 구현 문제입니다. 문제부터 간단하게 요약하면, 로봇 청소기가 아래의 규칙대로 움직일 때, 1. 현재 위치를 청소한다. 2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 2-1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 2-2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 ..

[백준] 연구소

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 구현과, bfs 문제입니다. 우선 문제부터 간단하게 요약하면, 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 다음과 같이 연구소가 있는데, 0,1,2는 각각 빈 칸, 벽, 바이러스를 나타냅니다. 이곳의 빈 칸중 세군데에 벽을 추가로 설치하여 바이러스가 퍼지지 않은 방의 갯수를 최대로..

[백준] 퇴사

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dfs 또는 dp를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 각각의 상담은 소요시간과, 받을수 있는 금액으로 구성되어 있습니다. 매일 상담이 있을 때, 상담을 통해 최대 수익을 얻는 경우의 최대 수익의 값이 얼마인지를 구해야 하는 문제입니다. dfs와 dp를 사용한 풀이 두가지 모두 설명해 보겠습니다. 방법 1. DFS를 이용한 풀이 문제의 조건처럼 상담이 아래 그림과 같이 주어진다고 생각해 봅시다. 우리는 매 상담에 대해, 이 상담을 할지 말지를 결정합니다. 간단한 예시로 1일차를 생각해봅시다. 1일차에 상담을 진행하..

[백준] 테트로미노

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net dfs방법과, 직접 구현하는 방식 두 방식으로 문제를 해결하였습니다. 총 두가지 풀이에 대해 설명해 보겠습니다. 우선 문제부터 간단하게 요약하면, 이렇게 4개의 정사각형으로 만들어진 조각들로 숫자들이 놓인 N x M 크기의 종이안의 합이 최대가 되는 경우의 값을 구하는 문제입니다. 실제로 문제를 읽어보는 것을 추천합니다. 총 두가지의 방법으로 해결하였는데 각각의 방법에 대해 설명해 보겠습니다. 방..

[백준] 주사위 굴리기

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 가로가 N, 세로가 M인 지도에서 규칙대로 주사위를 굴릴 때, (지도 밖으로 주사위가 나가는 경우에는 안굴립니다.) 굴리는 것에 성공 한 경우, 주사위의 가장 윗면에 적힌 숫자를 출력하는 것이 문제입니다. 실제로 문제가 조금 기니 한번 읽어보는 것을 추천합니다. 주사위의 전개도를 ..

[백준] 연산자 끼워넣기

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net dfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N개의 수와, N-1개의 연산자가 주어지면, 연산자를 적절하게 배열하여, 앞에서 부터 계산하였을 때, 최댓값과 최솟값을 return해야 하는 문제입니다. (이 때, 연산자는 +,-,*,/ 가 있습니다. 또 N개의 수의 위치는 고정되어 있다고 가정하고, 연산자의 위치만 바꾸어야 합..

[백준] 상어 초등학교

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 학생들을 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다. 다..

[백준] 불 끄기

https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 일종의 brute forcing하는 문제인데 규칙성을 찾아 횟수를 줄여야 하는 문제입니다. 우선 문제부터 간단하게 요약하면, #O######## OOO####### #O######## ####OO#### ###O##O### ####OO#### ########## ########O# #######OOO ########O# 다음과 같이 10 x 10의 array에서 O는 불이 켜져있음을 의..