전공
-
백준 11998(Milk Pails)전공/알고리즘 2020. 10. 9. 16:38
www.acmicpc.net/problem/11998 11998번: Milk Pails (Silver) Farmer John has received an order for exactly \(M\) units of milk (\(1 \leq M \leq 200\)) that he needs to fill right away. Unfortunately, his fancy milking machine has just become broken, and all he has are two milk pails of integer sizes \(X\) and \(Y\) www.acmicpc.net 주어진 행위를 할 때 그 행위를 할 수 있는 횟수가 주어져 있고, 그 횟수 이내에서 가장 적절한 값을 찾는것이 문제. 주어..
-
백준 11687(팩토리얼 0의 개수)전공/알고리즘 2020. 10. 7. 16:08
www.acmicpc.net/problem/11687 11687번: 팩토리얼 0의 개수 첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다. www.acmicpc.net 0이 어떻게 만들어지는지에 대한 문제이다. 어떤 n!을 파보던 2의 거듭제곱 갯수가 5의 거듭제곱 갯수보다 항상 많으므로 n!에서 0은 5의 거듭제곱 갯수가 결정한다. 5의 거듭제곱 갯수의 합을 구하면 되는 문제이다. #include using namespace std; #define MAX 100000000 int sum; int main() { int M; cin >> M; for (int i = 1; i
-
백준 1005(ACM Craft)전공/알고리즘 2020. 10. 7. 15:11
www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 위상정렬 문제이다. 위상정렬은 연결된 그 전 행위에 대해서 모두 마쳤을때 그 노드로 이동할 수 있는 그래프에 대한 순서이다. 위상정렬 알고리즘으로는 순서도 알 수 있고, 그 노드까지 실행하는데 필요한 최소값 최댓값 이런 것을 알 수 있다. 이 문제는 어떤 행위를 하는데 걸리는 최솟값에 대한 문제이다. 그래프 구성을 한 뒤에 진입차수 위상정렬 알고리즘을 이용해서 최솟값을 결정하도록 하자 그래프 구성은 단순..
-
백준 2352(반도체 설계)전공/알고리즘 2020. 10. 7. 13:06
www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 문제를 잘 읽고 생각을 좀 하다보면 n번 포트를 꽂을 차례가 되었을 때, 그 전에 최종적으로 무슨 포트를 어디에 꽂았느냐를 가지고 이게 가능한지 아닌지를 판단할 수 있다. 따라서 가능한 경우에만 갯수를 하나씩 늘려나가면서 저장을 하면 dp로 풀수 있다는 것을 알 수 있다. 그렇게 dp로 풀 수 있다고 생각을 했지만 입력이 40000이므로 N^2의 전체 확인 알고리즘으로 풀면 시간초과가 난다...
-
백준 1759(암호 만들기)전공/알고리즘 2020. 10. 5. 16:05
www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 딱 봐도 브루트포스이다. 들어가고 안 들어가고, 총 15^2 의 시간복잡도가 소요된다. 따라서 잘 전처리하고, 들어갈때 안 들어갈 때를 구하면 된다. 전처리라고 함은 사전식 배열로 바꾸어 줘야 한다. 그냥 sort로 정렬을 하면 된다. 그러고 나서 재귀로 돌리는데 조건을 잘 짜주자. #include #include #include using namespace std; int L, C, mo, ja; vector v;..
-
백준 13424(비밀 모임)전공/알고리즘 2020. 10. 5. 15:25
www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 그래프로 최단 거리를 구하는 문제이다. 최단 거리 알고리즘은 대표적으로 다익스트라가 있는데 이 알고리즘은 1vsN이므로 이 문제에서 요구하는 NvsN과는 좀 맞지 않는다 그래서 NvsN의 최단거리 알고리즘인 플로이드 와샬을 사용한다. 그래프를 구현하고, 플로이드 와샬 이용, 원하는 값을 구한다. 주의해야 할 점은 본인과 본인의 거리는 0이다 #include #include using namespace std; ..
-
16494전공/알고리즘(생각 멈춘거) 2020. 10. 5. 14:43
https://xkdlaldfjtnl.tistory.com/194 22.03.15 풀이 백준 16494 가장 큰 값 https://www.acmicpc.net/problem/16494 16494번: 가장 큰 값 첫째 줄에 N과 M(1 ≤ M ≤ N ≤ 20)이 주어진다. 둘째 줄에는 수열에 속한 수가 주어진다. 수는 공백으로 구분되어져 있고, 절댓값이 100보다 작거나.. xkdlaldfjtnl.tistory.com 위 링크 보세요 ----------------------------------------------------------------------------------------------------------------------- ----------------------------------..
-
백준 15886(내 선물을 받아줘 2)전공/알고리즘 2020. 10. 5. 13:43
www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직 www.acmicpc.net 문제 좀 제대로 읽자 처음에 위치에 따라 움직이는 것이 정해진다고 이해를 못 하고 단순 그 방향대로 무조건 움직여야 된다고 생각을 했다. 하지만 지도의 위치에 따라 움직인다면 무조건 EW가 있는 곳으로 향하기 때문에 EW의 갯수를 정하면 된다. 그래프로도 풀 수 있는 것같은데 지금은 생각이 안난다. #include using namespace std; int before = '0'; int main..