Passwd

에라토스테네스의 체 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 즉, 2부터 n까지의 모든 수를 나열한다. 지우지 않은 수 중 가장 작은 수를 찾는다. 이 수는 소수이다. 자기 자신을 제외한 소수의 배수를 모두 지운다. 더 지울 수가 없을 때까지 2 ~ 3 과정을 반복한다. 또는 \( \sqrt{n} \)의 정수부보다 작은 소수의 배수를 지우고 남는 수는 모두 소수이다. 그림의 경우, \( 11^2 > 120 \)이므로, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다. 구현 Python으로는 아래와 같이 구현할 수 있다. def prime_list(n): # 에라토스테네스의 ..

문제 https://www.acmicpc.net/problem/2998 창영이는 2진법 수를 8진법 수로 변환하려고 한다. 창영이가 사용한 방법은 아래와 같다. 1. 2진수의 길이가 3으로 나누어 떨어질 때까지 수의 앞에 0을 붙인다. 2. 그 다음, 3자리씩 그룹을 나눈다. 3. 아래의 표를 참고해 8진수로 바꾼다. 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 창영이가 사용한 방법을 이용해 2진수를 입력받아 8진수를 바꾸는 프로그램을 작성하라. 입력의 첫번째 줄에 2진수가 주어진다. 풀이 Python에서 2진수를 입력받는 방법과 정수를 8진수를 변환하는 방법을 알면 간단하게 해결할 수 있다. 1. int(x, base=10) int 함수의 base는 x의 진수에..

문제 https://www.acmicpc.net/problem/9081 단어를 입력받아, 그 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬할 때에 주어진 단어 다음에 나오는 단어를 찾는 프로그램을 작성하라. 입력 첫 줄은 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 알파벳 대문자로만 이루어진 단어로 공백은 없다. 풀이 파이썬에서 문자(chr)는 대소 관계 비교가 가능하므로 직전에 풀었던 2022.05.10 - [BOJ] 10972 - 다음 순열(next permutation) 문제를 활용하면 쉽게 풀어낼 수 있다. 차이가 있다면 값의 중복 여부인데, 이는 값을 교환할 위치 i - 1과 j를 찾아내려 갈 때의 조건을 크거나 같을 때 반복하도록 수정하면 된다. import sys..

문제 https://www.acmicpc.net/problem/1476 준규가 사는 나라에서는 숫자 E, S, M 3개를 이용해서 연도를 나타낸다. 그리고 이 세 수는 아래와 같은 범위를 가진다. 1 ≤ E ≤ 15 1 ≤ S ≤ 28 1 ≤ M ≤ 19 우리가 알고있는 1년은 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다. 예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. E S M 년도를 입력받아, 우리가 알고 있는 연도를 계산하라. 풀이 내 풀이 나는 연도를 증가시킨 후, 그 연도를 E S M 연도와 비교하는 방식을 사..

문제 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 1부터 N까지의 수로 이루어진 순열을 입력으로 받아, 사전 순으로 다음에 오는 순열을 구하여라. 사전 순으로 가장 첫 순열은 오름차순으로 이루어진 순열이고, 가장 마지막 순열은 내림차순으로 이루어진 순열이다. 예시 ) 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 입력 첫째 줄은 N을, 둘째 줄은 순열이 주어진다. 입력 받은 순열이 가장 마지막 순열인 경우에는 -1을 출력한다. 풀이 1. 순열의 오른쪽 끝에서부터..

문제 https://www.acmicpc.net/problem/10974 1 \( \leq \) N \( \leq \) 8인 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하라. 풀이 Python에 순열/조합과 관련된 라이브러리로 itertools를 지원하고 있어, 해당 라이브러리를 사용하였다. intertools의 permutations 모듈이 순열에 해당한다. permutations 함수는 interable한 데이터와 길이 r을 매개변수로 입력받아, r 길이의 시퀀스를 반환한다. tuple은 입력받은 iterable 순서에 따라 사전식 순서로 출력된다. 코드 from itertools import permutations import sys n = int(sys.stdin.re..

문제 https://www.acmicpc.net/problem/2556 자연수 n을 입력받은 후, 지금까지 안 나온 별 찍기 방식으로 n개의 줄에 걸쳐 별을 적절히 찍으세요. 풀이 문제가 꽤 당황스러운데…… 별 찍기 관련 문제는 https://www.acmicpc.net/workbook/view/20 에 모여있다. 별 찍기 문제를 1번부터 13번까지 확인해보면 직각삼각형, 이등변삼각형, 마름모, 나비 모양, 모래시계 모양 등을 출력하도록 요구하고 있는데, 정작 정사각형 모양은 요구한 적이 없는 것을 알 수 있다. 즉, 정사각형 모양이 되도록 별을 찍으면 된다. import sys n = int(sys.stdin.readline()) for i in range(n): print("*" * n)

문제 https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 두 집합 A와 B에 대해 (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 할 때, 그 원소의 개수를 구하여라. 예시 ) $$ A = \{1, 2, 4 \}, B = \{2, 3, 4, 5, 6 \}$$ $$ A-B = \{1 \}$$ $$ B-A = \{ 3, 5, 6\}$$ $$ A \triangle B=(A..

문제 https://www.acmicpc.net/problem/1748 첫째줄에 N을 입력받아, 1부터 N까지의 수를 이어서 쓴 하나의 수의 자릿수를 구하여라. 예시) n = 15 이어쓴 수 : 123456789101112131415 자릿수 : 21 풀이 틀린 풀이 N까지 이어서 쓴 수를 실제로 구한 뒤, 그 길이를 출력하는 방법을 썼다. import sys n = int(sys.stdin.readline()) print(len("".join([str(i) for i in range(1, n + 1)]))) 무식한 방법이었는지, 메모리 초과로 틀린 풀이였다. 맞은 풀이 i번째 자리수가 등장하는 개수와 N과의 관계를 생각해보자. 자릿수 범위 개수 1번째 (1의 자릿수) 1 ~ N N - 1 + 1 2번째 ..

문제 https://www.acmicpc.net/problem/1100 8 * 8 크기의 검정 칸과 하얀 칸이 번갈아가며 칠해진 체스판이 있다. 가장 왼쪽 위칸 (0, 0)이 하얀 칸이라고 할 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램을 작성하라. 말이 없는 칸은 "."로 표기하고, 말이 있는 칸은 "F"로 표기한다. .F.F...F F...F.F. ...F.F.F F.F...F. .F...F.. F...F.F. .F.F.F.F ..FF..F. 풀이 내 풀이 1. 체스판의 상태를 문자열 배열로 입력받는다. 2. 체스판을 탐색하며, 하얀 칸이면서(행과 열이 짝수이거나 행과 열이 홀수) 말이 있을 때 말의 개수를 1씩 증가시킨다. 3. 최종 확인된 말의 개수를 출력한다. 코드 import sy..