[Programmers] - 완주하지 못한 선수 (해시) with Python

문제 해시 - 완주하지 못한 선수 문제 분석하기 굉장히 쉬운 문제예요! 머리 예열 겸 코딩 테스트 연습을 다시 풀고 있어요. 아쉽게도 지원 언어가 C++, Java, JavaScript, Python 뿐이고 Swift는 없어서, 저의 경우 Java, JavaScript, Python으로 풀었는데 이 글에서는 Python의 코드로만 설명해볼게요 :) 그리고 이 글을 쓰게 된 이유는 가장 아래 문제 풀이 고민에서 말해볼게요! 두 가지 배열이 주어지고, 앞선 배열인 participants는 반드시 뒤의 배열인 completion 보다 요소 1개를 더 가지고 있고 이 요소를 찾는 문제예요. 가장 단순하게는 participants를 for문으로 돌고, completion을 그 안에서 순회하면서 매칭 되는지 여부를..
알고리즘 학습/프로그래머스 2022. 3. 23. 11:20
[Programmers] - 모음사전 (위클리 챌린지) with Python

문제 위클리 챌린지 - 모음사전 문제 분석하기 길이 5 이하이므로 사전을 전부 만든 후 검색을 해도 속도에 문제가 없어요. 참고로 사전의 총 길이는 5 + 5^2 + 5^3 + 5^4 + 5^5 가 될 거예요 :) 이 사전을 구현하기 위해 재귀 함수를 사용할 수 있겠지만 파이썬의 모듈인 product를 사용하면 보다 손쉽게 구현할 수 있어요. Product 사용하기 Product는 itertools에서 사용할 수 있어요. itertools에는 Permutation, Combination이 있는데 이것은 순열과 조합이므로 중복을 허락하지 않아요. 이 문제에서는 중복이 필요하기 때문에 Product를 사용해요. 사실 Product는 이름 그대로 product 곱을 위한 모듈이에요. 예시를 살펴볼게요! ite..
알고리즘 학습/프로그래머스 2022. 2. 17. 22:51
[Programmers] - 불량 사용자 (2019 카카오 개발자 겨울 인턴십) with Python

📎 간략한 문제 정리 입력된 사용자 목록에서 불량 사용자 목록에 등록된 아이디를 제거합니다. 불량 사용자 목록에 있는 아이디는 정확한 아이디가 아니라 *를 사용한 아이디로 *에는 어떠한 문자가 들어가든 다른 문자가 매칭되면 제거합니다. 이렇게 제거 가능한 아이디 조합의 종류를 찾는 문제입니다. 📈 문제 분석 문제가 어렵지 않아 보이지만 보기보다 난이도가 있는 문제입니다. 계속 가능성을 제외하는 좋은 로직을 생각하는 함정에 빠지면 구현에서 문제가 생깁니다. 한번에 모든 문제를 해결하려는 로직을 구현할 수 있다면 이상적이지만 언제나 완전 탐색의 가능성을 배제하면 안됩니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 수학적으로 계산하려고 했습니다. 가능성이 있는 모든 경우를 찾아 교집합 부분을 제거하려고 했는데 이..
알고리즘 학습/프로그래머스 2021. 5. 8. 12:31
[Programmers] - 보석 찾기 (2020 카카오 인턴십) with Python

📎 간략한 문제 정리 전체 배열의 모든 요소를 가진 set이 있을 때, 이 set의 모든 요소를 가진 배열의 부분 배열 중 최소의 길이를 가진 구간을 찾는 문제입니다. 📈 문제 분석 단순히 전체 순회를 하면 속도 이슈가 발생할 수 밖에 없습니다. 범위가 100,000 이므로 O(N^2)이면 바로 속도 이슈가 발생합니다(100번 연산). 아주 단순한 생각으로는 for문을 2차원으로 돌려 i와 j를 정하고, [i:j] 구간에서 모든 요소를 갖는지 검색해보면 되겠지만 이 검색 역시도 cost가 발생하는데다가 검색 자체에서 이미 속도를 넘어서므로 더 효율적인 방법이 필요합니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 저는 슬라이딩 윈도우를 생각했고, 이 슬라이딩 윈도우의 크기를 이분탐색을 통해 찾는 방식을 생각했..
알고리즘 학습/프로그래머스 2021. 5. 5. 11:30
[Programmers] - 수식 최대화 (2020 카카오 인턴십) with Python

📎 간략한 문제 정리 기존 사칙연산의 연산자 우선순위가 아니라 임의로 연산자 우선순위를 정해 주어진 expression의 연산을 합니다. 연산 결과의 절대값 중 가장 큰 값을 반환합니다. 📈 문제 분석 이 경우 모든 경우를 탐색하는 Brute-Force(완전 탐색)을 통해 최적의 결과를 찾아냅니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 기존의 제 풀이는 연산자 우선순위대로 탐색하며 연산을 진행하고, 다음 연산자를 검색하며 다음 연산을 진행하는 방식으로 결과를 찾았습니다. 하지만 공부를 위해 이 문제를 새로 풀며 중위 표기를 후위 표기로 바꾸는 과정에 연산자 우선순위가 있음을 기억했고 그 연산자 우선순위 표만 바꾸는 구조로 작성하면 되므로 중위를 후위로 바꾸는 메소드 한개, 후위 연산을 계산하는 메소드 한..
알고리즘 학습/프로그래머스 2021. 5. 4. 21:53
[Programmers] - 키패드 누르기 (2020 카카오 인턴십) with Python

📎 간략한 문제 정리 손가락을 움직이며 키패드를 누르는데 어떤 손가락으로 누를지를 기록하여 출력하는 문제입니다. 📈 문제 분석 특정한 알고리즘을 사용하는 것이 아니라 문제 조건을 그대로 시뮬레이션 하는 문제입니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 문제의 조건을 그대로 시뮬레이션하면 되는 문제입니다. 거리를 구하는 방법이 중요한데 이동이 위, 아래, 좌, 우로만 이루어지므로 절대적인 거리(피타고라스의 정리)를 직접 구할 필요 없이 좌로, 우로 이동하는 것만 생각하면 됩니다. 💻 풀이한 코드 def solution(numbers, hand): keypad = {"1": (0, 0), "2": (0, 1), "3": (0, 2), "4": (1, 0), "5": (1, 1), "6": (1, 2), "7..
알고리즘 학습/프로그래머스 2021. 5. 1. 17:33
[Programmers] - N으로 표현 (동적계획법) with Python

📎 간략한 문제 정리 주어진 숫자 N을 반복 활용해서 사칙연산을 통해 number를 만듭니다. number를 만들기 위해 필요한 N의 최소 개수를 출력합니다. 📈 문제 분석 N을 최대로 활용할 수 있는 개수가 8개로 한정 되어있어 보다 쉽게 풀이 가능한 문제입니다. 단순히 5로만 연산하는 것이 아니라 5를 2개 사용할 경우 55가 되기 때문에 상황 설계를 엄밀히 할 필요가 있습니다. 개수만 늘려가며 사칙연산의 경우를 추가하면 안됩니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 그래프적으로 문제를 인식하여 Pruning을 생각해보았지만 뺄셈 연산이나 나누기 연산처럼 값이 작아지는 경우가 있기 때문에 Pruning 할 수 없었습니다. 포인트는 특정 개수의 N으로 만들 수 있는 모든 경우의 수를 기록하고, 그 안..
알고리즘 학습/프로그래머스 2021. 4. 24. 12:14
[Programmers] - 입국심사 (이분탐색) with Python

📎 간략한 문제 정리 n명의 사람이 입국심사를 위해 줄을 서서 기다리고 있습니다. 심사관마다 심사하는데 걸리는 시간이 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하려고 합니다. 모든 사람이 심사를 받는데 걸리는 시간의 최소값을 return하는 함수를 작성합니다. 📈 문제 분석 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다. 또한 심사관은 1명 이상 100,000명 이하이고, 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분이하입니다. 시뮬레이션으로 각 상황을 그리며 결과를 비교하면 시간초과가 발생할 수 밖에 없는 범위입니다. O(N)만..
알고리즘 학습/프로그래머스 2021. 4. 23. 21:43
1 2 3 4 ··· 6