[TIL]20210729
알고리즘
1934 (백준)
from math import gcd
num=int(input())
for _ in range(num):
n,m = map(int, input().split())
print(n*m//gcd(n, m))
유클리드 호제법 (a*b/최대공약수)
을 이용한다.
18245 (백준)
풀이 1번
while 1:
inp = input()
if inp == 'Was it a cat I saw?':
break
a=1
print(inp[::a+1])
풀이 2번
a = 1
while 1:
inp = input()
if inp == 'Was it a cat I saw?':
break
for i in range(0, len(inp), a + 1):
print(inp[i], end="")
print()
a += 1
[a:b:c] 에서 a는 시작, b는 끝, c는 간격이다. 이때 c는 조작이 가능하다.
17502 (백준)
num = int(input())
str = list(input())
for i in range(num):
if str[i]=='?' and str[-(i+1)]=='?':
str[i]='a'
str[-(i + 1)]='a'
if str[i] != str[-(i + 1)]:
if str[i] == '?':
str[i] = str[-(i + 1)]
else:
str[-(i + 1)] = str[i]
print(''.join(str))
여기서 핵심은 str을 인풋받을때 List로 받는 것이다. str 타입으로 받으면 리스트이기때문에 인덱스 접근은 가능하지만 수정은 불가능해서 자리에 맞는 값으로 바꿀려면 매우 귀찮아질거같아서 애초부터 리스트로 받고 나중에 join을 이용해 합쳤다!
3943 (백준)
시간초과.
cnt = int(input())
for _ in range(cnt):
i = 0
num = [0 for i in range(500)]
inp = int(input())
num[0] = inp
while num[i] != 1:
if int(num[i]) % 2 == 0:
num[i + 1] = int(num[i]) / 2
else:
num[i + 1] = int(num[i]) * 3 + 1
i += 1
num.sort(reverse=True)
print(num[0])
정답
1번.
import sys
cnt = int(sys.stdin.readline())
for _ in range(cnt):
i = 0
num = [0 for i in range(500)]
inp = int(int(sys.stdin.readline()))
num[0] = inp
while num[i] != 1:
if int(num[i]) % 2 == 0:
num[i + 1] = int(num[i]) / 2
else:
num[i + 1] = int(num[i]) * 3 + 1
i += 1
num.sort(reverse=True)
print(num[0])
2번.
import sys
cnt = int(sys.stdin.readline())
for _ in range(cnt):
i = 0
num = []
inp = int(int(sys.stdin.readline()))
while 1:
if 1 in num:
break
num.append(inp)
if inp % 2 == 0:
inp //= 2
else:
inp = inp * 3 + 1
print(max(num))
시간초과때문에 input
대신 sys.stdin.readline()
를 쓰고 제출도 pypy로 했다.
10989 (백준)
오답
import sys
num=int(sys.stdin.readline())
c = []
for _ in range(num):
c.append(int(sys.stdin.readline()))
for i in sorted(c):
sys.stdout.write(str(i) + '\n')
조금씩 수정하면서 5번정도 제출했지만 모두 메모리 초과가 떠서 인터넷의 도움을 받았다.
import sys
n = int(sys.stdin.readline())
b = [0] * 10001
for i in range(n):
b[int(sys.stdin.readline())] += 1
for i in range(10001):
if b[i] != 0:
for j in range(b[i]):
print(i)
어떤차이가 있는지 모르겠어서 백준에 질문을 남겨 이유를 들었다.
입력되는 횟수를 카운트하는counting sort
라는 알고리즘이라고 한다.
리스트를 이용한 시간복잡도는 O(n)이지만 일반적인 정렬은 O(n log n)이다.
Author And Source
이 문제에 관하여([TIL]20210729), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kid_chang/TIL20210729저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)