분류 전체보기 310

[Algorithm] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

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

Python/Algorithm 2023.09.23

[프로그래머스] 예상 대진표 - Python

해당 문제는 대진표에서 대진을 하면서, 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 와 같은 경우다. 해당 경우는 다음 경기에 붙기 때문에 그 결과를 제외하고 처리를 하면 된다.

Python/Algorithm 2023.09.23

[프로그래머스] 점프와 순간 이동 - Python

해당 문제는 역순으로 생각하는 것이 키 포인트다. 마지막 예제 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

Python/Algorithm 2023.09.16

[프로그래머스] 멀리 뛰기 - Python

해당 문제는 피보나치 수열로 문제를 풀 수 있다. 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] 값을 리턴하는 방식으로 해결할 수 있따.

Python/Algorithm 2023.09.16

[프로그래머스] 구명보트 - Python

해당 문제는 탐욕법(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..

Python/Algorithm 2023.09.16

네이버 Tune CIC Music AI 오토 태깅 면접 후기

네이버 Turn CIC에서 Music AI 오토 태깅 관련 체험형 인턴 모집에 지원했다. 서류 합격 발표는 일주일 정도 걸렸던 것 같고, 서류에 있었던 논문 내용을 기점으로 면접에서 기술하는 형태로 진행하였다. 모집 요강을 살펴보면, 쿠버네티스 관련 지식, SQL 지식, 딥러닝 지식, 콘텐츠 기반 지식이 있어야 가능한 것으로 보인다. 서류 합격 운이 좋게도 서류는 합격하여 면접 기회를 받게 되었다. 원래 분야가 음성 처리 쪽이 아니다 보니, 서류 합격에 의의를 두고 면접에 임하자고 생각했다. 면접 후기 기억나는 면접 질문은 다음과 같다. 본인의 현재 가지고 있는 역량으로 오토 태깅을 한다면 어떻게 할 수 있을지? 입사한다면, 자율적으로 업무를 진행하는 것이 좋은지, 아니면 케어하면서 진행하는게 좋은지? ..

Interview 2023.09.09

틸다(Tilda) ML Engineer / Data Scientist 면접 후기

대학원을 졸업하고 취준생에 길에 이르러, 면접을 보고 합격 여부를 떠나 이를 정리해야겠다는 생각이 들었다. 현재까지 면접을 본 회사는 SK 브로드밴드, SK 플래닛, 네이버, 뤼튼, 하나캐피탈 정도 되는 것 같다. 공채 시즌이 다가오면서 다른 사람들도 면접 내용을 보고 함께 공유하면 좋을 것 같아서 정리한다. 틸다 ML/DS 이번에 면접을 본 회사는 ML 솔루션을 개발하는 회사인 틸다(Tilda)라는 회사다. 지원 자격의 경우 석사인 경우 ML/DS 전공, 학사인 경우 부트캠프 등과 같은 교육 이수, Kaggle 대회 참여 등과 같은 기술적인 부분에 초점을 두고 채용을 진행하는 것으로 보여서 지원하게 되었다. 또한, 나는 석사 학위 보유자며, 대학교에서는 수학과 경제학 그리고, 대학원에서 빅데이터응용학과..

Interview 2023.09.09

[프로그래머스] 둘만의 암호 - Python

해당 문제는 프로그래머스 기준 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한다. 그..

Python/Algorithm 2023.09.08

[프로그래머스] 대충 만든 자판 - Python

해당 문제는 프로그래머스 기준 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 ..

Python/Algorithm 2023.09.08

[프로그래머스] 메뉴 리뉴얼 - Python

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

Python/Algorithm 2023.09.05
반응형