본문 바로가기

Programmers39

[프로그래머스] 추억점수 def solution(name, yearning, photo): answer = [] # {'may': 5, 'kein': 10, 'kain': 1, 'radi': 3} name_dict = {name:yearning[i] for i,name in enumerate(name)} for i,row in enumerate(photo): total = 0 for j,col in enumerate(row): if name_dict.get(col) != None: total += name_dict[col] answer.append(total) return answer 이번 문제는 사전 자료형을 사용하여 간단하게 풀 수 있던 문제였다. 여기서 기억해야 할 점은 사전 자료형에서 어떠한 값을 접근할 때 get() 메.. 2023. 6. 23.
[프로그래머스] 달리기 경주 def solution(players, callings): # {'mumu': 0, 'soe': 1, 'poe': 2, 'kai': 3, 'mine': 4} player_dict = {player:rank for rank,player in enumerate(players)} # {0: 'mumu', 1: 'soe', 2: 'poe', 3: 'kai', 4: 'mine'} rank_dict = {rank:player for rank,player in enumerate(players)} for call in callings: call_index = player_dict[call] prev_index = call_index -1 player_dict[rank_dict[call_index]], player_di.. 2023. 6. 23.
[프로그래머스 Lv.3] 정수 삼각형 이번 문제는 Dynamic Programming 문제의 대표적인 예제인 정수 삼각형로, 대각선 방향으로만 움직일 수 있을 때 거쳐간 숫자의 합이 최대가 되도록 만드는 문제이다. 단순하게 완전탐색(DFS/BFS)로 풀 순 있겠지만, 이 문제의 경우 삼각형의 높이가 한 층씩 높아질수록 경우의 수 가 2배씩 늘어나는 문제로 단순히 완전탐색 알고리즘으로 풀게 되면 문제의 조건(높이는 1이상 500이하) 때문에 O(2^n)의 시간복잡도로 인해 시간초과가 발생할 것이다. 따라서 모든 경우의 수를 전부 구하는 완전 탐색이 아니라, 별도의 자료구조에 정보들을 저장하면서 중복된 연산을 최대한 줄여주는 DP 알고리즘을 사용하여 풀어야만 한다. 먼저 이전에 포스팅한 DP 알고리즘에 대한 내용을 복습할 겸 이 문제가 왜 DP.. 2023. 2. 28.

티스토리툴바