컴퓨터 공학 기초/알고리즘 (브루트포스)
-
백준 16928 (뱀과 사다리게임)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 17. 15:15
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 해당 문제는 1 ~ 100 까지의 칸을 가진 Map 위에서 주사위 ( 1~ 6 )을 굴려 말의 위치를 옮겨가며 해당 말의 위치가 100에 도착하기 위한 최단경로를 찾는 문제이다. 따라서 BFS를 이용하여 문제를 해결하면 된다. 이때 주의해야 할 점이 BFS를 사용하여 queue에 모든 경로를 저장하게 되면 메모리 초과가 발생하게 된다 따라서 이미 방문..
-
백준 14889 (스타트와 링크)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 17. 14:25
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 해당 문제는 총 n 명의 사람을 조합을 이용해 2개의 팀을 만들어 해당 팀의 평균 능력치를 구하여 각 팀 능력치의 절대값 중 최소값을 구하는 문제이다. 풀이 : #include #include #include #include #include #include using namespace std; int n; int used[21]; int map[21][21]; int result = 999999; vector sLis..
-
백준 2529 (부등호)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 17. 13:32
https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력� www.acmicpc.net 해당 문제는 0 ~ 9 까지 의 숫자들의 순열(중복 X)을 사용하여 주어진 부등호의 경우가 일치할 때 순열에 사용된 숫자를 비교하여 최대값과 최소값을 비교하는 문제이다. 풀이 : DFS를 사용한 재귀를 이용하여 문제풀이 1. 규칙 찾기 가장 첫번째 숫자를 제외한 나머지 숫자는 항상 부등호 뒤에 위치한다. 따라서 1 중 for 문을 사용하여 가장 첫 번째 숫자를 넣어준 뒤 재귀함수를 수행시키며 ..
-
백준 14226 (이모티콘)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 4. 18:49
https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만�� www.acmicpc.net 해당 문제는 영선이가 효빈에에게 이모티콘 S개를 보내려 할 때 조건에 따라 이모티콘의 수를 변경하며 최소 몇 초 만에 S개의 이모티콘을 보낼 수 있는지 구하는 문제이다. 이모티콘의 수를 변경할 수 있는 방법은 다음과 같으며 각 방법을 시행시 1초가 소요된다. 조건 1. 화면에 있는 이모티콘 전부를 클립보드에 복붙 하는경우 (따라서 화면에 이모티콘이 0이라면 수행 X) 2. 화면에 있는 이모티콘 ..
-
백준 13913 (숨바꼭질 4)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 3. 22:12
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 해당 문제는 수빈이가 동생을 찾는데 까지 걸리는 시간과 해당 시간동안 이동한 위치를 출력하는 문제이다. BFS를 사용하여 완전탐색을 시행하며 최단 거리를 출력하면 된다. 이때 주의할 점은 다음과 같다. 1. 수빈이가 이동한 위치를 기록할 Vector 생성 후 해당 벡터에 계속 push 하는 과정을 통해 위치를 저장하고 출력하면 된다. 하지만 수빈이의 위치가 ..
-
백준 17142 ( 연구소 3 )컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 7. 29. 16:56
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 해당 문제는 N과 K가 주어지며 N * N 개의 배열 안에서 바이러스를 퍼뜨려 맵 전체에 바이러스가 퍼질 수 있는 최단시간을 구하는 문제이다. 이때 조건은 바이러스는 무작위로 주어지며 해당 바이러스는 모두 활성화 되어있지 않으며 K개의 바이러스만 활성화 시켜 바이러스를 퍼트린다. 따라서 K개의 바이러스 조합을 만들어 어떤 바이러스 조합이 최소의 시간으로 맵 전체에 바이러스를 퍼트릴 수 있는지 구하면 된다...
-
백준 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 하며 좌측으로..