ok-lab

깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)은 코딩 테스트에서 단골로 출제되는 문제 유형 중 하나다. 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 최대한 깊이 먼저 내려간 후, 더 이상 나아갈 곳이 없는 경우에 옆으로 이동하여 다시 탐색하는 방식이다. 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6 의 형태로 움직이는 것이다. 미로 찾기 등과 같은 문제를 해결할 때 한 방향으로 끝까지 갈 수 있을 때까지 간 후, 더 이상 갈 수 없으면 가장 가까운 갈림길로 돌아와서 해당 갈림길 방향으로 다시 탐색하는 방식으로 볼 수 있다. 모든 경우의 수를 탐색하고자 할 때 DFS를 사용한다. 그러나, 모든 경우의 수를 ..

해당 문제는 대진표에서 대진을 하면서, 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] 값을 리턴하는 방식으로 해결할 수 있따.

해당 문제는 탐욕법(Greedy) 방식으로 접근하면 해결할 수 있는 문제다. 단순히 문제를 해결하는 것뿐만 아니라, 효율성도 따져야 하기 때문에 list로 접근하는 것 보다는 deque으로 접근하는 것이 더 편하다. list를 통해 pop(i)를 하게되면 list 내 존재하는 값을 한 번 서칭하고, pop을 하기 때문에 O(n)이 발생하지만, deque을 사용하면 O(1)로 해결이 가능하기 때문이다. from collections import deque def solution(people, limit): answer = 0 deq = deque(sorted(people)) while len(deq) > 1: if deq[0] + deq[-1] > limit: deq.pop() answer += 1 els..

해당 문제는 프로그래머스 기준 Level 1에 해당하는 문제로 쉽게 해결할 수 있는 문제다. 문제의 핵심을 간략하게 살펴보면, skip에 해당하는 단어는 넘어가고, 단어가 있는 곳에서 index 만큼 떨어진 알파벳으로 변환하면 끝이다. def solution(s, skip, index): answer = '' alphabet = 'abcdefghijklmnopqrstuvwxyz' for sk in skip: alphabet = alphabet.replace(sk, '') for a in s: idx = (alphabet.index(a) + index ) % len(alphabet) answer += alphabet[idx] return answer 먼저, skip에 해당하는 단어를 replace한다. 그..

해당 문제는 프로그래머스 기준 Level 1에 해당하는 문제다. 풀이는 2중 for문을 통해서 먼저 딕셔너리를 생성한다. 이때 자판 패드가 가장 가까운 번호를 기준으로 key와 value를 지정하면 된다. from collections import defaultdict def solution(keymap, targets): answer = [] inform = defaultdict(list) for key in keymap: for i, k in enumerate(key): if inform[k] == []: inform[k] = i+1 elif inform[k] != [] and (i+1) < inform[k]: inform[k] = i+1 for target in targets: values = 0 ..

해당 문제는 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..

해당 문제는 2022 KAKAO TECH INTERNSHIP에 출제된 문제다. 프로그래머스 기준 Level 2에 해당한다. Queue를 통해 푸는 문제로 collections 내 queue를 사용하면 된다. from collections import deque def solution(queue1, queue2): answer = 0 q1 = deque(queue1) q2 = deque(queue2) _max = (len(queue1)) * 3 t1 = sum(q1) t2 = sum(q2) total = t1 + t2 if total % 2 != 0: return -1 queue에서는 popleft라는 함수가 있어서, 왼쪽에 있는 값을 빼는 형태로 진행한다. 문제에서 조건 자체가 왼쪽에 있는 값을 차례대로..

해당 문제는 2018 KAKAO BLIND RECRUITMENT 에서 출제된 문제다. 프로그래머스 기준 Level 1에 해당한다. 다트를 던질 때 Single Double Triple 등을 유의하며, *, #에 해당하는 값도 처리하는 것이 관건이다. 첫 번째 풀이로 접근했을 때, 80% 정도 정답이 나왔다. def calculate(num, oper): if oper == 'S': return num ** 1 elif oper == 'D': return num ** 2 elif oper == 'T': return num ** 3 def solution(dartResult): score = [] for dr in dartResult: if dr.isnumeric(): n = int(dr) elif dr i..