알고리즘
-
[Python] 백준 2609 최대공약수와 최소공배수Python_알고리즘 2021. 7. 11. 02:27
문제 바로가기 문제분석 # 유클리드 호제법으로 최대공약수를 구한 후, 그걸 힌트로 최소공배수를 구한다. a,b의 최대공약수 == b와 a%b의 최대공약수 a%b가 0이 될 경우(나머지가 없이 a가 b로 딱 떨어진다는 것이므로) b가 최대공약수 최소공배수는 두 값의 곱/최대공약수 # 유클리드 호제법의 예 24 - 1 2 3 4 6 8 12 24#24의 약수들 18 - 1 2 3 6 9 18# 18의 약수들 a = 24 b = 18 a, b = b , a % b 24, 18 = 18, 6 18, 6 = 6, 0 -> 나머지가 0이 되었으니 나누는 수 6이 24와 18의 최대공약수 문제풀이 a, b = map(int, input().split()) def gcd(a, b): while b > 0: a, b =..
-
[Python] 백준 1037 약수Python_알고리즘 2021. 7. 10. 02:46
문제 바로가기 문제분석 # n의 진짜 약수는 1과 자기 자신을 제외한 약수이다. # 예를 들어 10의 약수는 1, 2, 5, 10이지만 진짜 약수는 2, 5뿐이다. # 같은 방법으로 20은 1, 2, 4, 5, 10, 20이지만 진짜 약수는 2, 4, 5, 10이다. # 문제에서는 진짜 약수가 주어졌을 때, n을 구하는 프로그램을 작성하라고 했다. # 약수가 순서대로 정렬이 되었을 때, 제일 처음 나오는 약수와 제일 끝에 나오는 약수를 곱하면 n이 나오는 방법을 이용한다. 문제풀이 n = int(input()) real = list(map(int, input().split())) real.sort() print(real[0] * real[-1]) # 약수의 개수를 입력값으로 받는다. # 입력값으로 받는 ..
-
[Python] 백준 2869 달팽이는 올라가고 싶다Python_알고리즘 2021. 7. 9. 01:50
문제 바로가기 문제분석 # 달팽이가 하루에 올라가는 높이는 낮에 올라가는 높이(a) - 밤에 미끄러지는 높이(b) 이다. # 정상에 오르면 미끄러 지지 않는다. # 정상에 오르는데 n일이 걸린다면, n-1일까지는 a-b를 n-1번 반복하고 마지막 날 낮에 a만큼 올라가면 된다. # 이를 식으로 나타내면, v = (a - b) * (n -1) + a 문제풀이 import sys import math a, b, v = map(int, sys.stdin.readline().split()) day = math.ceil((v-a)/(a-b)) + 1 print(day) # input( )대신 sys.stdin.readline( )을 사용할수도 있다. # math 모듈의 ceil메소드 사용해서 소숫점 아래 반올림해..
-
[Python] 백준 1436 영화감독 숌Python_알고리즘 2021. 7. 8. 01:28
문제 바로가기 문제분석 # 666을 하나의 문자열로 취급해야한다. # 모든 종말의 수 중에서 n번째 나온 수는 n번째 영화의 제목이 된다. # 모든 수를 탐색하면서 666이 들어가 있는지 찾는 조건문과 # 입력값과 반복문으로 돌려서 나온 값을 비교하는 조건문이 필요하다. 문제풀이 n = int(input()) count = 0 name = 666 while True: if '666' in str(name): count += 1 if count == n: print(name) break name += 1 # 입력값으로 몇번째 영화인지 n이 들어온다. (반복문을 돌려 나온 값과 같은지 비교해야한다.) # 영화제목에 666이 들어가는지 찾는 변수를 초기화한다. 666부터 시작하는 이유는 제일 작은 종말의 수이..
-
[Python] 백준 4948 베르트랑 공준Python_알고리즘 2021. 7. 7. 03:17
문제 바로가기 문제분석 # 소수 구하는 방법을 함수로 만들고 이를 이용해 문제에서 주어진 범위에서 소수를 구한다. # 에라토스테네스의 체를 활용해야한다. # 2부터 시작해서 배수를 구하고, 특정 수의 배수라는 것은 소수가 아니라는 뜻이므로 그 배수를 소수에서 제외하는 방식이다. 문제풀이 # 에라토스테네스의 체 개념을 이용해 소수구하는 함수 만들기 def num(num): if num == 1: return False else: for i in range(2, int(math.sqrt(num)) + 1): if num % i == 0: return False return True all_list = list(range(2, 246912)) save_list = [] for i in all_list: if ..
-
[Python] 백준 1011 Fly me to the Alpha CentauriPython_알고리즘 2021. 7. 6. 03:34
문제 바로가기 문제분석 # 이동을 앞뒤로 한칸씩 밖에 못한다. # 시작과 도착 직전에는 한칸밖에 못움직인다. # 최소한의 작동횟수로 이동해야하므로 1씩 커지다가 대칭으로 1씩 줄어들게 움직인다. # 총 n번의 횟수로 갔다고 가정할 때, n-1번째 이동한 거리는 최대 2광년, n-2번째에 이동한 거리는 최대 3광년, n-3번째에 이동한 거리는 최대 4광년...... # 이런식으로 규칙을 찾아야 한다. 거리 최단루트 최소이동횟수 1 1 1 2 11 2 3 111 3 4 (2의 제곱) 121 3 (2*2-1) 5 1211 4 6 1221 4 7 12211 5 8 12221 5 9 (3의 제곱) 12321 5(3*2-1) 10 123211 6 11 123221 6 12 123321 6 13 1233211 7 1..
-
[Python] 백준 2839 설탕 배달Python_알고리즘 2021. 7. 4. 00:18
문제 바로가기 문제분석 # 봉지를 가작 적게 가져가야 하므로 5킬로그램으로 먼저 나누고 나머지가 있다면 3킬로그램으로 빼면서 계산하는게 핵심이다. # 무한루프를 돌리고 그 안에서 if문으로 조건을 걸어 break해주는데, break의 조건은 2개가 생긴다. # 하나는 모두 계산이 되어서 출력이 되었을 때, 다른 하나는 정확하게 N킬로 그램을 만들 수 없을때 이다. 문제풀이 N = int(input()) bag = 0 while True: if N % 5 == 0: bag += (N // 5) print(bag) break N -= 3 bag += 1 if N < 0: print(-1) break # 설탕 무게(N)를 입력값으로, 받고 설탕 봉지를 셀 변수를 초기화한다. # 무한루프를 만들고, 조건문으로 ..
-
[Python] 백준 2941 크로아티아 알파벳Python_알고리즘 2021. 7. 2. 01:45
문제 바로가기 문제분석 # 크로아티아 알파벳이 입력값으로 주어지고 표에 나와있는 알파벳은 변경된 형태로 입력된다. # 입력으로 주어진 단어가 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다. # 크로아티아 알파벳은 하나의 알파벳으로 쓰이고, 출력은 크로아티아 알파벳이 몇개인지 확인하는 것이므로 # 크로아티아 알파벳을 인덱스가 하나인 아무 알파벳으로 치환하는게 핵심이다. 문제풀이 words = input() croatia = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z='] for i in croatia: words = words.replace(i,'*') print(len(words)) # 입력값으로 크로아티아 알파벳을 받는다. # 크로아티아 알파벳을 리스트..