Algorithms 검색 결과

해당 글 123건

[BOJ 9019] DSLR (C++)

DSLR (Gold 5) 문제 전체 문제 보기 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 접근법 이번 문제는 BFS로 풀 수 있지만 상당히 까다로운 문제입니다. 그 이유는 문제를 보고 BFS로 접근해야 한다고 생각하기 어렵고, 최단경로의 경로 크기만 출력하는 것이 아니라 어떤 경로를 지나왔는지까지 출력해야 하기 때문에 고려해야 할 사항이 많습니다. 최단 경로를 기록 및 출력하기 위해서 아래와 같이 현재 값을 만들 수 있는 부모 값 배열 parents와 현재 숫자로 만들기 위해 사용한 연산자 ..
Algorithms/DFS & BFS 2021. 9. 24. 19:09

[BOJ 1992] 쿼드트리(C++)

쿼드트리(Silver 1) 문제 전체 문제 보기 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 접근법 이번 문제는 분할정복으로 풀 수 있습니다. 우선 현재 입력받은 범위 내에서 모든 수가 같은지 확인하는 Check 함수를 만듭니다. 이 Check함수를 활용해서 모든 수가 같은지 확인 후 같다면 해당 수를 출력하고, 같지 않다 배열의 범위를 4곳으로 나누어 재귀적으로 호출합니다. 코드는 다음과 같습니다. 전체 풀이 #include #include #include #define endl '\n' u..
Algorithms/Division and Conquest 2021. 9. 23. 19:15

[BOJ 17626] Four Squares (C++)

Four Squares (Silver 4) 문제 전체 문제 보기 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 접근법 이 문제는 완전탐색 혹은 DP로 풀 수 있습니다. 여기서는 DP로 접근하여 풀었습니다. DP로 풀기 위해서 점화식은 다음과 같이 정리할 수 있습니다. \[f(n) = \mbox{min}(f(1 * 1) + 1 , f(2 * 2) + 1, ... ,f(\sqrt{n} * \sqrt{n} + 1)\] 전체 구현 아래와 같이 구현하여 문제를 해결할 수 있습니다. ..
Algorithms/DP 2021. 9. 23. 10:38

[BOJ 1389] 케빈 베이컨의 6단계 법칙(C++)

케빈 베이컨의 6단계 법칙(Silver 1) 문제 전체 문제 보기 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 접근법 모든 사람에 대해서 각 사람들까지 관계 단계를 모두 계산해야 합니다. 이럴 경우 플로이드 워셜 알고리즘을 사용할 수 있습니다. 모든 사람들 관계에 대한 2차원 테이블을 만듭니다. 그리고 플로이드 워셜 알고리즘을 활용하여 관계의 최단 거리를 구합니다. 이 거리들의 합이 바로 케빈 베이컨의 수가 됩니다. 이 수가 가장 작은 사람을 출력하면 정답을..
Algorithms/Graph 2021. 9. 22. 16:24