본문 바로가기

분류 전체보기134

[코딩 테스트] 프로그래머스 - 단속 카메라(Lv.3) in Python 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성. 더 자세한 설명- programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 1. 먼저 routes을 시작점 (원소[0]) 기준으로 오름차순 정렬. 2. minPos = 첫번째원소[0], maxPos = 첫번째원소[1]로 설정해준다. 3. 주어진 routes의 모든 원소를 탐색할 때까지 3-1. 다음 원소의 최솟값이 현재 .. 2021. 3. 14.
[코딩 테스트] 프로그래머스 - 섬 연결하기 (Lv.3) in Python gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.htmln개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하라. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 본다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능하다. 더 자세한 설명 - programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4.. 2021. 3. 14.
[코딩테스트] 프로그래머스 - 도둑질 (Lv.4) in Python 도둑이 어느 마을을 털려 하고 있습니다. 이 마을의 집들은 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. - 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. - money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 예시: money = [1, 2, 3, 1], 정답 = 4 programmers.co.kr/learn/courses/30/lessons/42897 풀이! - 역시나 동적계획법이므로, 각 위치에 도달하기까지의 최댓값을 배열에 넣어주면 된다.. 2021. 3. 13.
[코딩 테스트] 프로그래머스 - 정수 삼각형 (Lv.3) in Python 아래와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능함. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하라. 더 자세한 문제 설명- programmers.co.kr/learn/courses/30/lessons/43105 풀이 - 여느 동적 계획법 문제와 같이, 각 좌표에 다다를 수 있는 방법 중 최적의 것을 기록하는 방식으로 푼다. 동적 계획법 참고 -piaflu.tistory.com/75 - 위 그림과 같은 예시에서는, 각 좌표에 이를 수 있는 최적의 법 (가장 큰 숫.. 2021. 3. 12.

티스토리툴바