📗 CS/Algorithm

그리디 알고리즘 결정해야 할 때, 그 순간에 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘 그 때 그 때는 최적일수도 있지만 최종적으로는 최적의 해가 아닐 수도 있다. https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 소스 코드 #include using namespace std; int coin[10]; int main() { int n,k; int ans=0; ci..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net Point 1. 연구소 2와 달리 비활성화 바이러스가 존재. 2. 활성화 바이러스가 비활성화 바이러스가 있는 칸으로 가면 비활성화 바이러스가 활성화 바이러스로 바뀐다. 3. 활성화 바이러스를 선택하는 경우의 수는 최대 10개중에서 5개 고르는 경우로 10C5 = 252가지 경우가 존재한다. 4. 최대 10C5에 대해 BFS를 실행하면 O(252*50*50)=630,000 으로 시간 안에 통과 가능. 이 테..

https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net Point 1. 로봇청소기(o)에서 모든 더러운 칸(*)으로 이동하는데 필요한 최소 비용 2. 더러운 칸(*)의 최대 개수는 10개 3. 더러운 칸을 방문하는 순서에 따라 비용이 달라진다. 방문하는 순서에 따라 비용이 달라진다. 쓰레기가 3개인 경우에는 3! = 6가지의 경우의 수가 존재한다. 쓰레기의 최대 개수는 10개이므로 최대 10! =~ 3,600,000 경우의 수가 존재한다. 그렇다면 더러운 칸(..

https://www.acmicpc.net/problem/2151 2151번: 거울 설치첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net Point "#" ▶︎ 문 "!" ▶︎ 거울 설치 가능한 구역 "*" ▶︎ 벽거울을 45도 기울어진 대각선으로 설치해야 한다.문에서 문을 보기 위해 거울을 설치할 때, 설치해야 하는 거울의 최솟값을 구하는 문제. 다음과 같이 두 가지 방법이 있다. 테스트케이스 1번의 경우에는그림과 같이 거울을 설치하면 문에서 문을 볼 수 있다. Point1 )우선 거울과 문에 번호를 지정해주려한다. 문..

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net Solution 현재 상태에 대한 정보를 추가적으로 저장한다는 점에서 이전 포스팅에서 다룬 문제와 정확히 같은 유형의 문제입니다. 이전 포스팅과 매우 유사한 문제이기 때문에 소스코드를 짧게 설명하고 끝내도록 하겠습니다. 소스 코드 #include #include #include #include #include #define FASTio ios_base :: sy..