링크: https://www.acmicpc.net/problem/1759문제 이해이 문제를 처음 보았을 때, 백트래킹을 이용한 조합이라고 생각했다. 기본적으로 암호로 만들 수 있는 경우를 다 출력하는 문제인데 조건은 다음과 같다.암호는 최소 한 개의 모음과 최소 두 개의 자음의 조합이다.그리고 각 암호는 증가하는 순서로 배열되어있다. 백트래킹에 가지치기 잘 치면 될 것 같다 생각해서 코드를 작성했다.설명바로 문제 양식대로 백트래킹을 구현해 줬다.여기서 고민했던 부분은 최소 한 개의 모음과 최소 두 개의 자음이었다.생각을 해보니 모음을 선택 안 하는 기준은 전체 길이에서 현재 문자열의 모음 개수를 뺀 게 2보다 작거나 같다면즉, 자음 개수가 2보다 작으면 선택을 안 하면 되는 거였다.그리고 자음을 선택 안..

링크: https://www.acmicpc.net/problem/9019문제 이해이 문제를 처음 접했을 때, 내 머리는 이런 식으로 이해했다. 레지스터 \( n \) \( (0 \le n \le 10\,000) \) 이 있다. 그리고 명령어가 존재한다. 이는 D, S, L, R로 나뉜다.그리고 \( n \)의 네 자릿수를 \( d_1, d_2, d_3, d_4 \) 라고 한다.\( n = ((d_1 * 10 + d_2) * 10 + d_3) * 10 + d_4 \) 이다. 쉽게 이야기하면, \(d_i\)는 \(i\) 번째 수라 보면 된다. \( ( 1 \le i \le 4 ) \) 명령어 D, S, L, R은 다음과 같다.D: \( 2n \bmod 10\,000 \)S: \( n - 1 \) (만약 계산..

링크: https://www.acmicpc.net/problem/1193문제무한히 큰 배열에 다음과 같이 분수들이 적혀있다.1/11/21/31/41/5...2/12/22/32/4......3/13/23/3.........4/14/2............5/1.................................이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.입력첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.출력첫째 줄에 분수를 출력한다.제한시간0.5 초 (추가 시간 없음)첫번째 시도이 문제를 처음 접했..

링크: https://www.acmicpc.net/problem/17427문제두 자연수 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)를 출력한다.시간제한0.5 초 (추가 시간 없음)첫번째 시도이 문제를 처음 접했을 때는 "sqrt(N)까지 반복하면 되지 않을까?"라는 ..

링크: https://www.acmicpc.net/problem/24313문제오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.입력첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. $$(0 ≤ ..

링크: https://www.acmicpc.net/problem/10464문제S에서 F까지의 모든 정수를 XOR한 값은 무엇일까?입력입력의 첫 번째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다.다음 T 개의 줄에는 두 개의 정수 S와 F가 주어진다. (1 ≤ S ≤ F ≤ 1,000,000,000)출력각 테스트 케이스마다 S에서 F까지의 모든 정수를 XOR한 값을 출력한다.시간 제한1초첫번째 시도T = int(input())_ = [list(map(int, input().split())) for i in range(T)]for S, F in _: num = S for i in range(S+1, F+1): num ^= i print(num)문제를 처음..

에라토스테네스의 체는 무엇인가?에라토스테네스의 체는 소수를 구하는 알고리즘으로, 범위 내의 소수를 판별할때 유용하게 사용되는 알고리즘이다.소수를 마치 체로 걸러내는 방식과 유사하다고 하여, 에라토스테네스의 체라는 이름이 붙었다.작동 원리1. 1부터 N까지 숫자 배열을 생성한다.2. 1은 소수가 아니니 제거한다.3. 2부터 시작하여 그 수를 제외한 배수들을 다 제거한다.4. 그 후 1씩 증가하여 남은 숫자들도 3번과 똑같은 방식으로 진행한다. 예를 들어, 1부터 100까지의 범위에서 소수를 판별하고 싶다고 하자. 다음과 같이 1부터 100까지의 배열을 생성한다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454..