본문 바로가기

Algorithm/Math

 (101)
(C++) - 백준(BOJ) 10972번 : 다음 수열 www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 조합문제였습니다. next_permutation은 다음 수열이 있다면 다음 수열로 바꿔준다음 true를 반환합니다. 만약 현재 vector가 마지막 수열이라면 false를 반환합니다. 풀이방법 next_permutation이 false라면 -1를 출력해줍니다. 그 외에는 다음 수열을 출력해줍니다. Code #include using namespace std; int n; int main(){ cin >> n; vector v(n); for(auto &n : v) cin ..
(C++) - 백준(BOJ) 16479번 : 컵라면 측정하기 www.acmicpc.net/problem/16479 16479번: 컵라면 측정하기 첫째 줄에 K의 값이 주어진다. 둘째 줄에는 D1과 D2의 값이 사이에 공백을 한 개 두고 차례대로 주어진다. 단, K, D1, D2의 값은 양의 정수이다. www.acmicpc.net 수학 문제였습니다. 풀이방법 상기와 같이 3가지 형태의 컵라면이 나올 수 있습니다. 하지만 이를 하나의 공식으로 한 번에 높이를 구할 수 있습니다. n = (max(d1,d2) - min(d1,d2)) / 2 정답 : k * k - n * n Code #include using namespace std; double k,d1,d2,n; int main(){ cin >> k >> d1 >> d2; n = (max(d1,d2)-min(d1,d..
(C++) - 백준(BOJ) 1748번 : 수 이어 쓰기 1 www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 수학문제였습니다. 풀이방법 1. 단순 반복문으로는 시간초과 또는 메모리 초과를 맛볼 수 있으니 자릿수가 달라지는 구간에 대해 수학적으로 접근해야 합니다. 2. n이 1 ~ 9까지는 자리수가 1개씩 더해집니다. 10 ~ 99까지는 자리수가 2개씩 더해집니다. 100 ~ 999까지는 자리수가 3개씩 더해집니다. 따라서 n의 자리수만큼 loop를 돌며 해당하는 값을 적절히 더해주면 됩니다. Code #include #include using namespace std; int ans, margin, behind = 9, after = 1;..
(C++) - 프로그래머스(연습문제) : 최솟값 만들기 programmers.co.kr/learn/courses/30/lessons/12941 코딩테스트 연습 - 최솟값 만들기 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱 programmers.co.kr 수학 문제였습니다. 풀이방법 1. 두 수의 곱들의 합이 최소가 되려면 최소값 * 최대값들의 합으로 만들어주면 됩니다. 2. A를 오름차순 정렬, B를 내림차순 정렬한 뒤 차례대로 A[i] * B[i]한뒤 answer에 더해줍니다. Code #include using namespace std; int solution(vector A, vector B) { ..
(C++) - 백준(BOJ) 1673번 : 치킨쿠폰 www.acmicpc.net/problem/1673 1673번: 치킨 쿠폰 강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 교환 www.acmicpc.net ad-hoc 문제였습니다. 그 뜻처럼 이런 문제에만 적용되는 유일한 해결책을 찾는 문제입니다. 풀이방법 1. 입력 이 문제는 입력의 끝이 규정되어 있지 않습니다. 따라서 loop탈출을 위해서 파일의 끝을 찾았을 때 입력받고 있었던 loop를 탈출해야 합니다. 파일의 끝은 scanf를 사용해서 입력받았을 때 EOF(End Of File)을 만나면 false(0)을 반환합니다. 2. 쿠폰이 남아 있는 동안 loop..
(C++) - 백준(BOJ) 1002번 : 터렛 www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 두 원의 중심과 두 원의 교차점과 한 원의 중심점 사이의 거리가 두 개 주어졌을 때 만들 수 있는 원을 생각하고 이렇게 생긴 두 개의 원이 겹침으로써 만들어지는 교차점의 개수를 구하는 문제였습니다. 풀이방법 1. 값 구하기 : 주어진 두 원의 중심의 점으로 거리를 구할 수 있습니다. 이를 변수 a로 정의합니다. 다음은 (x1,y1) , (x2,y2) 사이의 거리를 구하는 공식입니다. $$a = \sqrt{(x1-x2)^2 + (y1-y2)^2} $$ 이후 각 반지..
(C++) - 프로그래머스(연습문제) : 행렬의 곱셈 programmers.co.kr/learn/courses/30/lessons/12949 코딩테스트 연습 - 행렬의 곱셈 [[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20, 14]] programmers.co.kr 행렬곱셈 구현 문제였습니다. Code #include #include using namespace std; vector solution(vector arr1, vector arr2) { vector answer; for(int i = 0; i < arr1.size(); i++){ for(int j = 0; j < arr1[i].size(); j++){ vect..
(C++) - 프로그래머스(연습문제) : 최대공약수와 최소공배수 programmers.co.kr/learn/courses/30/lessons/12940 코딩테스트 연습 - 최대공약수와 최소공배수 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 programmers.co.kr 유클리드 호제법으로 최대공약수를 구한뒤 이 값으로 최소공배수를 구하는 문제였습니다. Code #include using namespace std; int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); } vector solution(int n, int m) { vector answer; in..

티스토리툴바