2024년 1월 16일 알고리즘 문제풀이 문제 행렬의 곱셈 난이도 Lv. 2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 def solution(arr1, arr2): a1 = len(arr1) b1 = len(arr1[0]) a2 = len(arr2) b2 = len(arr2[0]) answer = [[0 for _ in range(b2)] for _ in range(a1)] for i in range(a1): for j in range(b2): tmp = 0 for x in range(b1): tmp += (arr1[i][x]*arr2[x][j]) answer[i][j] = tmp return answer 마지막 tmp를 구할때 b1이나 a2나 아무거나 사용해도 상관없다. 행렬의 곱셈이 가능하다는 건 두 수가 같다는 의미이기 때문이다. ...
2024년 1월 15일 알고리즘 문제풀이 문제 피보나치 수 난이도 Lv. 2 코드 1 2 3 4 5 6 7 8 def solution(n): dp = [0 for _ in range(n+1)] dp[1] = 1 if n<2: return dp[n] for i in range(2,n+1): dp[i] = (dp[i-1]+dp[i-2])%1234567 return dp[n]
2024년 1월 12일 알고리즘 문제풀이 문제 햄버거 만들기 난이도 Lv. 1 코드 배열을 순회하면서 순서대로 필요한 재료가 나오면 만들 수 있는 갯수를 하나 추가해주고, 해당 재료들을 제거해주었다. 이 방법은 틀렸는데, 재료가 연속해서 나와야 하기 떄문이다. 연속이라고 써놓지 좀… 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def solution(ingredient): answer = 0 arr = [1,2,3,1] while True: idx = 0 for x in range(len(ingredient)): if idx ==4: answer += 1 break if ingredient[x] == arr[idx]: idx += 1 ingredient[x] = 10 else: if idx == 4: answer += 1 else: return answer 그래서 하나씩 배열로 옮기면서, 최근 옮긴 4개로 햄버거를 만들 수 있다면 만들고 제거하도록 로직을 바꾸었다. ...
2024년 1월 11일 알고리즘 문제풀이 문제 자릿수 더하기 난이도 Lv. 1 코드 1 2 3 4 5 6 def solution(n): answer = 0 arr = list(str(n)) for x in arr: answer += int(x) return answer
2024년 1월 2일 알고리즘 문제풀이 문제 N-Queen 난이도 Lv.2 코드 그 어렵다고 소문난 N-Queen 문제. 정글 때 공부했던 문제였는데 그새 까먹었나보다. 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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 def solution(n): answer = 0 def check_width_row(p,q,arr): for i in range(n): if arr[i][q] == '0': arr[i][q] = False if arr[p][i] == '0': arr[p][i] = False def check_right_down(p,q,arr): i = 0 while p+i >= 0 and p+i < n and q+i >= 0 and q+i < n: if arr[p+i][q+i] == '0': arr[p+i][q+i] = False i += 1 def check_left_up(p,q,arr): i = 0 while p+i >= 0 and p+i < n and q+i >= 0 and q+i < n: if arr[p+i][q+i] == '0': arr[p+i][q+i] = False i -= 1 def check_right_up(p,q,arr): i = 0 while p-i >= 0 and p-i < n and q+i >= 0 and q+i < n: if arr[p-i][q+i] == '0': arr[p-i][q+i] = False i += 1 def check_left_down(p,q,arr): i = 0 while p+i >= 0 and p+i < n and q-i >= 0 and q-i < n: if arr[p+i][q-i] == '0': arr[p+i][q-i] = False i += 1 def check(p,q,arr): check_width_row(p,q,arr) check_right_down(p,q,arr) check_right_up(p,q,arr) check_left_up(p,q,arr) check_left_down(p,q,arr) arr[p][q] = True def search(x,arr): for i in range(n): if arr[x][i] == '0': check(x,i,arr) flag = True break else: flag = False return flag for i in range(n): w = [['0' for _ in range(n)] for _ in range(n)] w[0][i] = True check(0,i,w) k = 1 while k < n: tmp = search(k,w) if tmp: k += 1 else: break if k == n: print(w) answer += 1 return answer 보드판을 string ‘0’을 배치시켜 만들었다. 원래 숫자로 넣었는데 False일 떄와 0일때가 같이 취급되어서 따로 만들었다. 아무 선택되지 않은 좌표는 ‘0’, 공격당할 수 있기 때문에 놓을 수 없는 곳은 False, 퀸이 위치한 곳은 True로 설정하였다. 우선 임의의 좌표 (p,q)에 퀸을 놓았을 때 퀸이 공격할 수 있는 곳을 False 처리하는 코드를 작성했다. 임의의 좌표의 좌 우 대각선을 바꿔주는 함수를 각각 만들고 하나의 함수로 합쳤다(check). search는 특정 행에서 퀸을 놓을 수 있는 열을 찾아 존재하면 boolean값을 반환해주는 함수이다. ...
2024년 1월 1일 알고리즘 문제풀이 문제 최솟값 만들기 난이도 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 from heapq import heappop, heappush def solution(A,B): n = len(A) arr_A = [False for _ in range(n)] arr_B = [False for _ in range(n)] arr = [] def dfs(tmp,arr_A,arr_B): if arr and tmp > arr[0]: return if not arr_A.count(False) and not arr_B.count(False): if not arr or tmp < arr[0]: heappush(arr,tmp) for i in range(n): if arr_A[i]: continue for j in range(n): if arr_B[j]: continue arr_A[i] = True arr_B[j] = True dfs(tmp+(A[i]*B[j]),arr_A,arr_B) arr_A[i] = False arr_B[j] = False dfs(0,arr_A,arr_B) return arr[0] 처음엔 DFS로 시도했다. 여러 case가 규칙성 없이 나타날 수 있다고 생각했기 때문이다. 하지만 시간초과가 발생했다. 불필요한 탐색을 줄이기 위해, 값을 최소힙에 저장하도록 했다. DFS 과정 상 재귀 중에 이미 최소힙에 존재하는 최솟값을 넘어선 경우 탐색을 중단하도록 했다. 하지만 시간초과가 계속 발생했다. ...
2023년 12월 29일 알고리즘 문제풀이 문제 신규 아이디 추천 난이도 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 53 54 55 56 57 def solution(new_id): arr = ['1','2','3','4','5','6','7','8','9','0','-','_','.'] # 1단계 new_id = new_id.lower() # 2단계 tmp = [] for i in new_id: if i.islower() == True or i in arr: tmp.append(i) new_id = ''.join(tmp) # 3단계 if len(new_id) >1: tmp = [] for i in range(len(new_id)-1): if new_id[i] == '.' and new_id[i+1] == '.': continue tmp.append(new_id[i]) tmp.append(new_id[-1]) new_id = ''.join(tmp) # 4단계 if new_id: if new_id[0] == '.': if len(new_id) == 1: new_id = '' else: new_id = new_id[1:] # 4단계 if new_id: if new_id[-1] == '.': if len(new_id) == 1: new_id = '' else: new_id = new_id[:len(new_id)-1] # 5단계 if new_id == '': new_id = 'a' # 6단계 if len(new_id) >= 16: new_id = new_id[:15] # 6단계 if new_id[-1] == '.': new_id = new_id[:len(new_id)-1] # 7단계 if len(new_id) <= 2: while len(new_id) < 3: new_id = new_id + new_id[-1] return new_id 문제에 주어진 대로, 순차적으로 해결하면 큰 어려움은 없는 문제였다. 다만 중간중간, 문자열이 존재하지 않게 되는 상황이 발생할 수 있기 때문에 이를 따로 처리하는 로직이 필요하다. 시간 많이 잡아먹는 문제라 좋은 연습이 됐다. ...
2023년 12월 28일 알고리즘 문제풀이 문제 문자열 내 p와 y의 개수 난이도 Lv.1 코드 1 2 3 4 def solution(s): a = s.count('p') + s.count('P') b = s.count('y') + s.count('Y') return a == b 이 문제에선 p 와 y만 포함됐지만, 대문자나 소문자 자체를 어떻게 셀 지 궁금해져서 찾아보니 islower() 와 isupper() 를 사용하면 boolean 값으로 반환된다고 한다.
2023년 12월 26일 알고리즘 문제풀이 문제 줄 서는 방법 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import math def solution(n, k): answer = [] arr = list(range(1,n+1)) while n>0: tmp = math.factorial(n-1) a = k//tmp k = k%tmp if k: answer.append(arr[a]) arr.pop(a) else: answer.append(arr[a-1]) arr.pop(a-1) n -= 1 return answer 순열에 정의를 알면 접근방식 자체는 그리 어렵지 않지만, 코드로 구현하는 게 꽤나 까다로웠다. 순열은 결국 앞에서부터 올 수 있는 경우의 수를 정해주고 곱하는 방식이다. 4명이 줄을 서는 방법은 4! = 4 x 3 x 2 x 1이다. 왜 이렇게 나오냐면, 맨 앞에 올 수 있는 후보는 4개 이고, 그 다음은 3개, 2개, 1개 이기 때문이다. ...
2023년 12월 25일 알고리즘 문제풀이 문제 최댓값과 최솟값 난이도 Lv.2 코드 1 2 3 4 5 def solution(s): answer = '' arr = list(map(int,s.split())) answer = str(min(arr)) + ' ' + str(max(arr)) return answer 문자를 공백을 기준으로 쪼개 숫자형으로 변환하여 배열에 저장하였다. 최댓값과 최솟값만 다시 문자열로 변환한 쉬운 문제.