문제 링크 programmers.co.kr/learn/courses/30/lessons/68935 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr 풀이 자바스크립트는 진법 변환을 지원합니다. toString() 메소드는 일반적으로는 수를 string으로 바꿔주는 함수이지만, 기수를 인자로 주면 그에 맞는 진수로 변환해줍니다. parseInt() 함수는 string을 수로 바꿔주는 함수이며, string이 몇 진수인지 기수를 인자로 주면 그에 맞춰 10진수로 변환해..
문제 링크 programmers.co.kr/learn/courses/30/lessons/68644 코딩테스트 연습 - 두 개 뽑아서 더하기 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr 풀이 모든 쌍을 배열에 넣고 정렬해줍시다. 이때, include()를 이용하여 존재하지 않는 원소일 때만 넣어줍니다. 정답 코드 unction solution(numbers) { const p = []; for(let i=0; i
문제 링크 programmers.co.kr/learn/courses/30/lessons/70128 코딩테스트 연습 - 내적 길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요. 이때, a와 b의 내적은 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 입니다. (n은 a, b의 programmers.co.kr 풀이 reduce 함수를 이용해 쉽게 구현합시다. 정답 코드 function solution(a, b) { return a.reduce((ans, cur, i) => ans + a[i] * b[i], 0); }
문제 링크 www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 풀이 문제를 해결하기에 다음과 같은 어려움이 있습니다. 1) 모든 순열을 고려해봐야 하는데 $O(N!)$이라 경우의 수가 너무 많습니다. 2) 순열을 합친 큰 정수가 커도 너무 큽니다. 최대 750자리 수입니다. 수가 너무 큰데?? 2번 문제부터 해결해봅시다. 사실 우리는 정확한 수를 알고 있을 필요가 없습니다. 결국 알고 싶은 사실은 어떤 수 $x$가 $k$로 나누어 떨어지는지입니다. 이를 백준 8111 - 0과 1 문제와 같은 방식으로 ..
문제 링크 www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 어려워 보이지만 "어느 세 점도 일직선 위에 놓이지 않는다."라는 조건때문에 숨통이 트입니다. 이 조건만 보면 정말 반가워요.. 유니온 파인드를 이용해서 풀 수 있습니다. 주어진 선분의 양 끝점이 같은 집합이면 그 선분이 사이클을 만들게 됩니다. 그러니 이런 경우에 몇 번째 차례인지 출력하고 종료하면 됩니다. 정답 코드 #include #define mem(v, e) memset((v), ..
문제 링크 www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 풀이 이번에 새로 solved.ac 클래스 4에 추가된 문제입니다. 페르마 소정리와 모듈러 역원에 대해 친절하게 설명해줍니다. 정말 교육적인 문제예요.. 이제 문제는 $b^{x-2}$를 구하는 데 있습니다. $x$가 매우 크기 때문에 거듭제곱을 효율적으로 해야 합니다. 백준 1629 - 곱셈 문제와 같은 방식으로 거듭제곱을 빠르게 구해주도록 합시다. 정답 코드 #include #define TEST int _tt; cin >> _tt; while(_tt..
문제 링크 www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 $n$이 굉장히 큽니다. 여러 개의 식들을 하나의 행렬로 표현할 수 있습니다. $(a, b) \rightarrow (b, a+b)$가 되게끔 적절히 행렬로 표현해봅시다. 관련된 변수가 $a, b$ 두 가지니 2*2 행렬을 생각해볼 수 있습니다. $$\pmatrix{a & b}\pmatrix{ ? & ? \\ ? & ?} = \pmatrix{b & a+b}$$ $a, b$에 대한 식을 각각 세워봅시다. $$\begin{cases} a_{n+1} = 0\cdot a_{n} +..
문제 링크 www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 $b$가 너무 큽니다. 백준 1629 - 곱셈 문제와 같은 테크닉을 이용해 거듭제곱 시간을 줄여줍시다. 행렬 곱셈의 경우 vector 타입의 곱셈 연산을 오버로딩해주면 편합니다. 1000으로 나눈 답을 출력해야 하는데, 초기 행렬 값이 1000이고 $b$=1인 경우를 주의해주세요. 입력받을 때도 1000으로 나눠주어야 합니다. 정답 코드 #include using namespace std; using ll =..
문제 링크 www.acmicpc.net/problem/2824 2824번: 최대공약수 첫째 줄에 N이 주어진다.(1 ≤ N ≤ 1000) 둘째 줄에는 N개의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M이 주어진다.(1 ≤ M ≤ 1 www.acmicpc.net 풀이 수가 매우 크기 때문에 $a, b$를 long long으로 표현할 수 없습니다. $a, b$를 소인수분해한 뒤, 겹치는 소인수를 모두 곱해주는 방식으로 정답을 구하면 됩니다. 근데 출력조건이 너무 불친절합니다. 9자리까지 출력해야 하는데, 만약 정답이 123,456이면 "123456"을, 1,000,123,456이면 leading zero를 포함하여 "00..
문제 링크 www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 1) 각 수의 개수를 세줍니다. 2) 수 $i$마다, ($i$의 개수) * ($x - i$의 개수)를 정답에 더해줍니다. 3) 경우의 수가 두 번씩 중복되었으므로 정답을 2로 나눠준 뒤 출력합시다. 정답 코드 #include using namespace std; using ll = long long; ll n, x; map p; int ma..