목록전체 글 (317)
지나가던 개발자
[Python] 백준 12871번(무한 문자열) 문제 풀이
import math s = input() t = input() if s*(math.lcm(len(s), len(t))//len(s)) == t*(math.lcm(len(s), len(t))//len(t)): print(1) else: print(0) f(s) == f(t)가 참임을 판별하려면 s와 t를 같은 길이로 만든 뒤 둘이 같은지 다른지 여부를 판별하면 된다.
[Python] 백준 11008번(복붙의 달인) 문제 풀이
for i in range(int(input())): s, p = input().split() print(len(s.replace(p, "아")))
[Python] 백준 11721번(열 개씩 끊어 출력하기) 문제 풀이
w = input() for i in range(len(w)//10+1): for j in range(i*10, (i+1)*10): try: print(w[j], end="") except: break print("")
[Python] 백준 10826번(피보나치 수 4) 문제 풀이
n = int(input()) if n < 3: if n == 0: print(0) else: print(1) else: f1 = 1 f2 = 1 for i in range(n-2): f2 += f1 f1 = f2 - f1 print(f2) n이 0 혹은 1의 수가 될 수 있음을 모르고 헤매다가 문제 읽고 알았다..
[Python] 백준 4821번(페이지 세기) 문제 풀이
while True: pages = [False for i in range(int(input()))] if len(pages) == 0: break toPrint = input().split(",") for i in toPrint: to_print = list(map(int, i.split("-"))) if to_print[0] > len(pages): continue if len(to_print) == 1: pages[to_print[0]-1] = True continue if to_print[0] > to_print[1]: continue if to_print[1] > len(pages): to_print[1] = len(pages) for j in range(to_print[0], to_print[..
[Python] 백준 8892번(팰린드롬) 문제 풀이
from itertools import permutations def is_palindrome(a): return a == a[::-1] for i in range(int(input())): tango = [] for j in range(int(input())): tango.append(input()) printed = False for j in permutations(tango, 2): if is_palindrome("".join(j)): printed = True print("".join(j)) break if not printed: print(0) 메모리 초과가 떠도 그닥 이상치 않다고 생각하고 있었는데 맞았다.
[Python] 백준 2941번(크로아티아 알파벳) 문제 풀이
print(len(input().replace("c=", "크").replace("c-", "로").replace("dz=", "아").replace("d-", "티").replace("lj", "아").replace("nj", "알").replace("s=", "파").replace("z=", "벳"))) 반복문을 사용해서 매우 귀찮게 구현할 수도 있다. i번째 요소와 i+1번째 요소를 비교해서 크로아티아 알파벳에 해당되면 i+1번째 요소를 지우고 length += 1을 해주는 뭐 그런 식으로 말이다. 그런데 이미 내장 함수 만드는 분들이 다 구현해 놓은 게 있는데 굳이 그렇게 해야 할까?
[Python] 백준 5800번(성적 통계) 문제 풀이
for i in range(int(input())): print("Class", i+1) classI = sorted(list(map(int, input().split()))[1:]) print("Max", str(max(classI)) + ", Min", min(classI), end=", ") largestGap = 0 for j in range(len(classI)-1): if classI[j+1] - classI[j] > largestGap: largestGap = classI[j+1] - classI[j] print("Largest gap", largestGap) 자꾸 틀렸습니다 떠서 "뭐지...?" 이러고 코드 살폈는데 맨 마지막 줄에 "Largest gap"을 "Largest Gap"이라고 ..
[C] 백준 25904번(안녕 클레오파트라 세상에서 제일가는 포테이토칩) 문제 풀이
#include int main() { int n, x; int t[200]; scanf("%d %d", &n, &x); for (int i=0; i
[Python] 백준 2167번(2차원 배열의 합) 문제 풀이
import sys n, m = map(int,sys.stdin.readline().split()) array = [] for i in range(n): array.append(list(map(int,sys.stdin.readline().split()))) for i in range(int(input())): toSum = list(map(int,sys.stdin.readline().split())) s = 0 for j in range(toSum[0]-1, toSum[2]): for k in range(toSum[1]-1, toSum[3]): s += array[j][k] print(s) 시간초과 때문에 PyPy3로 제출해야 풀린다.
[Python] 백준 15727번(조별과제를 하려는데 조장이 사라졌다) 문제 풀이
l = int(input()) if l % 5 == 0: print(l//5) else: print(l//5+1)
[C] 백준 2083번(럭비 클럽) 문제 풀이
#include int main() { while (1) { char name[10]; int age, weight; scanf("%s %d %d", &name, &age, &weight); if ((age == 0) && (weight == 0)) { break; } if ((age > 17) || (weight >= 80)) { printf("%s Senior \n", name); continue; } printf("%s Junior \n", name); } return 0; } while (1)을 통해 무한 반복을 할 수 있다!
[Python] 백준 1032번(명령 프롬프트) 문제 풀이
n = int(input()) if n == 1: print(input()) else: files = [] for i in range(n): files.append(input()) for i in range(len(files[0])): letter = files[0][i] printed = False for j in range(1, len(files)): if files[j][i] == letter: continue print("?", end="") printed = True break if not printed: print(letter, end="")
[Python] 백준 2587번(대표값2) 문제 풀이
nums = [] for i in range(5): nums.append(int(input())) print(int(sum(nums)/len(nums))) print(sorted(nums)[len(nums)//2]) 4번줄에서 평균이 소수로 나오면 어떻게 할까 하는 생각을 했는데, 문제를 다시 읽어보니 주어지는 자연수는 100보다 작은 10의 배수였다. 이게 왜 브론즈II?
[Python] 백준 20362번(유니대전 퀴즈쇼) 문제 풀이
n, s = input().split() nicks = [] chats = [] isNick = False for i in range(int(n)): nick, chat = input().split() if isNick: continue if nick == s: isNick = True nicks.append(nick) chats.append(chat) answer = chats[nicks.index(s)] ans = 0 for i in chats: if i == answer: ans += 1 print(ans-1)
[Python] 백준 13773번(Olympic Games) 문제 풀이
while True: year = int(input()) if year == 0: break if year % 4 == 0 and year >= 1896: if 1914
[Python] 백준 20977번(JOI ソート (JOI Sort)) 문제 풀이
n = int(input()) s = input() for i in ["J", "O", "I"]: print(i*s.count(i), end="") 정렬... 이라기보다는 "J", "O", "I"로 구성된 S를 입력받아서 S에 포함된 "J", "O", "I"의 개수를 세 준 뒤, "J", "O", "I" 순서대로 각각의 개수만큼 출력해 주었다.
[Python] 백준 24175번(Tokyo2020) 문제 풀이
from collections import Counter while True: players = [] for i in range(int(input())): d = input().split() players.append([int(d[0]), d[2]]) if players == []: break players.sort(key=lambda x:x[0]) print(Counter([x[0] for x in players if x[1] == 'Gold']).most_common(1)[0][0], Counter([x[0] for x in players]).most_common(1)[0][0]) 파이썬에서 리스트의 최빈값을 구하기 위해서는 from collections import Counter를 해준 후 Coun..
[Python] 백준 13985번(Equality) 문제 풀이
s = input().split(" = ") if eval(s[0]) == int(s[1]): print("YES") else: print("NO")
[Python] 백준 15965번(K번째 소수) 문제 풀이
n = int(input()) A = [False, False] + [True] * 7368788 Primes = [] for i in range(2, 7368788): if A[i]: Primes.append(i) for j in range(i+i, 7368788, i): A[j] = False print(Primes[n-1]) 에라토스테네스의 체 알고리즘을 사용했다. (덕분에 메모리가 145980KB...) 50만번째 소수는 7368788이다.
분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합정렬이 있다. 나무위키에서 인용했다. 거듭제곱 또한 분할 정복 알고리즘을 활용하여 빠르게 계산이 가능하다. 임의의 수 C에 대하여 Cⁿ을 구할 때는 C를 n번 곱하므로 시간 복잡도가 O(n)인 반면, 분할 정복을 활용하여 계산하면 O(logn)의 시간 복잡도로 계산이 가능하다. 훨씬 빨라지는 것이다. 분할 정복을 활용하여 거듭제곱을 계산하는 것은 다음과 같은 아이디어로부터 출발한다. $$ C^{n} = \begin{cases} ..
[Algorithm] 오일러 피 함수(Euler's phi function) | 서로소인 자연수의 개수 구하기 | Python
오일러 피 함수(Euler's phi function, ϕ)은 임의의 양의 정수 n과 서로소인 자연수의 개수를 구하는 함수이다. 1. n이 소수일 때 n이 소수일 때 ϕ(n)은 항상 (n-1)의 값을 가진다. 왜냐하면 소수는 모든 자연수와 서로소이기 때문이다. $$ n = ab (a, b \in N, a 1 $$ $$ \phi (n) = n-1 $$ 2. n이 소수의 거듭제곱일 때 n이 소수 p의 거듭제곱일 때에, ϕ(n)은 다음과 같이 계산된다. $$ n = p^{k} $$ $$ p = ab(a, b \in N, a 1 $$ $$ \phi (n) = p^{k-1} (p-1) $$ 3. m과 n이 서로소일 때 m과 n이 서로소일 때, mn과의 서로소의 개수는 m과의 서로소의 개수와 n과의 서로소의 개수의..
[Python] 백준 4355번(서로소) 문제 풀이
def power(A, n): res = 1 while n: if n % 2 != 0: res *= A A *= A n //= 2 return res def factorization(x): d = 2 factorization = [] while d
[Python] 백준 6992번(Arithmetic Sequence) 문제 풀이
for i in range(int(input())): sequence = list(map(int, input().split()))[1:] if len(sequence) == 0: continue if len(sequence) == 1: print("The next 5 numbers after [" + str(sequence[0]) + "] are: [", end="") for i in range(1, 6): if i == 5: print(str(sequence[0]+i) + "]") continue print(str(sequence[0]+i) + ", ", end="") elif len(sequence) == 2: print("The next 5 numbers after [" + str(sequence[..
[Python] 백준 1546번(평균) 문제 풀이
input() grade = list(map(int, input().split(" "))) m = max(grade) for i in range(len(grade)): grade[i] = grade[i]/m*100 print(sum(grade)/len(grade))
[Mathematics] 삼각형의 한 변과 양 끝각을 알 때의 넓이 구하기
삼각형이 결정될 때, 일반적으로 그 결정조건을 가지고 넓이를 구할 수 있다. 예를 들어, 삼각형의 세 변을 알 때는 헤론의 공식을 사용하고, 삼각형의 두 변과 그 끼인각을 알 때에는 삼각비를 활용하여 넓이를 구한다. 그런데 삼각형의 한 변과 양 끝각을 알 때에는 그 넓이를 어떻게 구할까? 그 공식을 알아내 보도록 하자. 다음과 같은 삼각형에서 a와 각B, 각C를 알고 있다. 삼각형의 내각의 합은 180도이므로 각A 또한 결정된다. 여기서 다음과 같은 사인법칙은 자명하다. $$ \overline{BC} = a $$ $$ \overline{AC} = b $$ $$ \overline{AB} = c $$ $$ \frac{a}{sinA} = \frac{b}{sinB} = \frac{c}{sinC} $$ a와 B,..
[Python] 백준 10769번(행복한지 슬픈지) 문제 풀이
message = input() if message.count(":-)") == 0 and message.count(":-(") == 0: print("none") elif message.count(":-)") == message.count(":-("): print("unsure") elif message.count(":-)") > message.count(":-("): print("happy") else: print("sad") 파이썬은 PS 치트다...
[Python] 백준 11816번(8진수, 10진수, 16진수) 문제 풀이
x = input() if len(x) == 1: print(x) elif x[1] == "x": print(int(x, 16)) elif x[0] == "0": print(int(x, 8)) else: print(x)
[Python] 백준 1357번(뒤집힌 덧셈) 문제 풀이
def rev(x): return int(x[::-1]) x, y = input().split(" ") print(rev(str(rev(x)+rev(y))))
[Mathematics] 삼각형의 닮음을 이용한 피타고라스 정리의 증명
혼자서 끄적끄적 하다가 찾은 피타고라스 정리의 증명이다. 뭐 물론 내가 증명하기 전에도 여러 사람들이 같은 증명법으로 증명했겠지만, 그래도 내가 찾은 방법이니 블로그에 올려본다. 각 C가 직각인 직각삼각형 ABC에서 다음과 같이 나타내어 보자. $$ \overline{bc} = a $$ $$ \overline{ac} = b $$ $$ \overline{ab} = c $$ $$ \overline{bd} = m $$ $$ \overline{ab} = n $$ 그런데, 다음과 같이 삼각형 DBC와 삼각형 DCA, 삼각형 CBA가 닮음임을 보일 수 있다. $$ \angle{A} + \angle{B} = 90° $$ $$ \angle{BCD} = \angle{A}, \angle{ACD} = \angle{B} $$..