본문 바로가기
반응형

Minding's Programming

[코딩 테스트/Python] 코딩 테스트에서 자주 사용되는 Python 표준 라이브러리 코딩 테스트에서 자주 사용되는 알고리즘에는 해시(hash), 탐욕법(greedy), 정렬(sort), 동적 계획법(Dynamic Programming), 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 등이 있다. 이 알고리즘들은 직접 구현할 수도 있지만, 그렇게 하기엔 코드도 너무 길어지고 시간이 오래 걸린다. 코딩 테스트에서 시간은 생각보다 여유 있지 않을 뿐더러, 각 알고리즘 별 직접 구현 코드를 늘 외우고 있기도 어렵다. 이럴 때 Python에서 제공하는 표준 라이브러리를 사용하면 각 알고리즘을 보다 쉽게 구현할 수 있다. 이 글에서는 각 알고리즘 별 표준 라이브러리를 사용해 구현하는 법을 간단히 정리하고자 한다.  1. 해시(hash)해시의 경우, 라이브러리를 따로 임포트하지 않고 기본 자료.. 더보기
[코딩테스트/Python] 프로그래머스 코딩테스트 - 사탕 담기 문제 설명 m 그램(gram)을 담을 수 있는 가방에 사탕을 가득 채우는 경우의 수를 구하려 합니다. 단, 같은 사탕은 또 넣을 수 없습니다. 가방이 감당할 수 있는 무게 m, 사탕별 무게가 담긴 배열 weights가 매개변수로 주어질 때, 가방을 정확히 m 그램으로 채우는 경우의 수를 return 하는 solution 함수를 작성해주세요. 제한 조건 m은 1,000 이상 100,000 이하인 자연수입니다. 모든 사탕의 무게는 10 이상 100,000 이하인 자연수입니다. weights의 길이는 3 이상 15 이하입니다.입출력 예 문제 풀이# itertools의 combinations 이용 (파이썬 기본 라이브러리)from itertools import combinationsdef solution(m, .. 더보기
[코딩테스트/Python] 프로그래머스 코딩테스트 - 운송 트럭 문제 설명 XX 회사는 트럭을 이용해 상품을 운반합니다. 트럭은 최대 무게가 한정되어있습니다. 직원은 트럭에 상품을 순서대로 실으며, 상품을 실을 수 없는 트럭은 바로 목적지로 출발합니다. 이때 우리는 모든 상품을 운반하는데 필요한 트럭은 최소 몇 대인지 구하려 합니다. 예를 들어, 각 상품의 스펙이 다음과 같고, 트럭의 허용 무게가 300, 실어야 할 상품이 ["toy", "snack", "snack"]라고 합니다. 상품 이름 무게 toy 70 snack 200 이 경우 첫째 상품과 둘째 상품은 같은 트럭에 들어가지만, 셋째 상품은 다른 트럭에 넣어야 합니다. 따라서 필요한 트럭 수는 두 대 입니다. 상품 누적 무게 새 트럭 toy 70 불필요 snack 270 불필요 snack 200 필요 트럭의 허.. 더보기
[코딩테스트/Python] 프로그래머스 코딩테스트 - 나머지 한 점 문제 설명 직사각형을 만드는 데 필요한 4개의 점 중 3개의 좌표가 주어질 때, 나머지 한 점의 좌표를 구하려고 합니다. 점 3개의 좌표가 들어있는 배열 v가 매개변수로 주어질 때, 직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 return 하도록 solution 함수를 완성해주세요. 단, 직사각형의 각 변은 x축, y축에 평행하며, 반드시 직사각형을 만들 수 있는 경우만 입력으로 주어집니다. 제한사항 v는 세 점의 좌표가 들어있는 2차원 배열입니다. v의 각 원소는 점의 좌표를 나타내며, 좌표는 [x축 좌표, y축 좌표] 순으로 주어집니다. 좌표값은 1 이상 10억 이하의 자연수입니다. 직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 [x축 좌표, y축 좌표] 순으로 담아 return 해주세요.. 더보기
[코딩테스트/Python] 프로그래머스 코딩테스트 - 최솟값 만들기 문제 설명 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.) 예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면 A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5) A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21.. 더보기
[코딩테스트/Python] 프로그래머스 코딩테스트 - 기능 개발 문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자.. 더보기
[코딩테스트/Python] 코딩테스트 문제 유형 별 문제 풀이 방법 1. 해시(Hash) 대표 문제: 완주하지 못한 선수- 리스트가 숫자가 아닌 문자열일 경우 dict 자료형을 사용하는 것이 유용 (= 해시 자료구조 이용)- get()메서드를 이용해 해당 key값에 해당하는 value를 새로 추가하거나 업데이트 할 수 있음 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이.. 더보기
[CS/Python] 자료구조 & 알고리즘 정리 - 큐, 트리, 힙 큐 (Queues)큐 또한 스택과 함께 많이 사용되는 자료 구조이다. 스택과 마찬가지로 선형 구조라는 공통점을 가지고 있지만, 다른 특성을 가지고 있다. 스택이 LIFO(후입선출) 방식인 반면에, 큐는 FIFO(선입선출) 방식을 가지고 있다. 데이터 원소를 큐에 넣는 동작을 인큐 (enqueue) 연산이라고 부르고, 반대로 큐로부터 데이터 원소를 꺼내는 동작을 디큐 (dequeue) 연산이라고 부른다. 큐를 구현할 때는 선형 배열(리스트)보다 연결 리스트를 사용하는 것이 더 유리하다. 선형 배열은 디큐 연산 시 모든 원소를 한 칸씩 옮겨야 하기 때문에, 시간 복잡도 측면에서 불리하기 때문이다.  양방향 연결 리스트를 이용한 큐 구현class Node: def __init__(self, item): .. 더보기
728x90

티스토리툴바