https://www.acmicpc.net/problem/1629 1629번: 곱셈첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.www.acmicpc.net 단순히 계속 곱했다가는 오버플로우되는 문제. 하지만 모듈러 연산을 적용한다고 해도, 일반적인 반복문으로 접근한다면 시간제한에 걸린다 O(n)이니까. 결국 이 문제의 핵심은숫자가 오버플로우되지 않도록 모듈러연산을 계속해서 적용한다.O(n)으로 접근해서는 안된다.모듈러 연산은 https://codejin.tistory.com/68를 참조하자. 이를 통해 다 곱하고 나누는 것이 아니라, 나머지를 계속 곱하면서 최종적인 값을 찾아야 한다. 그러면 오버플로우는 해결했고 이제..
https://programmers.co.kr/learn/courses/30/lessons/12932?language=cpp 코딩테스트 연습 - 자연수 뒤집어 배열로 만들기 자연수 n을 뒤집어 각 자리 숫자를 원소로 가지는 배열 형태로 리턴해주세요. 예를들어 n이 12345이면 [5,4,3,2,1]을 리턴합니다. 제한 조건 n은 10,000,000,000이하인 자연수입니다. 입출력 예 n return 12345 programmers.co.kr 자연수를 뒤집은 배열을 반환하는 문제. 10으로 나눈 나머지를 순차적으로 배열에 넣는다. #include using namespace std; vector solution(long long n) { vector answer; while (n) { answer.pus..
https://programmers.co.kr/learn/courses/30/lessons/76501?language=cpp 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 re programmers.co.kr 정수의 절댓값과 부호가 따로 주어지는 문제. signs에 따라 뺄지 더할지 결정한다. #include using namespace std; int solution(vector absolutes, vector signs) { int answer = 0; for (int i = 0; i < absolutes.size()..
https://programmers.co.kr/learn/courses/30/lessons/12947 코딩테스트 연습 - 하샤드 수 양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하 programmers.co.kr 자기 자신의 자릿수의 총합이 자기 자신을 나누어 떨어지게 하는 숫자를 하샤드 수라고 한다. 숫자를 자릿수로 분리하여 합하고 나누어 떨어지는지 반환한다. #include #include using namespace std; bool solution(int x) { int copy = x; vector v; while(copy) { v.p..
https://programmers.co.kr/learn/courses/30/lessons/12901?language=cpp 코딩테스트 연습 - 2016년 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까 programmers.co.kr 주어진 날찌의 요일을 반환하는 문제. 일, 월, 화 ....., 토요일과 월별로 최대 일수를 배열에 저장한 후에, 1월 1일로부터 며칠이 지났는지 변환하여 월, 일을 일수로 바꾼 후에, 7로 나눈 나머지가 요일이 되므로 이를 출력한다. 이때 1월 1일이 금요일인걸 고려해야한다. #include usi..
https://programmers.co.kr/learn/courses/30/lessons/42748?language=cpp 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 전체 배열을 주어주고, 구간을 잘라 정렬하고, 거기서 k번째 수를 찾는 문제. 구간을 복사하여, 주어진대로 한다. #include #include using namespace std; vector solution(vector array, vector commands) { vector answer; vector::iterator commandIter = commands.begin(); vector copyA..
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 처음으로 풀어보는 탐색문제이다. 처음에는 탐색알고리즘이라는걸 모른 채로 그냥 for문 계속 돌리면서 풀었는데, 역시나 시간초과가 나오고 포기했던 문제이다. 하지만 이진탐색(binary search) 알고리즘을 알게 되어 이 문제를 다시 풀었고 맞췄다. 이진탐색은 생각보다 우리가 자주 쓰는 알고리즘이다. 0~100부터 아무 숫자나 하나 정하고, 업다운..
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표값이 몇번째에 있는지 출력하는 문제. 특이하게도 이 문제는 정렬하는것이 아닌, 중복을 제거하는 과정에서 애를 먹었다. 컨테이너에서 앞부분에 unique한 원소들로 채워넣고, 뒷부분에는 남은 원소들로 채운다음, 뒷부분의 포인터를 반환하는 unique함수의 동작원리때문에 애먹었다. std::move()함수를 통해 동작하기 때문에, 이를 이해하려고 ..
