문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 실패(시간초과) 코드 import sys def isPrime(n): if n < 2: return False elif n == 2 or n == 3: return True elif n % 2..
Problem Solve/백준(Python)
문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. Solution 최대공약수 = 유클리드 호제법 최소공배수 = (A * B) / 최대공약수 유클리드 호제법이란 -> A % B = R -> B % R = R2 -> R % R2 = R3 -> R2 % R3 = 0 위와 같은 식이 세워졌을 때 최대공약수는 R3이다. 내 코드 import sys A, B = map(int, sys.stdin.readline().rstrip().split()) mul = A * B while True: r = A % B if r == 0: print(B) break A = B B = r print(mul//B)
문제 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다. baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다. 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오. Solution 인덱스 슬라이싱으로 접미사 리스트를 만든다. sort() 함수를 이용하여 접미사 리스트를 정렬한다. 내 코드 # 시간 복잡도 : O(n^2) import sys # S = "baekjoon" S = sys.stdin.readline().rstrip(..
문제 네 자연수 A, B, C, D가 주어진다. 이때, A와 B를 붙인 수와 C와 D를 붙인 수의 합을 구하는 프로그램을 작성하시오. 두 수 A와 B를 합치는 것은 A의 뒤에 B를 붙이는 것을 의미한다. 즉, 20과 30을 붙이면 2030이 된다. Solution 두 수를 합칠 때는 문자열로 처리하고 합을 구할 때는 정수로 처리한다. 내 코드 import sys ABCD = list(sys.stdin.readline().split()) print(int(ABCD[0] + ABCD[1]) + int(ABCD[2] + ABCD[3]))
문제 ROT13은 카이사르 암호의 일종으로 영어 알파벳을 13글자씩 밀어서 만든다. 예를 들어, "Baekjoon Online Judge"를 ROT13으로 암호화하면 "Onrxwbba Bayvar Whqtr"가 된다. ROT13으로 암호화한 내용을 원래 내용으로 바꾸려면 암호화한 문자열을 다시 ROT13하면 된다. 앞에서 암호화한 문자열 "Onrxwbba Bayvar Whqtr"에 다시 ROT13을 적용하면 "Baekjoon Online Judge"가 된다. ROT13은 알파벳 대문자와 소문자에만 적용할 수 있다. 알파벳이 아닌 글자는 원래 글자 그대로 남아 있어야 한다. 예를 들어, "One is 1"을 ROT13으로 암호화하면 "Bar vf 1"이 된다. 문자열이 주어졌을 때, "ROT13"으로 암호..
문제 문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오. 각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있다. 해결 방안 아스키 코드를 활용해서 96과 123 사이라면 소문자, 64와 91 사이라면 대문자, 32라면 공백, 나머지는 숫자로 처리했다. 내 코드 import sys while True: S = list(sys.stdin.readline().strip('\n')) if not S: break count = [0 for _ in range(4)] while S: asc = ord(S.pop()) if 96 < asc < 123: count[0] += 1 elif 64 < asc < 91: count[1] ..
문제 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. 내 코드 import sys S = list(sys.stdin.readline().rstrip()) count = [-1 for _ in range(26)] L = len(S) for i in range(L): idx = ord(S[i]) - 97 if count[idx] == -1: count[idx] += i+1 print(*count) -1로 구성되어 있는 리스트를 알파벳의 개수 크기만큼 만들고, 알파벳의 아스키 코드를 인덱스 번호로 활용하여 나온 순서를 입력한다. 똑같은 알파벳이 중복되어 나올 경우를..
알파벳 개수 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오. 해결방법 아스키 코드를 인덱스 번호로 활용해서 카운트하면 된다. 내 코드 import sys S = list(sys.stdin.readline().rstrip()) count = [0 for _ in range(26)] while S: count[ord(S.pop()) - 97] += 1 print(*count) 알파벳 개수를 25개로 착각하고 count list를 25 크기로 만들었다가 런타임 에러 발생 26으로 수정하니 해결됐다.
문제 후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오. 후위 표기식이란 ? 1 + 2 * 3 - D / E 이란 식이 있을 때 이 식을 중위 표기식으로 표현했다고 말한다. 이 식을 후위 표기식으로 바꾸면 1 2 3 * + D E / - 과 같다. 후위 표기식 -> 전위 표기식 과정 1 (2 * 3) + D E / - (1 + 2 * 3) D E / - (1 + 2 * 3) D / E - 1 + 2 * 3 - D / E 해결 방법 입력 받은 문자를 아스키 코드를 이용하여 정수로 처리하여 스택에 하나씩 집어 넣는다. 만약 문자일 경우 그냥 스택에 집어 넣고, 연산자일 경우에는 스택을 2번 pop하여 연산한다. 연산된 값은 다음 연산을 위해 다시 스택에 집..
