본문 바로가기

프로그래머스31

[코딩 테스트] 프로그래머스 - 섬 연결하기 (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.3) in Python 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성. 예시: m = 4, n = 3, puddles = [[2, 2]] ~> answer = 4 더 자세한 설명 - programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programme.. 2021. 3. 12.
[코딩테스트] 프로그래머스 - 이중우선순위큐 (Lv.3) in Python 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현하라. 연산의 종류는 1. "I 숫자": 숫자를 삽입 2. "D 1": 큐에서 최댓값 삭제 3. "D -1": 큐에서 최솟값 삭제 programmers.co.kr/learn/courses/30/lessons/42628 풀이 - 어차피 숫자를 하나씩 넣으니까, 새로운 숫자를 넣을 때마다 대소관계 비교하면서 넣으면 되겠다는 생각을 했다. - "I 숫자"연산 위해서는 bisect (이진탐색) 이용. : 대소관계 비교를 매 번 수행해야 하는데, 이 때 이진탐색을 이용하면 O(log n)복잡도를 띄며 효율적이.. 2021. 3. 11.
[코딩 테스트] 프로그래머스 - 블록 이동 (2020 Kakao) in Python "0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성! 더 자세한 정보 - programmers.co.kr/learn/courses/30/lessons/60063 풀이 - 2차원 배열에서 '이동'하는 문제는 너비 우선 탐색 (BFS) 방법이 유용할 때가 많다. - 가능한 주변 좌표에 가보고, 안되면 다시 돌아와 다른 곳으로 가는 로직이 FIFO, 선입선출, 큐의 것과 비슷하기 때문이다. - 언제나 중요한 점! 구현이 복잡해지면, 기능 별로 따로 따로 메소드를 구현하는 것이 상당히 유용하다. 코드 구현 def possible(position, board): next_pos = [] positio.. 2021. 3. 10.

티스토리툴바