9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 시간 제한 1초 메모리 제한 128MB 문제 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-..

24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 시간 제한 1초 메모리 제한 512MB 문제 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자. 피보나치 수 재귀호출 의사 코드는 다음..

Intro Attention Is All You Need 논문에선 $Q$와 $K$ 벡터의 유사도를 0 ~ 1 사이의 확률 값으로 정규화하기 위해서 Dot-product Attention를 사용한다. 이때, Dot-product Attention을 그대로 사용하지 않고 $K$벡터의 차원 값인 $d_k$를 활용하여 scaling된 형태로 사용한다. $$Attention(Q, K, V) = softmax(\frac{QK^{T}}{\sqrt d_k})V$$ scaling의 근거는 논문에서 언급되며 다음과 같다. $d_k$가 커지면 $QK^{T}$ 값이 커진다. $QK^{T}$ 값이 커지면 softmax 함수의 gradient vanishing이 발생한다. scaling을 통해서 gradient vanishing..

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 시간 제한 1초 메모리 제한 256MB 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이..

문제 확인 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 시간 제한 : 1초 메모리 제한 : 256MB 나의 풀이 부분 합 개념을 이용해서 풀었다. 이때, 부분 합을 계산한 배열을 $i, j$로 순차적으로 접근할 경우 $O(N^2)$으로 시간 초과가 발생한다. 따라서 다른 방식으로 풀이해야 하고, 풀이는 다음과 같다. 미리 구해둔 prefix sum에서 부분 합을 구하려면 P[j] - P[i - 1]의 과정을 거쳐야 한다. 이때, P[j]와 P[i-1]이 각각 ..

16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 시간 제한 1초 메모리 제한 256MB 문제 승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다. '문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.' 승재를 도와 특정 문자열 S, 특정 알파벳 $\alpha$와 문..

2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 시간 제한 1초 메모리 제한 128MB 문제 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 아래와 같다. 이때, 온도의 합이 가장 큰 값은 21이다. 또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간..

11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 시간 제한 1초 메모리 제한 256MB 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한..

구간 합 N개의 수에 대해서 M개의 구간 정보로 구간 합을 구해야 하는 경우 구간 합을 완전 탐색을 통해서 구할 경우 O(NM)의 시간 복잡도 결국 N, M이 클 경우 별도의 방법 필요 누적합(Prefix sum) N개의 수는 변하지 않고 그대로이며 M개의 구간 정보만 바뀌는 상황일 때, N개의 수에 대한 누적합을 계산하여 별도의 리스트에 미리 저장해줌 필요한 시간 복잡도 O(N) 이 경우 M개의 구간 정보 L, R에서 구간 합을 구할 경우 P[R] - P[L-1]을 통해서 빠르게 구할 수 있음 인덱싱만 하면 되기 때문에 각 구간 정보당 O(1)의 시간 복잡도를 가지게 됨 따라서 구간 합을 구할 때 누적합을 이용하게 되면 O(N + M)의 시간 복잡도만으로 가능하다. 참고 이것이 취업을 위한 코딩 테스트..

2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 시간 제한 2초 메모리 제한 128MB 문제 $n \choose m$의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000)이 들어온다. 출력 첫째 줄에 $n \choose m$의 끝자리 0의 개수를 출력한다. 예제 입력 1 25 12 예제 출력 1 2 나의 풀이 숫자의 범위가 20억이기 때문에 for문을 통해서 N까지 순회하면 시간 초과가 발생한다. 따라서 5, 2의 인수의 개수를 몫의 성질로 빠르게 구한다. 팩토리얼 0의 개수에선 5의 개수만 알더라도..

1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 시간 제한 2초 메모리 제한 128MB 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 예제 입력 1 10 예제 출력 1 2 예제 입력 2 3 예제 출력 2 0 나의 풀이 마지막 숫자가 0이려면 10이 곱해져야 함 따라서 팩토리얼 구성 숫자들을 소인수 분해하여 만들 수 있는 10의 개수를 계산하면 됨 N = int(input()) count_2 = 0 count_5 = 0 for i in ra..

문제 확인 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 시간 제한 : 1초 메모리 제한 : 128MB 나의 풀이 못 풀었다. 시도한 풀이는 다음과 같다. 시간 복잡도만 생각하지 말고 메모리도 생각하면서 문제를 풀어야 겠다는 교훈을 얻었다... 여러 타입의 옷이 입력됐을 때 타입의 종류를 조합으로 결정한 뒤 풀이를 시도했다. 타입의 종류가 클 경우 조합 선택 시 메모리 초과가 발생했다. 시간 복잡도 말고 메모리에 대..