Study

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으로 설정하는 것은 내가 생각해도 잘한 것 같다. 특히나, 이렇게 하면 다리 길이보다 더 많은 트럭이 올라올 일은 걱정하지 않아도 된다. ...

Google Search Console 색인 등록 문제 해결법 상황 2023년 5월 27일에 지금의 깃허브 블로그를 처음 시작했다. 어려운 것, 귀찮은 것, 잘 모르는 것 투성이지만 그만큼 배울게 많아질 것이라 생각하며 시작했다. 24년 3월 18일을 기준으로 447개의 게시글을 작성했다! 자주 쓰는 만큼 고퀄리티는 아닌지라 누군가에게 보여주기 민망하지만, 그래도 한명이라도 나의 글로 도움을 받길 바라고 있다. 나 또한 다른 사람들의 글을 보며 그랬으니까. Google search console에 나의 블로그를 등록하고 sitemap.yml 과 robot.txt, feed.xml도 설정해주었다. 방법에 관한 글은 구글에 넘쳐난다. ...