알고리즘/BOJ(C++)
-
[BOJ] 1699 :: 제곱수의 합알고리즘/BOJ(C++) 2018. 6. 16. 20:25
https://www.acmicpc.net/problem/1699 다이나믹 프로그래밍으로 푸는 문제입니다. 다이나믹 프로그래밍을 생각할때 저는 항상 1차원 다이나믹인지, 2차원 다이나믹인지를 먼저 생각합니다. 이 경우에는 고려할 요건이 제곱수 밖에 없으므로 1차원으로 풀릴 것 같네요. 1차원 dp[100001]개를 잡은 후에 dp[i]의 조건을 정의합니다.dp[i]는 i를 만드는데 필요한 제곱수의 최소 개수로 정의합니다. 그 후 점화식을 이용해 dp[i]를 구해야 합니다.dp[i]를 구하기 위해선 i보다 작은 어떤 수 + 임의의 제곱수를 했을 때 i가 나오는 경우를 탐색해야 합니다.때문에 i와 같거나 작은 경우까지 각각의 경우에 (i에서 제곱수를 뺀 수의 dp값 + 1) 과 현재 dp값을 비교해 나가면서..
-
[BOJ]1406 :: 에디터알고리즘/BOJ(C++) 2018. 6. 16. 20:01
https://www.acmicpc.net/problem/1406 자료구조 연습하기 좋은문제!! 문제 설명은 생략하고 커서를 기준으로 왼쪽 문자열을 저장하고 오른쪽 문자열을 저장하는게 핵심이다! 왼쪽 오른쪽 모두 앞뒤로 push pop이 편리해야 하므로 deque 자료구조를 사용합니다.. L : 왼쪽 deque의 back을 오른쪽 deque의 맨 앞으로 (empty일 경우 예외처리)D : 오른쪽 deque의 front을 왼쪽 deque의 맨 뒤로 (empty일 경우 예외처리)B : 왼족 deque의 back을 삭제하기(pop_back())P : 왼쪽 deque의 back에 추가! #include #include #include using namespace std;deque l;//커서 왼쪽 문자들을 보관..
-
[BOJ] 6679 :: 싱기한 네자리 숫자알고리즘/BOJ(C++) 2018. 6. 2. 21:26
https://www.acmicpc.net/problem/6679 입력은 없습니다.1000부터 9999까지 해당 조건을 만족하는 숫자를 모두 출력하면 되는 문제입니다. 해당 조건은 10진수로 바꿨을 때 각 자리수의 합 == 12진수로 했을 때 모든 자리 수의 합 == 16진수로 했을 때 모든 자리 수의 합입니다. 각 숫자를 진법 변환해주는 과정만 구현하면 아주 쉬운 문제입니다. 저는 %연산을 통해 자리수를 확인한 후 진수로 나누어 0이 되기 전까지 각 자리를 확인해 주었습니다. #include using namespace std;int main(){for(int i = 1000; i
-
[BOJ] 8958 :: OX퀴즈알고리즘/BOJ(C++) 2018. 6. 2. 21:20
https://www.acmicpc.net/problem/8958 연속된 O의 개수를 찾는 것이 관건입니다. X가 나오기 전까지 t의 값을 늘리면서 확인 해 주다 X가 나오면 t를 0으로 초기화 해주면 됩니다. #include #include using namespace std;int main(){int t;cin >> t;while (t--){string s;cin >> s;int t = 0;int ans = 0;for (int i = 0; i
-
[BOJ] 2581 :: 소수알고리즘/BOJ(C++) 2018. 6. 1. 23:18
https://www.acmicpc.net/problem/2581 N부터 M까지의 소수를 구해서 벡터에 저장해주는 것이 핵심입니다! 벡터에 모든 원소를 탐색하며 총 합을 구하고, 작은 수부터 소수를 구하는 함수를 돌릴 것이기 때문에 항상 최솟값이 벡터의 가장 앞에 오므로 최솟값은 v[0]으로 접근할 수 있습니다. 소수가 존재하지 않을 경우 vector이 비여서 따로 예외처리 해주는거 잊어서 런탐에러 난건 안비밀..... #include #include using namespace std;bool find(int n){if (n == 1)return false;bool flag = true;for (int i = 2; i > a >> b;vector v;for (int i = a; i
-
[BOJ]2908_상수알고리즘/BOJ(C++) 2018. 6. 1. 22:55
https://www.acmicpc.net/problem/2908 거꾸로 읽은 숫자 중 큰 수를 구하는 문제입니다! 거꾸로 읽은 숫자중 큰 값을 구하는게 관건인데, 저는 처음부터 string으로 입력을 받아 algorithm 헤더파일에 들어있는 swap함수를 이용해 reverse된 스트링을 구해줬습니다. string을 다시 int로 변환해서 비교를 해줘야 할 거라고 생각했는데[... 그냥 변환 안하고 크기를 비교해도 되더라구요! #include #include #include using namespace std;int main(){string a, b;cin >> a >> b;int len_a = a.length();int len_b = b.length();for (int i = 0; i
-
[BOJ]15780_멀티탭 충분하니?알고리즘/BOJ(C++) 2018. 5. 27. 15:20
제 4회 IUPC A번 문제입니다. https://www.acmicpc.net/problem/15780 사용할 수 있는 멀티탭의 개수를 구해서 학생수 보다 큰지만 확인해 주면 되는 아주아주 간다한 문제 ! 멀티탭이 3개이면 2개를 사용할 수 있고 4개이면 2개 , 5개이면 3개를 사용할 수있으므로 개수 + 1 /2가 각 멀티탭에서 사용할 수 있는 최대 개수이다. 1234567891011121314151617181920212223242526#include using namespace std; int info[101];//콘센트 수의 정보를 저장할 배열 int main(){ std::ios::sync_with_stdio(false); cin.tie(NULL); int n, k;//학생 수, 콘센트 수 cin..