본문 바로가기

Algorithm/Math

 (100)
(C++) - 백준(BOJ) 6588번 : 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 수학문제였습니다. 풀이방법 1. 에라토스테네스의 체를 이용해 i번째 수가 소수인 부분은 0 아닌 부분은 1로 ck배열에 저장합니다. 2. 답 출력 : i와 n-i가 모두 소수라면(ck배열에 해당 값이 0이라면) 정답을 출력합니다. * 수학적으로 100만 이하의 소수 두 개의 합으로 모든 짝수를 표현할 수 있습니다. 따라서 안되는 경우는 없습니다. 낚시입니다. Code #in..
(Python) - 백준(BOJ) 16428번 : A/B - 3 https://www.acmicpc.net/problem/16428 16428번: A/B - 3 첫째 줄에 A와 B가 주어진다. (-1010000 ≤ A, B ≤ 1010000, B ≠ 0) www.acmicpc.net 큰 수에 대해 나눗셈 연산을 구현하는 문제였습니다. 풀이방법 파이썬은 기본적으로 큰 수(long long 범위 초과하는)의 사칙연산을 지원합니다. 두 가지 방법으로 구현하는 법이 있습니다. 1. 그냥 나눠 몫과 나머지를 구하는 방법 : 기본으로 지원해주므로 양수 / 음수인 경우에만 if문으로 처리하는 것 외에 몫을 c, 나머지를 d변수에 저장해 출력합니다. 2. 함수 이용 : divmod(정수1,정수2)함수를 이용하게 되면 정수1을 2로나눈 몫과 나머지가 튜플 형태로 반환됩니다. 이를 이..
(C++) - 프로그래머스(연습문제) : 줄 서는 방법 https://programmers.co.kr/learn/courses/30/lessons/12936# 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 조합의 속성을 파악하는 문제였습니다. 풀이방법 n이 최대 20까지이므로 모든 조합을 backtracking을 사용한다거나 next_permutation내장함수를 사용하게 되면 시간초과가 나게 됩니다. 이를 해결하기 위해서는 n과 k의 특정한 규칙을 찾아야 합니다. 나와 있는 예시로 설명하겠습니다. n은 3일 때 나올 수 있는 조합의 수는 3!이므..
(C++) - 프로그래머스(연습문제) : 최고의 집합 https://programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만 programmers.co.kr 수학 문제였습니다. 풀이방법 1. 몫이 0이라면 -1을 담아 반환합니다. 그 외에 가장 곱이 크기 위해서는 s/n값이 n개 있을 때 입니다. 따라서 s/n값을 n개 가지고 있는 vector ans를 선언합니다. 2. ans의 끝부터 끝 - s%n 으로 오면서 나머지를 1씩 배분해줍니다. 3. 정답을 반환합니다. Code #include ..
(C++) - 프로그래머스(2017 팁스타운) : 예상 대진표 https://programmers.co.kr/learn/courses/30/lessons/12985?language=cpp# 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 수학 문제였습니다. 풀이방법 토너먼트 방식이므로 n을 2로 나누어가며 a와 b가 왼편과 오른편에 위치해 있으면 해당 라운드에는 만난다는 것을 알 수 있습니다. 재귀를 이용해 해결합니다. * a와 b는 누가 더 큰지 명시되어 있지 않기 때문에 여러 입력에 대해 고려해야합니다. * 만약 a와 b가 모두 n/2기준으로..
(C++) - 프로그래머스(Summer/Winter Coding(~2018)) : 점프와 순간이동 https://programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 진수활용 문제였습니다. 풀이방법 *가장 먼저 떠올릴 수 있는 풀이방법은 bfs나 다익스트라이지만 n이 10억이므로 시간복잡도가 높아집니다. 따라서 다른 방식을 생각해야합니다. 점프를 한 것은 현재자리에서 1칸을 움직인 것에 해당하며 순간 이동을 하게되면 현재자리에서 *2를 하므로 다음 자리로 넘어가게 됩니다. 이는 이진수의 속성에 대입해볼..
(C++) - 백준(BOJ) 2407번 : 조합 www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 조합, 큰 수 더하기 구현 문제였습니다. 풀이방법 1. long long 범위를 초과하기 때문에 string으로 수를 중간에 바꿔줘야 overflow가 발생하지 않습니다. 2. dfs를 통해 nCm = n-1Cm-1 + n-1Cm이라는 조합식을 구현할 수 있습니다. Code #include #define ll long long using namespace std; ll n, m, ans; string comb[101][101]; string numToString(string a, string b){ ll sum = 0; str..
(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 ..

티스토리툴바