목록CodingTest/programmers (96)
기억은 짧고 기록은 길다
[프로그래머스/Programmers] 다리를 지나는 트럭 - Python
Link 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr Solution def solution(bridge_length, weight, truck_weights): answer = 0 q = [0] * bridge_length while q: answer += 1 q.pop(0) if truck_weights: if sum(q) + truck_weights[0] weight: bridge.append(0) else: truck = truck_weights.pop() bridge.a..
[프로그래머스/Programmers] 기능개발 - Python
Link 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr Solution def solution(progresses, speeds): answer = [] count = 0 idx = 0 while idx != len(progresses): for i in range(len(progresses)): progresses[i] += speeds[i] while idx = 100: count += 1 idx += 1 else: break ..
[프로그래머스/Programmers] 구명보트 - Python
Link 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr Solution 해당 문제는 두 개의 인덱스 변수를 사용해야 한다는 것을 떠올리면 쉽게 해결할 수 있는 문제였다. 필자의 풀이에서는 한 구명보트에는 최대 두명이 탑승 가능하므로 가장 가벼운 사람과 가장 무거운 사람의 무게를 합쳤을 때 limit보다 무거우면 무거운 사람을 혼자 태우고 2번째로 무거운 사람과 가장 가벼운 사람을 다시 태워보는 풀이를 코드로 구현하였다. def solution(people, limit): answe..
[프로그래머스/Programmers] 게임 맵 최단거리 - Python
Link 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr Solution 해당 문제는 BFS(Breadth-First Search)를 사용하여 해결하는 문제였다. BFS는 너비 우선 탐색으로 Graph Algorithm 중 하나이다. BFS와 DFS에 대해 자세하게 설명해놓은 글을 첨부할테니 참고바란다. from collections import deque def solution(maps): n = len(maps) m = len(maps[0]) if m..
[프로그래머스/Programmers] 가장 큰 정사각형 찾기 - Python
Link 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr Solution 해당 문제는 Dynamic Programming을 활용하여 해결해야하는 문제였다. Dynamic Programming을 간단하게 설명하자면 주어진 문제를 여러 개의 부분 문제로 나누어 푼 뒤 그 결과를 토대로 주어진 문제를 푸는 방식이다. 또한 memoization 기법을 사용해 반복으로 인한 계산을 줄어주기 때문에 시간복잡도를 줄이는데 효과적이다. Dynamic Programming을 피보나치 수열에 적용하여 Dynamic Programming을 설명한 좋은 글을 첨부할테니 참고바란다. from itertools import ..
[프로그래머스/Programmers] N개의 최소공배수 - Python
Link 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr Solution 해당 문제는 arr가 오름차순으로 정렬되어 주어지기 때문에 arr[0]과 arr[1]의 최소공배수를 구하고 구한 최소공배수와 arr[2]의 최소공배수를 구하고 이런식으로 진행하여 모든 수의 최소공배수를 구하는 방식으로 진행하였다. for문에서 최대한 시간복잡도를 줄이기 위해 arr[i]부터 answer * arr[i] + 1까지 arr[i]의 간격으로 진행하여 최소공배수를 구하였다. ex) ar..