Algorithm Study
[백준 파이썬] 에라토스테네스의 체
에라토스테네스의 체 스터디를 통해 이해했던 내용을 바탕으로 정리해보았다. 수학적으로 정확하게 풀어냈다기 보단 스스로 이해한 바를 정리한 것으로 참고만 하길 바란다. 합성수 여부 판단 에라스토테네스의 체를 통해 소수와 합성수 여부를 판단할 수 있다. ※ '소수 2개의 곱를 이용해서 합성수를 만들 수 있다' 는 가정에서 시작한다. N = 6일 때(N>1), 6은 합성수에 해당한다. 합성수는 2개의 숫자 곱으로 표현할 수 있다. 이때 작은 수를 K, 큰 수를 L로 둔다. ex) 6 = 2 * 3 $$ 1
[백준 파이썬] #11729 하노이 탑 이동 순서
Silver II # 11729 하노이 탑 이동 순서 11729번: 하노이 탑 이동 순서 (acmicpc.net) 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 구글링을 통해 답을 확인하고 해석하였다. def hanoi_tower(n, start, by, end): if n == 1: print(start, end) return # 1개의 블럭일 때 start에서 end로 이동 hanoi_tower(n-1, start, end, by) # n-1개의 블럭을 start에서 by로 이동 print(s..
[백준 파이썬] #3135 라디오
Siver IV # 3135 라디오 https://www.acmicpc.net/problem/3135 3135번: 라디오 첫 줄엔 정수 A와 B가 주어진다 (1 ≤ A, B < 1000, A ≠ B). 다음 줄엔 정수 N이 주어진다 (1 ≤ N ≤ 5). 다음 N개의 줄엔 미리 지정되어 있는 주파수가 주어진다 (주파수는 1000 보다 작다). www.acmicpc.net 풀이 A, B = map(int, input().split()) N = int(input()) record = [abs(int(input())-B) for i in range(N)] print(min(abs(A-B), min(record)+1)) 문제를 잘 읽어야 한다 저장된 버튼이 1개이고, 그 아래에 인덱스로 채널이 저장되있던 것으로..
[백준 파이썬] #14646 욱제는 결정장애야!!
Silver IV # 14646 욱제는 결정장애야!! https://www.acmicpc.net/problem/14646 14646번: 욱제는 결정장애야!! 욱제는 매일 세계사에 한 획을 그을만한 심각한 비결정론적 문제에 직면한다. 그렇다. 바로 저녁메뉴를 고르는 것이다. 매일 반복되는 중대한 선택에 지친 욱제는 N일 동안의 저녁메뉴를 미리 www.acmicpc.net 내가 작성했던 코드 # 시간초과 N = int(input()) bbopgi = list(map(int, input().split())) pan = [] cnt = [] for i in bbopgi: if i not in pan: pan.append(i) elif i in pan: pan.remove(i) cnt.append(len(pan)..
[백준 파이썬] #11653 소인수분해
Siver IV # 11653 소인수분해 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 내 풀이 방식 주어진 N값을 소수로 나누었을 때 구할 수 있는 약수를, 다시 소수로 나누는 과정을 반복하면 구할 수 있을 것이라 생각했지만, 코드구현에 실패했다. 다른 풀이 코드 리뷰 - while문 활용 (스터디원) n = int(input()) d = 2 while n != 1: if n%d == 0: n = n // d print(d) else: d+=1 생각보다 간단하고 깔끔하게 코드 구현을 잘 했다. 재귀적 풀이가 어려울 때 while문과 조건을 이용해서 시도해볼 수..
[백준 파이썬] #2217 로프
Silver V # 2217 로프 풀이 N = int(input()) weights = sorted([int(input()) for i in range(N)]) w = [] for i, j in enumerate(weights): result = (len(weights)-i) * j w.append(result) print(max(w)) 규칙성을 찾으면 어렵지 않은 문제였으나, 코드 구현에 어려움이 있었다. 알게된 점 enumerate 함수를 처음 직접 적용해보았다. for 루프가 돌아간 횟수를 인덱스처럼 사용할 수 있어서 풀이에 도움이 되었다.
[백준 파이썬] #1302 베스트셀러
Siver IV # 1302 베스트 셀러 https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 풀이 N = int(input()) bs = [input() for i in range(N)] sbs = list(sorted(bs)) cnt=[] for i in sbs: cnt.append(bs.count(i)) print(sbs[cnt.index(max(cnt))]) 배운 내용 dictionary 자료형을 이용할 수 있다 딕셔너리는 key, v..
[백준 파이썬] #16435 스네이크 버드
Siver V # 16435 스네이크 버드 https://www.acmicpc.net/problem/16435 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 풀이 N, L = list(map(int, input().split())) # 과일개수 N, 스네이크 버드 초기 길이 L h = list(map(int, input().split())) # 과일 높이 h = sorted(h) # h.sort()으로 변환하면 채점에서 틀렸다고 함 for i in range..
[백준 파이썬] #7785 회사에 있는 사람
Silver V # 7785 회사에 있는 사람 https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 풀이 #시간 초과 발생 PyPy3로 채점해서 정답 n = int(input()) com = [] for i in range(n): a, b = input().split() if b == 'enter': com.append(a) elif b == 'leave': com.remove(a) com = sorted(co..
[백준 파이썬] #10867 중복 빼고 정렬하기
Silver V # 10867 중복 빼고 정렬하기 https://www.acmicpc.net/problem/10867 10867번: 중복 빼고 정렬하기 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. www.acmicpc.net 큰 어려움 없이 풀 수 있었다 풀이 N = int(input()) num = list(map(int, input().split())) s_num = sorted(set(num)) for i in s_num: print(i, end = ' ') 출력과정에서 조금 고민했었다. 리스트 안의 요소를 어떻게 해야 깔끔하게 출력할 수 있을까 싶었는데, 그냥 for문을 돌리면 되는 거였다...