게임 개발 낙서장

개념 Selection Sort는 Bubble Sort과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 과정 주어진 배열 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. (pass) 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 시간복잡도 데이터의 개수가 n개라고 했을 때, 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2 ... (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균,..

개념 Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다. 과정 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 시간복잡도 주어진 배열 안에서 교환(swap)을 통해..

문제 풀이 전 이론 - 1 - 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다 - 위의 문장에 3을 더하면 - 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다로 바뀐다. - 이는 아직 증명되지 않은 문제이기 때문에 "추측"이다. - 하지만 $10^18$이하에서는 참인 것이 증명되었기 때문에, 알고리즘 문제를 푸는데에는 전혀 문제가 없다. 문제 풀이 - 이 문제는 n의 최악의 경우가 100만이고, 테스트 케이스 문제이기 때문에 - 크기가 100만인 배열을 할당하여 미리 정답을 저장해놓고, 반복문을 통하여 입출력을 해야한다. - 입력은 짝수를 받으며, 짝수 = 홀수(소수) + 홀수(소수)이므로, 소수들을 미리 배열에 저장해놓는 방법을 사용한다. - 일단, 에라토스테네스의 체를 이용하여 100만..

문제 풀이 전 이론 - 1 - 해당 문제는 소수 찾기1과 동일하지만, 입력에서 최악의 경우가 실행 시간에 치명적인 영향을 미친다. - 기존의 방법으로 풀었으면 약수를 알아내는 시간 O($\sqrt{N}$)과 모든 N에 대한 O(N)로 인해 O(N$\sqrt{N}$)이 될 것이다. - 일단 최악의 경우가 백만이라고 하면 의심해봐야 한다...(꿀팁) - 이에 대한 문제를 효율적으로 해결할 수 있는 방법은 에라토스테네스의 체 알고리즘을 사용하는 것이다. 문제 풀이 전 이론 - 에라토스테네스의 체 - 1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다. - 이를 이용하면 N이 100만인 경우 + 테스트케이스 문제일 때, 모든 소수를 크기가 100만인 배열에 미리 저장해놓고, 입..

문제 풀이 전 이론 - 1 - 소수는 약수가 1과 자기 자신 밖에 없는 수이다. - N이 소수이기 위해서는 N/(2-(N-1))이 0으로 나누어 떨어져서는 안된다. - 소수를 구하는 방법은 두가지가 있다. - 1. 어떤 수 N이 소수인지 아닌지를 판별한다.(효율성을 크게 안따져도 되는 경우) - 2. N이하의 모든 소수를 다 구한다.(N의 맥시멈이 100만이어서 미리 저장해놓아야 하는 경우) - 해당 문제는 N의 최악의 경우가 치명적이지 않으므로 첫 번째 방법을 사용해보겠다. 문제 풀이 전 이론 - 2 - 어떤 수 N이 소수인지 아닌지를 판별하기 위해서는 N을 2~N-1로 나누었을 때 0이 나오는지 살펴보면 된다. - 하지만, 굳이 N-1까지 반복해볼 필요도 없다. 약수 파트에서 살펴보았듯이 약수는 대칭..

문제 풀이 전 이론 - 1 - 최대공약수는 줄여서 GCD라고 한다. - 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다. - 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나누어 보는 방법이 있다. - min(A,B)인 이유는 어차피 두 수의 공통된 약수 중 가장 큰 정수는 min(A,B)보다 크지 않기 때문이다. - 위의 이론은 O(N)이고, 입력이 10,000이하이기 때문에 시간 제한 1초 내에는 충분히 실행가능하다. - 하지만 이보다 더 빠른 방법으로 문제를 해결하기 위해 유클리드 호제법]을 사용해본다. int g =1; for(int i = 2; i

문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다. 예제입력 / 예제출력 5 1 / ..

문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 g(N)를 출력한다. 예제입력 / 예제출력 1 / 1 2 / 4 10 / 87 10000 / 82256014 문제 풀이 전 이론 - 1 - 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 ..

서론 약수 문제 중 기본적인 문제이다.(solved.ac : 실버5 문제) 문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다. 출력 첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다. 예제입력 / 예제출력 2 4 2 / 8 문제 풀이 - 우리가 구해야하는 N을 24라고 가정 하고 24의 약수를 나열해보면 1,2,3,4,6,8,12,2..