[Algorithm] BOJ Class 2*
1일 1알고리즘 아침 문제 풀이
Jun 22, 2023
1일 1알고리즘 문제 풀기
- 시간 : 자유 (오전에 문제 업로드)
- 계획 : Class2*문제 2023-06-01 ~ 21 (이후에 Class3*문제 도전)
Problem
Date | No | Problem | Level | Time | Redo |
2023-06-01 | 01 | Bronze | 8 min | ㅤ | |
2023-06-02 | 02 | Bronze | 12 min | ㅤ | |
2023-06-03 | 03 | Bronze | 3 min | ㅤ | |
2023-06-04 | 04 | Bronze | 9 min | ㅤ | |
2023-06-05 | 05 | Bronze | 12 min | ㅤ | |
2023-06-06 | 06 | Bronze | 9 min | ㅤ | |
2023-06-07 | 07 | Bronze | 6 min | ㅤ | |
2023-06-08 | 08 | Bronze | 15 min | ㅤ | |
2023-06-09 | 09 | Silver | 6 min | ㅤ | |
2023-06-10 | 10 | Silver | 60 min | ✓ | |
2023-06-11 | 11 | Silver | 30 min | ✓ | |
2023-06-12 | 12 | Silver | 14 min | ㅤ | |
2023-06-13 | 13 | Silver | 15 min | ㅤ | |
2023-06-14 | 14 | Silver | 7 min | ㅤ | |
2023-06-15 | 15 | Silver | 23 min | ㅤ | |
2023-06-16 | 16 | Silver | 9 min | ㅤ | |
2023-06-17 | 17 | Silver | ㅤ | ㅤ | |
2023-06-18 | 18 | Silver | 6 min | ㅤ | |
2023-06-19 | 19 | Silver | ㅤ | ㅤ | |
2023-06-20 | 20 | Silver | 7 min | ㅤ | |
2023-06-21 | 21 | Silver | 13 min | ㅤ |
Solution
01. 직각삼각형
Solution. if문 3항 연산자 사용하기
while True : a, b, c = sorted(list(map(int, input().split()))) # 종료 조건 if (a, b, c) == (0, 0, 0): break # 직각삼각형 조건 cond1 = (a>0) and (b>0) and (c>0) cond2 = (a+b > c) cond3 = (a**2 + b**2 == c**2) print('right' if cond1 and cond2 and cond3 else 'wrong')
첫 스타트 (사실 class3로 바로 갔다가 첫 문제부터 고생하고 여기서 시작하기로 했다.)
문제 리스트를 보니까 여기는 중고등학교 때 봤던 수학 서술형 문제 느낌이 많아서 나름 재밌다.
02. ACM 호텔
Solution. for _ in range()
# 입력횟수 T = int(input()) # H, W, guest를 받았을 때 호텔객실 배정 for _ in range(T): H, W, guest = list(map(int, input().split())) 층 = (guest % H) or H 호 = ((guest-1) // H) + 1 print(층*100 + 호)
백준에는
for _ in range(T): 로 시작하는 문제들이 많은 것 같다.호에서 헷갈려서 (guest-1)//H 로 고치는데 시간이 좀 걸렸다.03. 평균
N = int(input()) nums = list(map(int, input().split()))[:N] print(sum(nums)/len(nums) * 100/max(nums))
너무 쉬워서 스터디에 올리기가 좀 그랬다. 빠르게 혼자 풀고 패스.
04. 이항계수 1
math.factorial 활용하기
from math import factorial N, K = list(map(int, input().split())) print(int(factorial(N) / factorial(K) / factorial(N-K)))
이것도 너무 쉬워서 혼자 풀고 패스.
05. 소수 찾기
Solution 1.
# 소수인지 판별하는 함수 def is_prime(n): if n<2 : return False for i in range(2, (n//2)+1): if n%i == 0: return False return True # 위의 함수를 적용해서 True인 경우만 카운트 N = int(input()) num_list = list(map(int, input().split()))[:N] print(sum([is_prime(num) for num in num_list]))
Solution2. all() 활용하기
def is_prime(n): return False if n<2 else all([n%i!=0 for i in range(2, (n//2)+1)]) # all() => True only if all of the () are True # any() => True if any of the () is True
함수명, 변수명을 잘 만드는게 이해하는데 도움이 되는 것 같다.
is_prime 처럼..다른 사람들 풀이 보니까 새로운 함수랑 활용법이 이해가 돼서 도움이 되는 것 같다.
06. 블랙잭
Solution1. for문을 3중으로 사용하기
N, M = list(map(int, input().split())) deck = list(map(int, input().split())) # card_1, card_2, card_3를 순서대로 뽑고 => 합을 result에 append result = [] for i in range(N): for j in range(N-1): for k in range(N-2): temp = deck.copy() card_1 = temp.pop(i) card_2 = temp.pop(j) card_3 = temp.pop(k) result.append(card_1 + card_2 + card_3) # 저장된 합 중 M에 가장 가까운 수를 출력 print(max([n for n in result if n<=M]))
Solution2.
itertools.combinations 활용하기from itertools import combinations N, M = list(map(int, input().split())) deck = list(map(int, input().split())) # nC3 으로 3장씩 묶음 => 합이 M에 가장 가까운 경우 출력 cards = list(combinations(deck, 3)) print(max([sum(c) for c in cards if sum(c)<=M]))
라이브러리를 쓰니까 너무 쉬워진다. 생각흐름대로 코드를 쓰는 것도,
collections.Counter()처럼 유용한 라이브러리 정리도 둘 다 필요해 보인다.07. 팰린드롬수
문자열 슬라이싱으로 역순 만들기
while True: n = int(input()) if n==0: break print('yes' if n == int(str(n)[::-1]) else 'no')
추가 문제) 앞에 0이 들어가는 경우 카운트하기
10 은 팰린드롬수가 아닙니다. 하지만 특별히 앞에 무의미한 0이 올 수 있다고 가정하면 010이 되어 팰린드롬수로 취급할 수도 있습니다. 이렇게 0이 추가되면 가능한 경우까지 모두 포함하여 팰린드롬수 여부를 출력하도록 하세요. ex. 12100 => 0012100 (yes) while True: n = str(input()) if n=='0': break # 뒤에 있은 0만큼 앞에 붙여주기 cnt = 0 while n[-1]=='0': cnt += 1 n = n[:-1] n = '0'*cnt + n + '0'*cnt # 팰린드롬수 여부 출력 print('yes' if n == str(n)[::-1] else 'no')
08. 최대공약수와 최소공배수
Solution 1. 약수를 모두 구해서 계산하기 => 실패 : 답은 맞는데 BOJ에서는 런타임 에러 발생함.
def get_divisor(n): ''' 약수를 구하는 함수 ''' divisor = [] for i in range(1, n//2 +1): if n%i == 0: divisor.append(int(i)) divisor.append(int(n/i)) return set(divisor) # 입력 num1, num2 = sorted(list(map(int, input().split()))) # 최대공약수, 최소공배수 구하기 최대공약수 = max(get_divisor(num1) & get_divisor(num2)) 최소공배수 = int(num1 * num2 / 최대공약수) print(최대공약수) print(최소공배수)
Solution 2. 공약수 후보 중 큰 숫자부터 확인해서 최대공약수를 바로 구하기 => 성공
def get_gcd(a, b): ''' 최대공약수를 구하는 함수 ''' for i in range(min(a,b), 0, -1): if (a%i==0) and (b%i==0): return i # 입력 num1, num2 = list(map(int, input().split())) # 최대공약수, 최소공배수 구하기 최대공약수 = get_gcd(num1, num2) 최소공배수 = int(num1 * num2 / 최대공약수) print(최대공약수) print(최소공배수)
Solution 3. math라이브러리 활용하기
import math # 입력 num1, num2 = list(map(int, input().split())) # 최대공약수, 최소공배수 구하기 최대공약수 = math.gcd(num1, num2) 최소공배수 = math.lcm(num1, num2) print(최대공약수) print(최소공배수)
Solution4. 유클리드 호제법 활용하기
유클리드 호제법
- 호제법: 두 수가 서로 상대방을 나누어 결국 원하는 수를 얻는 알고리즘을 의미함.
- 유클리드 호제법 : 2개의 자연수의 최대공약수를 구하는 호제법(알고리즘).
두 정수 a, b에서 r = a % b 이면 => gcd(a, b) = gcd(b, r) r' = b % r 이면 => gcd(a, b) = gcd(b, r) = gcd(r, r') = ... 반복문을 만들어서 마지막이 (?, 0)이 되면 나누어 떨어지니까 ?가 최대공약수가 된다
# 입력 num1, num2 = sorted(list(map(int, input().split()))) # 호제법 a, b = num1, num2 while (b!=0): a, b = b, (a%b) 최대공약수 = a 최소공배수 = int(num1 * num2 / a) print(최대공약수) print(최소공배수)
09. 단어정렬
리스트 정렬 조건 key 활용하기
# 입력 N = int(input()) words = [] for _ in range(N): words.append(input()) # 중복제거, 정렬(길이, 알파벳) words = sorted(list(set(words)), key=lambda x: (len(x), x)) # 출력 for w in words: print(w)
우선순위가 떨어지는 조건으로 먼저 정렬한 후에 우선순위가 높은 조건으로 다시 정렬해줘도 같은 결과가 나오는 것 같다. (from 희권, 희묵)
my_list = sorted(my_list, key=2번쨰 조건) my_list = sorted(my_list, key=1번쨰 조건)
10. 체스판 다시 칠하기
IDEA
- 좌측 상단을 ‘기준점’이라고 정한다.
- 주어진 판 크기가 (10, 10)일 때, ‘기준점’이 가능한 곳은 (0,0), (1,1), (1,0), (0,1), (2,0), (2,1), (1,2), (2,2) ⇒
(range(기존x-8+1), range(기존y-8+1))
- ‘기준점’을 기준으로 x축으로 i, y축으로 j만큼 움직일 때, i+j가 홀수이면 다른 색, i+j가 짝수이면 같은 색인지 확인한다. 만약 아닐 경우, count에 담아서 그 수를 센다.
- 후보1 :
min(count)= ‘기준점’ 색을 가만히 두고 다른 칸들의 색을 바꿀 경우 후보2 :(8*8 - max(count))= ‘기준점’ 색부터 바꾸는게 오히려 효율적일 경우 ⇒min(min(count), (8*8-max(count)))
Solution 1.
# 입력 > 원래 체스판 만들기 M, N = map(int, input().split()) board = [] for _ in range(M): board.append(list(input())) # 기준점 정하기 count_list = [] for a in range((M-8)+1): for b in range((N-8)+1): # 기준 색 정하기 color = board[a][b] count = 0 # (a, b)에서 떨어진 칸수를 기준으로 > color==색, color!=색 카운트 for i in range(8): for j in range(8): count += int(((i+j)%2==1) and (board[a+i][b+j] == color)) count += int(((i+j)%2==0) and (board[a+i][b+j] != color)) count_list.append(count) # 기준색을 바꿔버리는 경우도 고려해서 최소값 찾기 > 출력 print(min(min(count_list), 64-max(count_list)))
Solution 2. Pandas 활용하기
익숙한 Pandas.DataFrame 형태로 만들어서 loc 값을 인덱싱 해봤는데 이 문제에서는 라이브러리 사용을 막아놔서 오류가 발생한다. ------------------------------------------------------ import pandas as pd # 입력 > 원래 체스판 만들기 M, N = map(int, input().split()) board = pd.DataFrame(index=range(M), columns=[i for i in range(N)]) for i in range(M): board.loc[i] = list(input()) # 기준점 정하기 count_list = [] for a in range((M-8)+1): for b in range((N-8)+1): # 기준 색 정하기 color = board.loc[a, b] count = 0 # (a, b)에서 떨어진 칸수를 기준으로 > color==색, color!=색 카운트 for i in range(8): for j in range(8): count += int(((i+j)%2==1) and (board.loc[a+i, b+j] == color)) count += int(((i+j)%2==0) and (board.loc[a+i, b+j] != color)) count_list.append(count) # 기준색을 바꿔버리는 경우도 고려해서 최소값 찾기 > 출력 print(min(min(count_list), 64-max(count_list)))
Bronze는 아주쉬움, Silver는 쉬움 정도로 생각했는데 생각보다 어렵다..
IDEA에서 2번까지 생각하는데 시간이 오래 걸렸다.
11. 수 찾기
Solution 1. list에서 in을 사용하기
N = int(input()) nums = list(map(int, input().split()))[:N] M = int(input()) targets = list(map(int, input().split()))[:M] for target in targets: print(int(target in nums))
Solution 2. 이진탐색 이용하기 (feat. ChatGPT) ⇒ 시간초과!
처음에는 left, right를 양 끝으로 잡아서 중간값(mid)과 target의 대소를 비교한다. target이 mid보다 크거나 작으면 반대쪽 절반을 잘라서 버리고 left, right, mid를 그 안에서 다시 설정해서 비교를 반복한다.
def binary_search(nums, target): """ 이진탐색으로 target값이 nums에 있으면 1, 없으면 0을 리턴하는 함수 """ # 중복제거 후 정렬 nums = sorted(list(set(nums))) # 이진탐색을 위한 인덱스 left = 0 right = len(nums) - 1 while left < right : mid = (left + right)//2 if target == nums[mid]: return(1) elif target > nums[mid]: left = mid+1 else : right = mid-1 return(0) N = int(input()) nums = list(map(int, input().split())) M = int(input()) targets = list(map(int, input().split()))[:M] for target in targets: print(binary_search(nums, target))
Solution 3. set에서 in 사용하기
위의 두 방법은 시간초과 오류가 발생했다.
⇒ 시간 복잡도로 봤을 때, list의 in은
O(n), 이진탐색은 O(log n), set과 dict는 O(1)이 된다.⇒ set의 시간복잡도가
O(1)이므로 n이 커져도 속도에 차이가 없게 되고 가장 빠른 방법(해시탐색)이다.N = int(input()) nums = set(map(int, input().split())) M = int(input()) targets = list(map(int, input().split())) for target in targets: print(int(target in nums))
12. 카드2
Solution 1. 기본 풀이
시간초과로 실패
=> 카드를 한장 버리고 자리를 이동하는 과정(리스트를 슬라이딩, 다시 합쳐주는 처리)에서 시간이 초과되는 것 같다.
# 1~N까지의 숫자카드 => range(1, N+1) cards = list(range(1, int(input())+1)) # # 제일 위에 카드를 버리고, 그 다음 카드를 제일 밑으로 옮김 > 반복 while len(cards) > 1: cards.pop(0) cards = cards[1:] + [cards[0]] # 마지막 남은 카드를 출력 print(cards[0])
Solution 2. collections.deque, rotate() 활용
그 다음으로 생각난 방법
cards[0]을 cards[-1]로 옮기는 연산을 deque.rotate()로 처리한다.
# popleft() => pop(idx번호)가 deque에서는 안되는 것 같다.
# rotate(-1) => cards[0]을 cards[-1] 자리로 이동
import collections cards = list(range(1, int(input())+1)) cards = collections.deque(cards) # 제일 위의 카드를 버리고, 그 다음 카드를 제일 밑으로 옮김 (popleft, rotate) > 반복 while len(cards) > 1: cards.popleft() cards.rotate(-1) # 마지막 남은 카드 출력 print(cards[0])
List, String, Deque의 시간복잡도 (by ChatGPT)
1) List
- 맨 첫 번째 원소를 맨 마지막으로 이동: 리스트의 pop(0) 연산으로 첫 번째 원소를 가져온 후, append() 연산으로 맨 뒤에 추가합니다. 이러한 이동 작업은 리스트의 길이가 N일 때 O(N)의 시간이 소요됩니다.
- 추가 및 제거 작업: 리스트의 append() 및 pop() 연산은 일반적으로 상수 시간 O(1)이 소요됩니다. 하지만 리스트의 중간에 있는 원소를 추가하거나 제거하는 경우, 해당 위치 이후의 원소들을 한 칸씩 이동해야 하므로 최악의 경우에는 O(N)의 시간이 소요될 수 있습니다.
- 따라서, 리스트를 사용할 경우 맨 첫 번째 원소를 맨 마지막으로 이동시키는 작업은 O(N)의 시간이 소요되며, 추가 및 제거 작업은 일반적으로 O(1)이지만 중간에 있는 원소의 추가 및 제거는 최악의 경우 O(N)의 시간이 소요됩니다.
2) String:
- 문자열은 불변 (Immutable) 자료형이므로 맨 첫 번째 원소를 맨 마지막으로 이동시키는 작업은 직접적으로 지원되지 않습니다. 문자열을 수정하려면 새로운 문자열을 생성해야 합니다. 이러한 작업은 맨 첫 번째 문자를 제외한 나머지 문자를 새로운 문자열로 복사하는 과정이 필요하므로 O(N)의 시간이 소요됩니다.
- 추가 및 제거 작업: 문자열은 불변 자료형이기 때문에 추가 및 제거 작업이 지원되지 않습니다. 문자열을 수정하려면 새로운 문자열을 생성해야 하므로 추가 및 제거 작업은 O(N)의 시간이 소요됩니다.
3) Deque:
- 맨 첫 번째 원소를 맨 마지막으로 이동: 덱의 popleft() 연산으로 첫 번째 원소를 제거한 후, append() 연산으로 맨 뒤에 추가합니다. 덱은 이러한 작업을 O(1)의 시간에 수행할 수 있습니다.
- 추가 및 제거 작업: 덱은 양쪽 양 끝에서의 추가 및 제거 작업을 O(1)의 시간에 수행할 수 있습니다.
=> 정리
- 속도 : Deque > List > String (문제에서 정해준 '맨 첫번쨰를 맨 마지막으로 보낸다' 라는 프로세스를 구현할 때 기준)
- Deque는 popleft()에 O(1), rotate도 이미 구현된 기능으로 1번만에 O(1)로 됨.
- List는 pop()으로 맨 앞을 빼는데 O(1), 슬라이싱하는 과정에서 최대 O(N)까지 걸릴 수 있음.
- String은 더하거나 빼는게 안돼서 새로 복사하는 개념으로 봐야 함. 맨 앞을 뺴는데 항상 O(N), 뒤에 추가하는데 O(N)이 소요됨.
N을 하나씩 높여가면서 마지막 출력되는 카드의 규칙을 찾아보면,
2의 배승이 나올때까지 2씩 증가해서 나온다.
- N = 일 때, ⇒ 이 그대로 출력된다.
- N = 으로 표현할 수 없을 때, ⇒ 이고, N이 1 증가할 떄마다 2씩 커진다.
N:2 → 2 N:3 → 2 N:5 → 2 N:9 → 2
N:4 → 4 N:6 → 4 N:10 → 4
N:7 → 6 N:11 → 6
N:8 → 8 N:12 → 8
…
N:15 → 14
N:16 → 16
import math N = int(input()) log2_N = math.log2(N) print(N if log2_N==int(log2_N) else 2*(N-(2**int(log2_N))))
반복문을 수행하지 않고 바로 N에 따라서 결과를 판별해서 알려주게 만든 코드여서 그런지 속도가 deque를 활용한 코드보다도 훨씬 빨랐다.
이 문제에서는 이럴 유형에서 deque의 rotate를 사용하면 된다는 것을 본 적이 있어서 사용했지만, 생소한 형태가 나왔을 때는 이렇게 규칙을 찾아보는 것도 좋아 보인다. 정석은 아니지만 창의적인 느낌.
13. 수 정렬하기 2
Solution
sys.stdin.readline()이 문제에서는 최대 입력과 출력을 100만개까지 해야 한다. 이렇게 대량으로 입출력을 받을 때
sys.stdin .readline()을 사용하면 input()보다 효율적으로 입력을 처리할 수 있다. ⇒ 처리속도가 빨라진다.import sys input = sys.stdin.readline N = int(input()) nums = [] for _ in range(N): nums.append(int(input())) for i in sorted(nums): print(i)
14. 괄호
N = int(input()) for _ in range(N): s = input() # ()가 없을 때까지 제거 반복 while '()' in s: s = s.replace('()', '') # 모두 없어졌으면 YES, ')', ')((' 처럼 뭔가가 남으면 NO print('YES' if s=='' else 'NO')
최근 문제들이 너무 어려워서 알고리즘 개념부터 보고 다시 돌아와야 하나 고민했는데, 그렇게 도망갈까봐 보너스로 준 문제 같다. 희망고문 문제.
15. 나이순 정렬
Solution
N이 최대 100,000까지 가능하다고 되어있다. 마찬가지로 출력도 100,000개가 될 수 있다.
import sys input = sys.stdin.readline print = sys.stdout.write N = int(input()) people = [] for i in range(N): age, name = input().split() people.append([age, name, i]) people = sorted(people, key=lambda x: (int(x[0]), x[2])) for p in people: print(p[0] + ' ' + p[1] + '\')
sys.stdin.readline : sys.stdout.write : 16. 숫자 카드 2
Solution
from collections import Counter import sys input = sys.stdin.readline print = sys.stdout.write _ = input() N = Counter(input().split())) _ = input() M = input().split()) print(' '.join([str(N[n]) for n in M]))
list.count vs collections.Counterlist.count(): list는 선형으로 순회하면서 요소를 비교하여 개수를 세는 방식이다.
collection.Counter(): Counter는 객체요소를 key, 개수를 value로 저장한다.
⇒ 데이터셋의 크기가 커지면 Counter가 유리해진다.
17. 스택
18. 큐
19. 덱
20. 좌표 정렬하기
Solution
import sys input = sys.stdin.readline coordinates = [] for _ in range(int(input())): coordinates.append(tuple(map(int, input().split()))) for c in sorted(coordinates, key=lambda x: (x[0], x[1])): print(f'{c[0]} {c[1]}')
앞에 나왔던 나이순, 단어 정렬 문제랑 비슷했다. 이제
sorted에서 key값이랑 lambda문이 눈에 익어서 편했다.21. 요세푸스 문제 0
Solution
원순열에서 k번째 마다 값을 제외하기를 반복하게 된다.
⇒ 이전에 빠졌던 값을 뛰어넘어야 해서 인덱스 값을 계산하기가 복잡하다.
⇒ deque를 이용해서 주어진 배열 자체를 돌려버리면 편해진다!
1. 주어진 arr를 rotate가 가능하도록 deque로 만들어준다. (고정해놓고 생각하면 어렵다) 2. 이번 턴에서 맨 앞(arr[0])에 있는 값을 제외시킨다. ⇒ len이 1 작은 새로운 arr가 만들어진다. 3. k칸만큼 arr를 돌린다. 4. 2~3을 len(arr)==0 이 될 때까지 반복한다.
from collections import deque N, k = map(int, input().split()) d = deque([i+1 for i in range(N)]) result = [] while d: d.rotate(-(k-1)) result.append(str(d.popleft())) print(f"<{', '.join(result)}>")
앞에 몇 문제가 똑같은 패턴이여서 약간 심심했는데 이 문제는 생각해봐야 해서 재밌었다.
이렇게 푸는거 맞겠지
Share article