빅오 표기법(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억으로 계산하여 알고리즘이 대략 몇..
A - Single Wildcard Pattern Matching 최대 1개의 *(와일드카드)가 있는 문자열 s로 문자열 t를 표현할 수 있는 지를 묻는 문제이다.*의 인덱스 번호를 기준으로 앞, 뒤가 문자열 t 앞과 뒤에 있으면서도겹쳐서는 안되므로 t은 문자열의 길이는 s-1보다 작으면은 안된다.이 두 조건에 유의하며 코드를 작성하면 풀 수 있는 문제이다. B - Pair of Toys 1~N까지의 수 중 서로 다른 2개의 수를 골라 이들의 합이 K를 만족하는 경우의 수를 출력하는 문제이다.N이 K-1보다 같거나 클 경우 K/2가 가능하나 K가 6일 때 (3, 3)과 같은 경우를 제외해주어야 하므로K/2가 짝수 일 때는 1을 빼주어야 한다.이외의 경우에는 max(0, (N-K/2))로 일반화 할 수 있..
3051번: 군사 기지 - 계산 기하 N개의 선분이 주어질 때, 세 명의 사람이 한 선분 위에 있지 않으나세 명의 사람이 이어져 있을 수 있는 방법의 가지 수를 묻는 문제이다. 즉 쉽게 얘기하면 N개의 선분을 그렸을 때 그 위에서 찾을 수 있는 삼각형의 개수이다.처음에는 N개의 선분에서 3개를 골라 이들이 삼각형을 이루는 지 확인하였다.선택한 세 선분 a, b, c로 삼각형을 만들 수 있는 지 확인하는 방법은 다음과 같이 진행하였다. 1. a와 b, b와 c, c와 a는 교점을 가진다.2. a와 b의 교점이 c 위에 있어서는 안된다. 이렇게 문제에 접근 할 경우 문제가 되는 경우는 평행한 두 선분이 합쳐질 수 있을 때이다.즉, a = (0, 2), b = (0, 4), c = (0, 3), d = (0,..
3044번: 자전거 경주 준비하기 - 위상정렬 N개의 마을이 M개의 일방통행 도로로 연결되어 있을 때1번 마을에서 시작하여 2번 마을로 끝나는 경로의 수를 구하는 문제이다. 접근 방법은 다음과 같다.1번 마을에서 X번 마을까지의 경로의 수는 X번 마을이 도착점으로 연결되어 있는 마을의 경로의 수의 합과 같다.즉 X번 마을이 도착점으로 연결되어 있는 마을의 경로의 수를 모두 구한다면 이들을 합하여 구할 수 있을 것이다.이는 그래프를 위상정렬한 순서대로 경로의 수를 구해주면 된다는 것을 알 수 있다. 먼저 1번 마을부터 2번 마을로 갈 수 있는 간선들만 모은 그래프를 다시 재생성 하여야 한다.이유는 위상정렬은 사이클이 없는 방향 그래프(DAG)에서만 할 수 있는데사이클이 있으면 무조건 inf를 출력해줘야한다..
2014번: 소수의 곱 - 우선순위 큐 K개의 소수들을 중복을 허용하여 곱했을 때의 값들을 오름차순으로 나열했을 때,N번째 오는 수를 출력하는 문제이다. 가장 먼저 생각나는 방법은 수들을 정렬한 뒤 가장 작은 수를 제거하고,그 수를 이용하여 만들 수 있는 수들을 추가하여 정렬해주면 될 것이다.예제와 같이 수 2, 3, 5, 7을 이용하여 수를 만든다면처음에는 2를 제거하고 2*2, 2*3, 2*5, 2*7값인 4, 6, 10, 14을 추가해주며 정렬한다.그러면 3, 4, 5, 6, 7, 10, 14가 될 것이며 또 3을 제거한 뒤3*2, 3*3, 3*5, 3*7값인 6, 9, 15, 21을 추가하여 정렬해주면 될 것이다.원소를 추가/제거를 하면서 반복적으로 정렬을 해야하기에 우선순위 큐를 사용하면 효율적..
1351번: 무한 수열 - DP N, P, Q가 주어질 때,A[0] = 1A[i] = A[i/P] + A[i/Q]인 점화식을 만족하는 A[N]을 구하는 문제이다. 이와 같이 간단한 점화식은 중복되는 부분문제를 저장하는 DP기법을 사용하려고 접근하지만N이 최대 10^12이기에 부분문제를 저장하는 배열을 선언할 수 없다.그러나 점화식을 자세히 보면 i가 계속 P, Q로 나누어지는데P와 Q가 최소값인 2일 때에도 2^40 >= 10^12이기에 각각 40보다 많은 항을 보지 않는 것을 알 수 있다.이에 부분문제를 담는 배열을 지수에 대한 값을 인자로 두어dp[41][41]와 같이 표현한 뒤 점화식을 세워 문제를 풀 수 있다. 또다른 방법으로는 적은 값만 참조하기에 map을 이용하여value값이 0이라면 값을 업..
A - Death Note 한 페이지에 m개의 이름을 적을 수 있으며 매일 이름을 이어서 적을 때,하루마다 몇페이지를 넘기는 지를 구하는 문제이다.이전까지 이 페이지에 적었던 이름이 sum개, 이 날 적어야 하는 이름이 X개라면(sum + X) / m개의 페이지를 넘겨야 하며 마지막 페이지에는 (sum + X) % m개의 이름이 있다는 것을 알 수 있다.매번 sum값을 업데이트 해주며 (sum + X) / m값을 출력하면 풀 수 있는 문제이다. B - Segment Occurrences q개의 쿼리동안 문자열 s[l ... r]에 문자열 t가 몇 번 나타나는 지를 출력하는 문제이다.n, m이 10^3로 비교적 작기에 완전탐색으로 O(nm)에 문자열 s에서 t가 어느 인덱스부터 등장하는 지 찾아낼 수 있다..
3955번: 캔디분배 - 선형 다오판토스 방정식, 확장 유클리드 알고리즘 구매하고 싶은 캔디는 K*X+1개이며 사탕 한 봉지에 사탕이 C개 들어있을 때 몇 봉지를 사야할 지 묻는 문제이다. 이 때 이를 수식으로 적어보면 K*X+1 = C*N가 되며 이 수식을 만족하는 10^9이 넘지 않는 N을 구해주면 된다.K*X+1 = C*N는 C*N - K*X = 1로 변환 될 수 있다. 이 형태는 일차부정방정식의 형태로,먼저 선형 다오판토스 방정식에 의하여 일차부정방정식 ax + by = c이고 d = gcd(a, b)라 할 때d | c 즉 c를 d로 나누었을 때 나누어떨어지지 않는다면 해가 존재하지 않으며,그렇지 않다면 해가 무수히 존재하며 이 수식을 만족하는 하나의 특수 해를 구한다면 일반 해를 구해낼 수 있다..
1837번: 암호제작 - 문자열의 나머지 구하기 P와 K를 입력받아 P라는 숫자가 소수 p,q의 곱으로 나타내질 때,p와 q 중 하나라도 K보다 작은 p, q가 있을 경우 BAD와 두 소수 중 작은 소수를 출력하고없을 경우 GOOD을 출력하면 되는 문제이다. 간단하게 생각해보면 K범위가 10^6까지 이므로 10^6까지의 모든 소수를 에라토스테네스 체를 이용하여 구한 뒤P라는 수에 그 소수들을 하나하나 나누어 본 뒤 하나라도 나누어진다면 BAD,안나누어진다면 GOOD을 출력하면 되는 간단한 문제이다. 이 때 문제가 되는 부분은 P의 범위가 10^100으로 int, long long 자료형으로는 받을 수 없기에이를 문자열을 사용해서 받아야한다. 이 때 문자열을 정수로 나눈 나머지를 나머지 연산을 이용하여re..
A - Balloons 서로 packet을 나누어 가질 때 하나 이상의 packet을 가지며 packet에 들어있는 풍선의 수는 같지 않게 해야할 때어떤 packet의 인덱스를 가져갔는 지 출력하는 문제이다.N이 1일 때에는 무조건 한 명은 packet을 받지 못하니 불가능하고packet에 있는 풍선의 수들을 정렬한다면 가장 적은 수의 풍선이 든 packet은 N이 2일 때를 제외하고는나머지 packet들의 풍선을 더했을 때보다 무조건 적다는 것을 알 수 있다.그러므로 N이 1 또는 N이 2이며 두 packet에 들어있는 풍선의 개수가 같은 경우는 -1,아닌 경우에는 풍선이 가장 적은 packet을 제외한 packet의 인덱스 번호를 출력해주면 된다.인덱스 번호를 출력해야함을 조심하자 B - Cuttin..