1222번: 홍준 프로그래밍 대회 - 수학 N개의 수가 주어질 때 이들 중 X로 나누어 떨어지는 수의 개수 * X의 값의 최대값을 출력하는 문제이다.N은 최대 200,000이며 수의 최대값은 2,000,000으로 N^2으로 보는 방법은 당연히 시간 초과이다.풀이는 이러하다. 2,000,000여개를 담을 수 있는 배열 A을 만든 뒤 이 배열에는 수들의 개수를 담는다.그 다음 1 ~ 2,000,000를 보며 지금 보는 수를 X라 할 때 A[X], A[2*X], A[3*X] ... 의 값을 더한다면X로 나누어 떨어지는 수의 개수가 된다.이들 중 2이상인 수에 대해 X와 곱한 값이 가장 큰 값을 출력하면 풀 수 있는 문제이다. 이 때의 시간복잡도를 계산해보면 2,000,000개의 모든 수를 X가 1일 때는 2,..
A - Palindromic Twist 문자열 s가 주어질 때 이 문자열의 모든 글자를 그 글자 알파벳의 다음 알파벳, 또는 이전 알파벳으로 바꾸어펠린드롬을 만들 수 있는 지 없는 지 판단하는 문제이다.간단한 구현 문제인데 실제 대회에선 많은 Hack이 나온 문제 중 하나였다.이는 a와 z같은 양 끝 알파벳은 각각 b, y로만 바뀔 수 있으며 서로 바뀌지는 않는다. (순환 형태가 아니다.)이에 대한 조건만 조심하면 쉽게 풀 수 있는 문제이다. B - Numbers on the Chessboard 정해진 규칙에 따라 n*n 체스보드를 채워나갈 때 x열 y행에 적혀있는 숫자는 무엇인지 출력하는 문제이다.n이 짝수일 때 홀수일 때, x + y가 짝수일 때 홀수일 때로 나누어 수식을 세워 계산하였다.예를 들어 ..
빅오 표기법(Big-O Notation)이란 계수와 낮은 차수의 항을 제외하고 수식을 표기하는 방법입니다.이 표기법은 문제를 해결하는데 걸리는 시간과 입력의 함수관계를 뜻하는 시간 복잡도(Time Complexity)와공간과 입력의 함수관계를 뜻하는 공간 복잡도(Space Complexity)를 표현하는데에 사용하며이를 이용하여 문제에서 주어지는 시간 제한과 메모리 제한에 적절한 코드인지 코드를 작성하기 전 확인할 수 있습니다.많이 사용하는 빅오 표기법의 대소 관계는 아래와 같습니다. O(1) < O(lgN) < O(N) < O(NlgN) < O(N^2) < O(N^3) < O(2^N) < O(N!) 문제에서 주어지는 최대 N에 대하여 시간복잡도에 대입하였을 때1초당 1억으로 계산하여 알고리즘이 대략 몇..