컴퓨터 공학 기초
-
백준 17837 (새로운 게임 2)컴퓨터 공학 기초/알고리즘 (구현) 2020. 7. 30. 23:00
https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net 해당 문제는 N * N 크기의 격자판이 주어지며 격자판에서 움직일 수 있는 말 M개가 주어져 M 개의 말이 이동하여 특정한 위치에 4개 이상 겹치게 둘 경우 현재 진행횟수를 출력하면 되는 문제이다. 추가로 각 말의 위치 정보와 이동할 수 있는 방향이 주어진다. 게임의 룰은 다음과 같다. 말이 이동중 현재 말 위에 다른 말이 올라가 있다면 위에 있는 모든 말들도 같이 움직인다. 1. 만약 말이..
-
백준 17142 ( 연구소 3 )컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 29. 16:56
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 해당 문제는 N과 K가 주어지며 N * N 개의 배열 안에서 바이러스를 퍼뜨려 맵 전체에 바이러스가 퍼질 수 있는 최단시간을 구하는 문제이다. 이때 조건은 바이러스는 무작위로 주어지며 해당 바이러스는 모두 활성화 되어있지 않으며 K개의 바이러스만 활성화 시켜 바이러스를 퍼트린다. 따라서 K개의 바이러스 조합을 만들어 어떤 바이러스 조합이 최소의 시간으로 맵 전체에 바이러스를 퍼트릴 수 있는지 구하면 된다...
-
백준 17140 (이차원 배열과 연산)컴퓨터 공학 기초/알고리즘 (구현) 2020. 7. 28. 19:37
https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 해당 문제는 간단한 구현 문제이다. Y, X, K 값이 주어지며 배열의 Y, X 번째 요소가 K가 되는 경우를 찾는 문제이다. 3 * 3 에 해당하는 2차원 배열에 각 수가 주어지며 다음과 같은 조건일 때 배열이 변화한다. Y 축의 값과 X축의 값을 비교했을 때 Y 축의 값이 X 보다 크거나 같다면 X축의 값을들 비교한다. 위의 경우가 아닌경우 Y축의 값들을 비교한다. #include..
-
백준 17143 (낚시왕)컴퓨터 공학 기초/알고리즘 (구현) 2020. 7. 27. 21:04
https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 간단한 구현 문제이다. 상어의 위치가 주어지며 격자판 안에 상어가 존재한다. 낚시꾼은 X축을 +1 하며 이동하면서 마지막 X축 까지 이동하면서 잡은 상어의 총크기를 구하면 되는 문제이다. 이때 주의해야 할 점이 있는데 상어가 이동할 수 있는 경우가 최대 1000 번이기 때문에 시간 초과를 주의해야 한다. TIP : 상어가 격자판의 Y or X 축을 한바퀴 돌아 제자리로 돌아오는..
-
백준 15686 (치킨 배달)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 21. 19:25
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 해당 문제는 집과 치킨 가게의 위치가 주어지고 M개의 가게만 남겼을 때 구할 수 있는 집들의 치긴 가게와의 거리중 최소 값을 구하는 문제이다. 풀이 1. 주어진 map을 탐색하며 집과 치킨 가게에 해당하는 좌표를 각각 배열 house, chekenList에 담는다. 2. 재귀 (조합) 을 사용하여 1개의 치킨 가게를 선택하며 계속 재귀를 수행하며 이때 남겨야 하는 가게의 수 ..
-
백준 15684 (사다리 조작)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 21. 14:51
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 해당 문제는 사다리를 최대 3개 까지 놓을 수 있으므로 재귀를 통한 완전탐색을 이용하여 문제를 해결 할 수 있다. 풀이 사다리를 두는 순서는 상관 없음으로 조합을 이용하여 재귀 호출을 사용하며 이때 사다리를 놓는 곳은 1, 사다리의 왼쪽에 해당하는 영역은 2로 Check를 실시한다. 따라서 1인 경우에는 X좌표를 +1 하는 것으로 우측으로 이동하며 만약 2인 경우에는 X좌표를 -1 하며 좌측으로..
-
백준 15683 (감시)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 20. 18:47
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감�� www.acmicpc.net 해당 문제는 각 CCTV 당 최대 4개의 경우의 수를 가질 수 있다. 따라서 map을 탐색하며 CCTV 가 존재할 경우 해당 CCTV가 감시할 수 있는 모든 경우의 수를 탐색하면 되는 문제이다. 재귀의 흐름을 보면 다음과 같다. 위와 같이 탐색 된 CCTV의 종류 별로 나올 수 있는 모든 경우의 수를 탐색하며 탐색되는 영역을 visit 배열에 체크하며 재귀를 수행하면 문제를 해결할 ..
-
백준 14503 (로봇 청소기)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 20. 14:27
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 해당 문제는 재귀를 이용하여 지문의 조건에 맞게 풀었다. 지문의 조건을 요약하면 다음과 같다 1. 청소기의 현재 방향을 기준으로 왼쪽이 청소를 하지 않은 영역이라면 해당 영역을 청소하고 청소기의 방향전환 2. 만약 청소기의 왼쪽 영역이 청소가 되어 있거나 벽이라면 청소기의 방향을 왼쪽으로 돌린 뒤 다시 1 부터 수행 3. 만약 청소기를 계속 왼쪽 방향으로 돌려 4방위를 모두 탐색했을 때 모든 방..