2024년 4월 3일 알고리즘 문제풀이 문제 소수 경로 난이도 실버 2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import sys k,n = map(int,sys.stdin.readline().split()) lan = [] for _ in range(k): lan.append(int(sys.stdin.readline())) low = 0 high = 2**31-1 while low <= high: mid = (low+high)//2 cnt = 0 for thing in lan: cnt += thing//mid if cnt >= n: low = mid+1 else: high = mid-1 print((high+low)//2) 생각보다 평범한 이진탐색문제였다. ...
2024년 4월 3일 알고리즘 문제풀이 문제 소수 경로 난이도 골드 4 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 import sys from heapq import heappop, heappush def check(k:int): if not k%2: return False for i in range(3,int(k**(0.5))+1): if not k%i: return False else: return True prime_numbs = [ False for _ in range(10000)] for i in range(1000,10000): if check(i): prime_numbs[i] = True def change_num(arr: list): result = [] for i in range(10): for j in range(4): tmp = arr.copy() tmp[j] = str(i) if int("".join(tmp)) > 999 and prime_numbs[int("".join(tmp))] and tmp != arr: result.append(tmp) return result t = int(sys.stdin.readline()) for _ in range(t): answer = 'Impossible' a,b = map(int,sys.stdin.readline().split()) visited = [False for _ in range(10000)] visited[a] = True q = [] a_arr = list(str(a)) b_arr = list(str(b)) heappush(q,[0,a_arr]) while q: cnt, now = heappop(q) if now == b_arr: answer = cnt break change_arr = change_num(now) for num in change_arr: if not visited[int("".join(num))]: visited[int("".join(num))] = True heappush(q,[cnt+1, num]) print(answer) 매 번 소수 여부를 체크하지 않고, 1000부터 9999까지 소수 여부를 표시한 배열을 만들었다. change_num() 함수는 특정 수에서 1자리만 바꾼 수이다. 배열에 넣을 때, 몇 번 바뀌었는지를 함께 넣고 최소힙을 이용하여 최대한 적게 바꿀때를 찾을 수 있도록 했다. ...
2024년 4월 2일 알고리즘 문제풀이 문제 가장 큰 수 난이도 Lv.2 코드 1차 실패 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def check_first(s): if len(str(s)) == 1: return int(s) else: return int(str(s)[0]) def solution(numbers): n = len(numbers) answer = '' arr = [] for _ in range(10): arr.append([]) for num in numbers: tmp = check_first(num) arr[num].append(num) return answer 두 수 중 먼저 와야할 수는 가장 앞에 있는 수가 큰 수면 되겠다 싶었다. 그래서 모든 수를 맨 앞이 1인 수, 2인 수, … , 9인 수 까지 분류하려했다. 생각해보니 그 다음은? 그 안을 또 나누기엔 컴퓨터가 터지지 않을까? 수 두 개를 비교할 때, 길이는 중요하지 않다는 걸 파악했다. 그리고 가장 앞에 있는 수가 중요하다는 것도 캐치했다. 두번 째로 오는 수는 앞자리 수와의 비교가 중요하다. 예를 들어, 30,31,32 는 두 번째 자리가 0,1,2 로 모두 3보다 작으므로 그냥 ‘3’보다 늦게 올 애들이다. 반면 34,35 등은 3보다 더 앞에 나타나야 한다. 비교를 쉽게 하기 위해 앞자리를 복붙하면 되겠다고 생각했는데, 1000 이하이니 싹 다 3자리 짜리로 만들어주면 되겠다. ...
2024년 4월 1일 알고리즘 문제풀이 문제 n진수 게임 난이도 Lv.2 코드 1차 실패 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 def find_limit(a,b): # a를 b진법으로 바꿀 때 자릿수를 반환 idx = 0 while b**idx < a: idx += 1 return idx def change(k,m): # k를 m진법으로 변환하는 함수 max_val = find_limit(k,m) arr = [0 for _ in range(max_val)] for i in range(max_val): arr[i] = k//(m**(max_val-(i+1))) k -= arr[i]*(m**(max_val-(i+1))) return str(''.join(arr)) def solution(n, t, m, p): answer = '' arr = [] numbers = [str(i) for i in range(10)] + ['A', 'B', 'C', 'D', 'E', 'F'] n_numbers = numbers[:n] for i in range(m*t): num = change(i,n) print(num) return answer m명이 t개를 불러야 하므로 m*t까지 숫자를 구한다음, 모두 n진법으로 바꾸려 했다. 문자열로 조각내 배열에 담은다음 찾으면 될 듯 했다. 진법 변환을 못하겠다.. ...
2024년 3월 28일 알고리즘 문제풀이 문제 다트 게임 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 def solution(dartResult): idx = 0 scores = [] # while문 1회 마다 1차례의 결과를 체크 while idx < len(dartResult): # 점수 부분을 담을 변수 tmp = 0 # 문자열이 숫자 부분이라면 점수를 의미 if dartResult[idx].isdigit(): # 그 다음 문자도 숫자라면 10이라는 의미이므로 2글자 모두 담는다. if dartResult[idx+1].isdigit(): tmp = int(dartResult[idx]+dartResult[idx+1]) # 다다음 글자를 보기위해 index 증가 idx += 2 # 아니면 1자리 숫자이므로 1글자만 담는다. else: tmp = int(dartResult[idx]) # 다음 글자를 보기위해 index 증가 idx += 1 # 알파벳이 나오면 보너스를 의미 if dartResult[idx].isalpha(): if dartResult[idx] == 'D': tmp = tmp**2 elif dartResult[idx] == 'T': tmp = tmp**3 # 다음 글자를 살피기 위해 idx 증가 idx += 1 scores.append(tmp) # 옵션은 없을수도 있음 # 마지막 차례에 옵션이 없어서 더이상 글자가 없을 경우를 고려하여 예외처리가 필요 if idx >= len(dartResult): break # 옵션이 있다면 if dartResult[idx] in ['*','#']: # 스타상의 경우 가장 최근 점수의 2배 증가 if dartResult[idx] == '*': scores[-1] = 2*scores[-1] # 첫번째 다트 기회에 스타상이 나올 경우에는 그 이전 점수는 증가시키지 않음 # 따라서 그 이전 점수가 존재할때만 그것도 2배 증가 if len(scores) > 1: scores[-2] = 2*scores[-2] # 아차상은 그 전점수의 부호를 변경 else: if scores: scores[-1] = -1*scores[-1] idx += 1 return sum(scores)
2024년 3월 28일 알고리즘 문제풀이 문제 서울에서 김서방 찾기 난이도 Lv.1 코드 1 2 3 4 def solution(seoul): answer = '' answer = str(seoul.index('Kim')) return f"김서방은 {answer}에 있다"
2024년 3월 26일 알고리즘 문제풀이 문제 압축 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 def solution(msg): answer = [] alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' arr = dict() for i in range(len(alphabet)): arr[alphabet[i]] = i+1 # 다음 추가될 색인 번호는 마지막보다 1 큰 수 last_num = len(alphabet)+1 # idx까지 볼때 idx-1 까지만 포함되므로 1로 설정 idx = 1 n = len(msg) while idx <= n: # 이미 있다면 다음이 더 긴지 확인하기 위해 idx만 1 증가 if msg[:idx] in arr: idx += 1 continue else: # 사전에 없다면, 길이가 1 작을 때가 가장 긴 단어이므로(2단계) 그 번호를 출력 answer.append(arr[msg[:idx-1]]) # 없는 단어와 색인 번호를 추가 arr[msg[:idx]] = last_num # 다음 추가될 색인 번호 1 증가 last_num += 1 # 찾아낸 가장 긴 단어는 삭제 msg = msg[idx-1:] # 인덱스 오류를 방지하기 위해 매 반복마다 길이 체크 n = len(msg) # 인덱스 초기화 idx = 1 # 마지막 반복 때 사전에 있는 단어로 끝났다면 추가되지 않는 단어가 생기므로 추가 # KAKAO에서 마지막 O는 별도로 추가해야함 if msg: answer.append(arr[msg]) return answer 매 번 느끼는 거지만, 문제가 길 때(특히 카카오)는 차근차근 시키는대로 하는게 정답이다. ...
2024년 3월 25일 알고리즘 문제풀이 문제 대충 만든 자판 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 def solution(keymap, targets): answer = [] arr = dict() idx = 0 # 각 글자를 입력하기 위한 버튼 누르는 횟수의 최솟값을 저장하는 배열 arr을 만드는 과정 # 각 버튼의 0번 index 부터 하나씩 참조 while True: # 모든 키의 입력 범위를 넘어갔는지 확인하기 위한 플래그 flag = False # 모든 버튼 순회 for button in keymap: # 예를 들어, 버튼을 5번 누를 수 있는데 idx가 6이라면 그 버튼은 더이상 조사할 필요가 없으므로 넘어감 if idx >= len(button): continue # 어떤 버튼을 참조했음을 플래그에 표시. 이 과정이 없으면 keymap중 가장 긴 버튼의 길이를 구하느 과정이 따로 필요 flag = True # idx번 눌렀을 때 해당 버튼에서 입력되는 글자 letter = button[idx] # 지금 입력되는 글자가, 아직 입력된적 없는 글자라면 배열에 추가 if letter not in arr: arr[letter] = idx+1 # 이미 입력된적 있다면, idx를 작은 값으로 바꿔줌. 각 글자를 누르는 최소 방법만 알면 되기 때문 # 0번 인덱스는 1번 눌러야 하므로 idx+1을 저장 else: arr[letter] = min(arr[letter],idx+1) # 아무 버튼도 탐색하지 않았다면 무한루프 종료 if not flag: break idx += 1 for target in targets: cnt = 0 # 타겟을 하나씩 탐색하며 글자를 확인 for i in range(len(target)): # 만약 글자를 입력할 방법이 있다면 해당 키의 값을 추가 if target[i] in arr: cnt += arr[target[i]] # 글자를 입력할 방법이 없다면 -1로 지정하고 종료 else: cnt = -1 break answer.append(cnt) return answer
2024년 3월 18일 알고리즘 문제풀이 문제 다리를 지나는 트럭 난이도 Lv.2 코드 1차 42.9점 / 100점 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 from collections import deque def solution(bridge_length, weight, truck_weights): answer = 0 # 다리를 표현하기 위한 덱 in_bridge = deque() # 다리의 길이와 트럭의 위치를 표현하기 위해 트럭이 없는 곳은 0인 원소로 채운다. for _ in range(bridge_length): in_bridge.append(0) for truck in truck_weights: # 현재 다리에 지금 주목하는 트럭이 올라가면 무게 제한을 초과할 경우 # 가장 끝에 있는 원소를 빼낸다. 트럭일 수도, 빈 값(0)일 수도 있다. # 0번 인덱스가 빠지고 하나가 추가되기 때문에 모든 원소들의 index는 1씩 줄어든다. # 따라서 다리 위의 모든 트럭이 1칸 움직이는 것을 의미한다. while sum(in_bridge)+truck > weight: outgoing_truck = in_bridge.popleft() in_bridge.append(0) answer += 1 # 만약 실제로 트럭이 빠졌다면, 이와 동시에 새로운 트럭이 올라올 수 있다. # 새로운 트럭이 올라오는 행위는 동시에 일어나므로 시간이 흐르지 않은것으로 치기 위해 뺸다. if outgoing_truck: answer -= 1 # 다리에 새로운 트럭이 올라올 수 있다면 올려준다. if sum(in_bridge)+truck <= weight: # 잘못된 부분: 위에서 동시에 올라온다고 해놓고 여기서 또 하나의 트럭을 빼주었다. 여기서 오답이 발생 in_bridge.popleft() in_bridge.append(truck) answer += 1 # 모든 트럭을 다리 위에 올렸더라도, 도착까지 계산해야 한다. # 가장 도착지에서 먼 트럭이 도착지까지 걸리는 시간을 더해준다. for i in range(len(in_bridge)-1,-1,-1): if in_bridge[i]: answer += (i+1) break return answer 덱을 이용해야겠다는 생각은 보자마자 들었다. 배열에서 한 쪽으론 트럭을 빼내야 하고 한 쪽으론 집어 넣어야 해서 입구와 출구가 정해져있는 덱이 유리하겠다고 생각했다. 덱의 길이를 항상 bridge_length 만큼으로 유지하기 위해 항상 빈 곳은 0의 값을 채워 넣어 주었다. 다리의 길이가 1이 아니기 때문에, 다리 위에서 트럭이 움직일 떄도 시간이 흐르기 때문이다. 시간이 흐를 때마다 0번 index 값을 빼주고(popleft), 맨 뒤에 새로운 값을 삽입하면(append) 다리 위에 있는 모든 트럭의 index는 1씩 감소하게 된다. 따라서 1칸 씩 전진한 셈이 된다. 현재 트럭의 위치를 index로 설정하기 위해선 트럭이 있지 않은 공간을 0으로 설정하는 것은 내가 생각해도 잘한 것 같다. 특히나, 이렇게 하면 다리 길이보다 더 많은 트럭이 올라올 일은 걱정하지 않아도 된다. ...
2024년 3월 18일 알고리즘 문제풀이 문제 캐시 난이도 Lv.2 코드 1차 80점 / 100점 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def solution(cacheSize, cities): answer = 0 if not cacheSize: answer = 5 * len(cities) return answer arr = [] for i in cities: city = i.lower() if len(arr) < cacheSize: answer += 5 arr.append(city) continue if city in arr: answer += 1 arr.remove(city) arr.append(city) continue else: answer += 5 arr.pop(0) arr.append(city) return answer 캐시에 여유공간이 있을 때는 우선적으로 채워주었다. 캐시가 가득 찼을 때, 가장 사용된지 오래된 캐시가 삭제되야 하므로 이에 대한 구별이 필요했다. 따라서 사용한 캐시는 배열에서 삭제후 다시 추가하였다. 이렇게 되면 캐시 배열의 0번 index의 값이 1순위로 삭제될 캐시가 된다. 테스트 케이스가 몇개 있어 실패하였는데, 생각해보니 캐시가 가득 차지 않았을 때도 이미 캐시에 존재하여 추가할 필요가 없는 경우가 있었다. 예를 들어, 첫 번째 두 번쨰 도시가 같다면 내 로직에선 둘 다 캐시에 들어 가버린다. 이 경우를 위해 조건을 추가했다. ...