수학

[프로그래머스 Lv.2] 소수 찾기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42839# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이문자열을 이루는 각 숫자를 조합하여 특정 숫자를 만들고 이 수가 소수인지 체크하면 되는 간단한 문제이다.풀이 순서는 다음과 같다.문자열을 한 자리씩 잘라서 한 자리의 정수로 만든다.한 자리 정수들을 사용하여 만들 수 있는 수들을 permutation을 사용해 모두 알아낸다.2번에서 만든 수들이 소수인지 체크하고 소수의 수를 기록한다.from itertools import permuta..

[프로그래머스 Lv.2] 행렬의 곱셈 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12949 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이행렬곱을 구현하면 되는 단순한 문제이다. 행렬곱의 경우 아래와 같은 방식으로 계산한다.이런 계산 방식을 코드로 구현하면 된다.def solution(arr1, arr2): answer = [] for m in range(len(arr1)): # 피연산자(arr1)의 각 행 별로 계산 arr = [] for r in range(len(arr2[0..

[프로그래머스 Lv.2] 교점에 별 만들기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87377 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이레벨 2의 문제답게 크게 어렵지 않게 풀 수 있는 문제라고 생각한다. 아래 사진의 두 일차방정식의 교점을 구하는 공식을 알고 있기 때문에, 문제에 이를 적용함으로써 교점을 구하고 이를 사용하여 교점의 위치에 *을 출력하면 해결이 된다.def solution(line): x_min = y_min = float('inf') # 그려야할 직사각형의 시작 위치를 알기 위한 최소값 x..

(Python) 백준 6588번 - 골드바흐의 추측

문제 링크: https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 풀이 문제를 해결하기 위한 기본적인 아이디어는 에라토스테네스의 체이다. 우선 가장 홀수 중 가장 작은 소수인 3부터 시작해서 소수인지 검사하고, 만약 그 수(x)가 소수라면 n-x도 소수인지 체크를 한다. 이 모든 체크가 통과되면 n = x + n-x를 출력하면 된다. import sys MAX_NUM = 1000001 # N의 최대값 arr = [True] *..

[프로그래머스 Lv.2] 의상 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제는 해시와 수학적인 사고가 필요한 문제이다.우선 해시를 사용해 각 옷의 종류별 개수를 파악한다. 파악한 수를 기반으로 입을 수 있는 총 조합의 개수를 계산한다. 조합의 갯수는 옷의 종류별의 수를 n이라 했을 때, n+1을 곱해주다가 최종적으로 -1을 해주면 된다. n+1을 곱해주는 이유는 n개의 옷과 입지 않을 경우의 1을 더해주는 것이고, 최종적으로 1을 빼주는 이유는 모두 다..

(C++) 백준 11051번 - 이항 계수 2

문제 링크 : https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 풀이 이항 계수의 성질 중 다음의 파스칼의 삼각형을 사용하여 풀었다. 처음에 재귀함수를 사용하여 풀이하였으나 그럼 시간 초과가 발생하기에 다음과 같이 dp로 풀이하였다. #include using namespace std; int n, k; int bicos[1005][1005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; bicos[0][0] = bi..

(C++) 6064번 - 카잉 달력

문제 링크 : https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 문제 풀이 문제에 나온 예시를 들어보면 M = 10이고 N = 12일 때 첫 번째 해는 , 11번째 해는 , 13번째 해는 , 는 마지막인 60번째 해를 나타낸다. 이들의 규칙을 찾아보면 n번째 해는 임을 알 수 있다. 그리고 당연히 마지막 해는 규칙에 의해 최소공배수 즉 60번째 해임을 알 수 있다. 이를 이용하여 풀이하였다. #include using namespace std; in..

(C++) 백준 11653번 - 소인수분해

문제 링크 : https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 풀이 소인수분해는 가장 작은 소수인 2부터 시작하여 합성수가 나눠지지 않을 때까지 계속해서 나눠주면 된다. #include using namespace std; int n; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 2; i*i

(C++) 백준 1929번 - 소수 구하기

문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 풀이 에라토스테네스의 체를 사용한 풀이이다. #include #include using namespace std; int m, n; vector state(1000005, true); void prime(int n){ state[1] = false; for(int i = 2; i*i m >> n; prime(n); for(int i = m; i

(C++) 백준 1978번 - 소수 찾기

문제 링크 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 풀이 만일 N이 2부터 √n의 수까지 나누어 떨어지는 경우가 있으면 이는 소수가 아니다. 이를 활용하여 풀이하였다. #include using namespace std; int A[102]; int n, cnt; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i > A[i]; for(int i = 0; i < ..