ok-lab

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 위 형태로 Triangle을 구성하면 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 가 된다. 먼저 문제를 풀기 전에 Index Error가 발생하지 않도록 각 행의 양 옆에 [0]을 P..

문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 2자리 이상, 1,000,000 자리 이하인 숫자입니다. k는 1이상, number의 자릿수 미만인 자연수입니다. 해당 문제는 탐욕법(Greedy) 방식으로 접근하는 문제다. d..

해당 문제는 Summer/Winter Codding(~2018)에 출제된 문제로 Level 2에 해당한다. 11 by 11 Matrix로 구성된 좌표 평면에서 캐릭터가 이동하고, 캐릭터가 지나간 길 중 처음 걸어본 길의 길이를 구하는 문제다. 입력이 'ULURRDLLU'로 주어졌다면, 아래와 같이 그려볼 수 있고, 8과 9에 해당하는 이동은 처음 걸어본 길이 아니기 때문에 빼고 값은 7이 된다. 두 번째 예시의 경우, 벽에 붙은 경우에는 이를 무시한다. 해당 문제는 좌표 평면 + 집합으로 계산하면 쉽게 해결이 가능하다. 집합을 통해 시작 지점과 끝 지점을 양방향 그래프, 무향 그래프로 표현하고 전체 길이에서 2를 나누게 되면 처음 방문한 거리가 나온다. 만약에 문제에서 방향 까지 고려한다고 했으면, 코드..

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 처음 문제를 접근했을 때는 아래와 같이 deque으로 접근했다. deque으로 접근하게 되면, 매번 Sorted를 통해서 정렬을 해주어야 하기 때문에 시간 초과가 발생했다. from collections import deque def solution(scoville, K): scv = deque(sorted(scoville)) cnt = 0 while min(scv) < K: cnt += 1 x, y = scv.popleft(), scv.popleft() scv.append(x + y*2) scv = deque(sorted(scv)) if len(scv) == 1: return -1 r..

해당 문제는 DFS로 해결이 가능하다. DFS 는 깊이 우선 탐색으로, 한번에 던전을 갈 수 있는 끝까지 탐색한 후 이전 단계로 돌아가는 작업을하면 된다. 이때, 방문 여부와 방문 횟수를 초기화하고 다시 탐색을 하면 끝이다. answer = 0 def solution(k, dungeons): global answer def DFS(k, cnt, dungeons, visited): global answer answer = max(answer, cnt) # 최대 방문 횟수 for i in range(len(dungeons)): if visited[i] == 0 and k >= dungeons[i][0]: visited[i] = 1 # 방문 DFS(k-dungeons[i][1], cnt+1, dungeons,..

해당 문제는 Level 2에 해당하는 문제로, "해시"로 분류된 문제다. 조합 공식을 이용해 아래와 같이 쉽게 풀이할 수 있다. from collections import defaultdict def solution(clothes): inform = defaultdict(list) answer = 1 for cl in clothes: k, v = cl inform[v] += [k] for k in inform.keys(): n = len(inform[k]) answer *= (n + 1) return answer - 1 모든 의상에 대해서 가지고 온 후, 모든 조합을 계산한다. 이때 모든 조합이란, 옷을 아무것도 입지 않는 경우도 포함하는 것이다. 그렇기 때문에 마지막에 -1을 해주어서 값을 도출하면 된다.

해당 문제는 대진표에서 대진을 하면서, A와 B가 몇 번째 붙는지를 찾는 문제다. A와 B는 무조건 계속 이긴다는 가정하고 있다. A와 B를 나누어서 결국 1, 2 혹은 3, 4 처럼 두 값의 차이가 하나 인 경우를 찾으면 된다. def solution(n,a,b): for i, _ in enumerate(range(n//2)): if abs(a-b) == 1 and (a//2) != (b//2): return i + 1 a = round(a/2 + 0.1) b = round(b/2 + 0.1) a//2 와 b//2가 같은 경우는 2, 3 혹은 4, 5 와 같은 경우다. 해당 경우는 다음 경기에 붙기 때문에 그 결과를 제외하고 처리를 하면 된다.

해당 문제는 역순으로 생각하는 것이 키 포인트다. 마지막 예제 5000을 예시로 들면, 5000 -> 2500 -> 1250 -> 625 -> 624 -> 312 -> 156 -> 78 -> 39 -> 38 -> 19 -> 18 -> 9 -> 8 -> 4 -> 2 -> 1 -> 0 굵은 숫자를 보면, 1번씩 이동해야되는 경우가 발생한다. 즉, 나누어서 2로 떨어지지 않으면 K칸을 점프해야 된다는 것이다. def solution(n): ans = 1 while n != 1: if n % 2 == 0: n /= 2 else: n -= 1 ans += 1 return ans

해당 문제는 피보나치 수열로 문제를 풀 수 있다. def solution(n): if n == 1: return 1 else: p = [0] * n p[0] = 1 p[1] = 2 for i in range(2, n): p[i] = (p[i-1] + p[i-2]) % 1234567 return p[-1] 점화식으로 풀이를 진행했는데, 마지막에 1234567으로 나누지 않았을 때에는 테스트 케이스의 값이 너무 커서 런타임에러가 발생했다. 매번 값을 계산할 떄마다 1234567을 나눠주는 형태로 결과를 도출하고 마지막 p[-1] 값을 리턴하는 방식으로 해결할 수 있따.

해당 문제는 2021 KAKAO BLIND RECRUITMENT에서 출제된 문제다. 프로그래머스 기준 Level 2에 해당한다. 이번 문제는 combinations 함수와 Counter 함수를 사용하면 쉽게 해결이 가능하다. from itertools import combinations from collections import Counter def solution(orders, course): answer = [] for n in course: candidates = [] for menu in orders: for l in combinations(menu, n): candidates.append(''.join(sorted(l))) candidates = Counter(candidates).most_co..