코테용 문제풀이/백준

골드바흐 파티션 풀이

문제 링크: https://www.acmicpc.net/problem/17103 백준 알고리즘 기초 1/2 301에서 6번째 - 17103번 골드바흐 파티션을 풀어보았다. 풀이: 골드바흐 파티션의 수를 구하는 문제이다. 파이썬의 경우, 기존의 에라토스테네스의 체를 이용하는 코드는 하도 시간초과가 나서 https://week-year.tistory.com/171 이 코드를 사용했다. C++ Python def get_primary_list(n): array = [1 for _ in range(n+1)] for i in range(2, int(n ** 0.5) + 1): if array[i]: j = 2 while i * j

-2진수 풀이

문제 링크: https://www.acmicpc.net/problem/2089 백준 알고리즘 기초 1/2 301에서 5번째 - 2089번 -2진수를 풀어보았다. 풀이: -2진수로 바꾸는 문제인데, 진법계산을 할 때 나머지가 +1로 고정되게(-1이 안되게) 계산을 해야 한다. C++ Python n=int(input()) res="" if n==0: print(0) # 0이 입력이면 else: while n: if n%-2==0: res+='0' n//=-2 else: res+='1' n=n//-2+1 print(res[::-1]) # 거꾸로 출력 Java

8진수 2진수 풀이

문제 링크: https://www.acmicpc.net/problem/1212 백준 알고리즘 기초 1/2 301에서 4번째 - 1212번 8진수 2진수를 풀어보았다. 풀이: 8진수를 받아 2진수로 출력한다. C++ Python print(bin(int(input(),8))[2:]) Java

2진수 8진수 풀이

문제 링크: https://www.acmicpc.net/problem/1373 백준 알고리즘 기초 1/2 301에서 3번째 - 1373번 2진수 8진수를 풀어보았다. 풀이: 2진수를 8진수로 바꾼다. 파이썬의 경우, 0o를 지우기 위해 [2:]를 썼고, input() 뒤에 숫자를 넣으면 그 수의 진법대로 받는다는 것을 알게 되었다. C++ Python print(oct(int(input(),2))[2:]) Java

숨바꼭질 6 풀이

문제 링크: https://www.acmicpc.net/problem/17087 백준 알고리즘 기초 1/2 301에서 2번째 - 17087번 숨바꼭질 6을 풀어보았다. 풀이: 내 위치와 동생들의 위치의 차를 절댓값으로 구하고, 최대공약수를 구하면 된다. C++ Python import math n,m=map(int,input().split()) arr=list(map(int,input().split())) for i in range(n): arr[i]=abs(arr[i]-m) # 절대값 res=arr[0] for i in range(1,n): res=math.gcd(res,arr[i]) print(res) Java

GCD 합 풀이

문제 링크: https://www.acmicpc.net/problem/9613 백준 알고리즘 기초 1/2 301에서 1번째 - 9613번 GCD 합을 풀어보았다. 풀이: 어렵게 생각하지 말고, 숫자들끼리 gcd를 하나하나 구해 더하면 된다. C++ Python import math n=int(input()) for i in range(n): ts=list(map(int,input().split())) sum=0 for j in range(1,ts[0]+1): for k in range(j+1,ts[0]+1): sum+=math.gcd(ts[j],ts[k]) print(sum) Java

골드바흐의 추측 풀이

문제 링크: https://www.acmicpc.net/problem/6588 백준 알고리즘 기초 1/2 300에서 6번째 - 6588번 골드바흐의 추측을 풀어보았다. 풀이: 짝수를 두 홀수의 합으로 보일 수 있는지 알아보는 문제이다. 파이썬의 경우, 리스트를 쓰면 시간초과가 나서 에라토스테네스의 체 함수를 딕셔너리로 출력하게 해서 key의 value가 true면(소수이면) 합을 출력하게 했다. C++ Python import sys def primes(n): sieve = [True] * n m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i] == True: for j in range(i+i, n, i): sieve[j] = False return {i:..

접미사 배열 풀이

문제 링크: https://www.acmicpc.net/problem/11656 백준 알고리즘 기초 1/2 203에서 9번째 - 11656번 접미사 배열을 풀어보았다. 풀이: 한글자씩 줄여가며 배열에 넣고, 정렬해 출력하면 된다. C++ Python s=input() res=[] for i in range(len(s)): res.append(s[i:]) res.sort() for i in res: print(i) Java

네 수 풀이

문제 링크: https://www.acmicpc.net/problem/10824 백준 알고리즘 기초 1/2 203에서 8번째 - 10824번 네 수를 풀어보았다. 풀이: 두 수끼리 붙이고, 합을 구한다. C++ Python a,b,c,d=input().split() ab=a+b cd=c+d print(int(ab)+int(cd)) Java

ROT13 풀이

문제 링크: https://www.acmicpc.net/problem/11655 백준 알고리즘 기초 1/2 203에서 7번째 - 11655번 ROT13를 풀어보았다. 풀이: 알파벳에 13을 더해 암호화한다. 알파벳의 범위를 넘어가지 않게 해야 한다. C++ Python inp=input() res="" for i in inp: if i.isupper(): # 대문자 a=ord(i)+13 if a>90: a-=26 # 넘어가면 res+=chr(a) elif i.islower(): # 소문자 a=ord(i)+13 if a>122: a-=26 # 넘어가면 res+=chr(a) else: res+=i print(res) Java