현재를 행복하게 현재를 행복하게

알고리즘

• [BOJ] 1373 :: 2진수 8진수

  알고리즘/BOJ(C++) 2018. 6. 19. 21:42

  https://www.acmicpc.net/problem/1373 2진수를 8진수로 바꾸는 간단한 문제입니다.2진수를 3개씩 끊어서 10진수로 바꿔서 출력해주면 됩니다. 앞의 3개만 예외처리 해서 총 길이가 3의배수가 아닐경우 처리해주면 됩니다. #include #include #include #include using namespace std;int main(){string initial;cin >> initial;int decimal = 0;int len = initial.length();int left = len % 3;if (left == 1){cout

  Read More
• [BOJ] 2225 :: 합분해

  알고리즘/BOJ(C++) 2018. 6. 16. 21:09

  https://www.acmicpc.net/problem/2225 다이나믹 프로그래밍으로 해결했습니다. 아무리 생각해도 1차원 dp로는 해결되지 않는데 아직 2차원 dp에 약한지 점화식 세우는데 꽤 애를 먹었네요 ㅠ 우선 dp[202][202]정도 잡아줍니다이 때 dp[k][n]의 정의는 k번 더해서 n을 만들 수 있는 경우의 수 입니다. dp[i][n] 은 dp[i-1]행에서 0부터 n까지 값을 더해서 만들 수 있습니다.i-1번 더해서 만들 수 있는 경우의 수에 0부터 n까지 어떤 수던 한개 더하면 n을 만들 수 있으니까요! 5 by 5의 예를 들어 보겠습니다. 0 1 2 3 4 51 1 1 1 1 1 12 1 2 3 4 5 63 1 3 6 10 15 214 1 4 10 20 35 565 1 5 15 ..

  Read More
• [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값을 비교해 나가면서..

  Read More
• [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;//커서 왼쪽 문자들을 보관..

  Read More
• [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

  Read More
• [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

  Read More
• [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

  Read More
• [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

  Read More