2023년 12월 12일 알고리즘 문제풀이 문제 멀리뛰기 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 def solution(n): answer = 0 dp = [0 for _ in range(n+1)] for i in range(1,n+1): if i == 1: dp[i] = 1 elif i == 2: dp[i] = 2 else: dp[i] = (dp[i-1] + dp[i-2])%1234567 answer = dp[n] return answer n번째 칸은 ...
2023년 12월 11일 알고리즘 문제풀이 문제 땅따먹기 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def solution(land): n = len(land) answer = 0 dp = [[0 for _ in range(4)] for _ in range(n)] dp[0] = land[0] def check(next_row,next_col): arr = [] for i in range(4): if i == next_col: continue arr.append(dp[next_row-1][i]) return max(arr) x = 1 while x < n: for i in range(4): dp[x][i] = check(x,i) + land[x][i] x += 1 answer = max(dp[-1]) return answer 각 행에는 4개의 열이 있다. 각 열에 올 수 있는 방법의 경우는 3가지이다. 예를 들어 2행 0열에 오는 방법은 2행 1열, 2행 2열, 2행 3열에서 오는 것이다. 이러한 원리를 바탕으로 DP를 설정했다. ...
2023년 12월 08일 알고리즘 문제풀이 문제 로또의 최고 순위와 최저 순위 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 def solution(lottos, win_nums): def translate(p): if p >=2: return 7-p else: return 6 answer = [] cnt = 0 unknown = 0 for num in lottos: if not num: unknown += 1 continue if num in win_nums: cnt += 1 continue max_match = cnt + unknown min_match = cnt answer.append(translate(max_match)) answer.append(translate(min_match)) return answer 확실한 것을 통해 최저 순위를 확정지을 수 있고 정해지지 않은 수가 모두 맞는다고 가정하면 최고 순위도 알 수 있다. ...
2023년 12월 07일 알고리즘 문제풀이 문제 문자열을 정수로 바꾸기 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 def solution(s): if s[0] == '-': answer = int(s[1:]) * -1 elif s[0] == '+': answer = int(s[1:]) else: answer = int(s) return answer
2023년 12월 05일 알고리즘 문제풀이 문제 다음 큰 숫자 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 def solution(n): num = str(bin(n)[2:]) cnt = num.count('1') while True: n += 1 tmp = str(bin(n)[2:]) if tmp.count('1') == cnt: break answer = n return answer 생각보다 쉬웠다. 기수법 관련해서는 문자열로 처리하는 경우가 꽤 많이 나오는 것 같다. ...
2023년 12월 04일 알고리즘 문제풀이 문제 개인정보 수집 유효기간 난이도 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 def solution(today, terms, privacies): answer = [] today_y, today_m, today_d = today.split('.') today_y = int(today_y) today_m = int(today_m) today_d = int(today_d) def check(y,m,d,t): ans = True m += t while m > 12: y += 1 m -= 12 if y > today_y: ans = False elif y == today_y: if m > today_m: ans = False elif m == today_m: if d > today_d: ans = False return ans arr = dict() for x in terms: term_type, term_months = x.split() arr[term_type] = int(term_months) for i in range(len(privacies)): privacy_date, privacy_type = privacies[i].split() privacy_y, privacy_m, privacy_d = privacy_date.split('.') tmp = check(int(privacy_y),int(privacy_m),int(privacy_d),arr[privacy_type]) if tmp: answer.append(i+1) return answer 기존에는 check() 함수 내의 while문이 존재하지 않았고, if 문을 통해 한번만 로직을 거치도록 했다. 하지만 유효기간이 2년 이상 된다면 12를 여러번 빼서 해를 몇번 넘겨야 할 수도 있기 때문에, 반복문이 필요했다. 유효기간을 더해봤자 2년 이하 일 것이라고 생각한 것이 실수였다. ...
2023년 12월 03일 알고리즘 문제풀이 문제 가장 큰 정사각형 찾기 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def solution(board): answer = 1 p = len(board) q = len(board[0]) dp = [[0 for _ in range(q)] for _ in range(p)] dp[0] = board[0] for i in range(p): dp[i][0] = board[i][0] for a in range(p): for b in range(q): if a-1>=0 and b-1>=0 and board[a][b]==1: dp[a][b] = min(dp[a-1][b-1],dp[a-1][b],dp[a][b-1])+1 answer = max(answer,dp[a][b]) return answer*answer 위 코드는 정확성은 통과했지만 효율성에서 문제를 겪었다. 이 로직은 board 상 1인 좌표마다 검사를 해 가장 큰 사각형의 한 변의 길이가 몇인지 모두 탐색한다. board의 좌표 갯수는 1000000 인데, 이를 평균적으로 500개씩 탐색하면 500000000(5억)이나 수행해야 한다. 결국 아래처럼 고쳐 통과되었다. ...
2023년 12월 02일 알고리즘 문제풀이 문제 짝수와 홀수 난이도 Lv.1 코드 1 2 3 4 5 6 def solution(num): if num%2: answer = 'Odd' else: answer = 'Even' return answer
2023년 11월 28일 알고리즘 문제풀이 문제 3 x n 타일링 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def solution(n): dp = [0 for _ in range(5001)] dp[2] = 3 dp[4] = 11 for i in range(1,n+1): if n%2: return 0 if i%2: continue else: if not dp[i]: tmp = 2 tmp += dp[i-2]*dp[2] for x in range(2,i//2): tmp += dp[i-2*x]*2 dp[i] = tmp%1000000007 return dp[n] 진짜 어렵다. 홀수는 나올수 없으므로 무조건 0이라는 것은 일찍 발견했다. 하지만 일반항을 위한 점화식을 구하기가 어려웠다. 처음에 한 추론은 다음과 같다. ...
2023년 11월 27일 알고리즘 문제풀이 문제 공원산책 난이도 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 def solution(park, routes): H = len(park) W = len(park[0]) a = 0 b = 0 for i in range(H): for j in range(W): if park[i][j] == 'S': a = i b = j def check(p,q,x,y): for i in range(1,q+1): if p == 'N': if x-i < 0 or park[x-i][y] == 'X': return False elif p == 'S': if x+i >= H or park[x+i][y] == 'X': return False elif p == 'E': if y+i >= W or park[x][y+i] == 'X': return False elif p == 'W': if y-i < 0 or park[x][y-i] == 'X': return False if p == 'N': return x-q,y elif p == 'S': return x+q,y elif p == 'E': return x,y+q elif p == 'W': return x,y-q i = 0 while i < len(routes): way_to_go, distance_to_go = routes[i].split() if not check(way_to_go,int(distance_to_go), a,b): i += 1 continue a,b = check(way_to_go,int(distance_to_go), a,b) i += 1 return [a,b] 어렵진 않은데 좀 귀찮고.. 그렇다. 그래도 이런 문제 많이 풀어서 어렵진 않다. 레벨이 1인 이유는 문제에서 따져야 하는 경우를 모두 설명해줘서 그런듯 하다. ...