본문 바로가기

프로그래머스4

프로그래머스 - 섬연결하기 (파이썬) 프로그래머스 Lv3 - 섬연결하기 문제설명 n개의 섬 사이에 다리를 건설하는 비용이 주어지고, 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 구한다. 그래프에서 최소비용으로 모든 노드를 연결할 수 있는 최소신장트리를 찾는 문제이다. 문제풀이 1. 크루스칼 알고리즘 사용 # 부모 노드를 찾기 위한 함수 def find(parent,x): if parent[x]==x: return x else: return find(parent,parent[x]) # 부모 노드가 다를 경우 두 노드가 속한 집합을 합침 (두 집합에 간선을 연결한다고 생각하기) def union(parent,a,b): root_a=find(parent,a) root_b=find(parent,b) # 부모 노드는 무조건 작은 값을.. 2024. 3. 5.
프로그래머스 땅따먹기 파이썬 1. dfs(x) 가능한 모든 경우의 수를 구하기 위해 dfs를 사용했다. 깊이가 깊어지면 런타임에러가 발생하게 된다. answer=0 def dfs(land,now_x,now_y,pre_y,tot): global answer if len(land)==now_x: answer=max(answer,tot) elif pre_y != now_y: for i in range(4): dfs(land,now_x+1,i,now_y,tot+land[now_x][now_y]) def solution(land): global answer for i in range(4): dfs(land,0,i,-1,0) return answer 2. i행에서 i-1행을 값 선택 i행의 각 값에 선택할 수 있는 i-1행의 값들중 가장 큰값.. 2024. 2. 23.
프로그래머스 게임 맵 최단거리 파이썬 1. dfs 사용 (x) bfs 사용하기 위해서는 현재 위치를 다시 방문하지 않아야 하는데 이 문제는 오른쪽, 아래로 이동할 뿐만 아니라 위, 왼쪽으로 이동도 가능하므로 현재 위치를 또 방문할 가능성이 생긴다. 따라서 bfs가 아닌 완전탐색 문제로 풀어야 한다. 그러나 완전탐색으로 풀면 깊이가 너무 깊어져 효율성 테스트에서 런타임 오류가 발생한다. import sys answer= sys.maxsize #int 최대값으로 초기화 # cnt = 이동한 칸 횟수 , point = 현재 위치 좌표 , check = 방문한 좌표인지 확인하기 위해 def dfs(maps,cnt,point,check): global answer if point[0]==len(maps)-1 and point[1]==len(maps[.. 2024. 2. 23.
프로그래머스 Lv3. 단속카메라 (파이썬) https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 각 차량이 단속용 카메라를 최소 한번은 만나야 한다. routes 배열에는 각 차량의 출발지점 & 도착지점이 들어있다. 출발지 또는 도착지에 카메라가 있어도 카메라를 만난것으로 간주한다. -> 모든 차량이 단속용 카메라를 만나기 위한 카메라의 최소 개수는? 배열의 겹치는 부분을 찾되 최소한의 카메라를 놓아야 한다. 테스트 케이스를 보면 겹치는 부분은 세군데이지만 카메라는 두개만 있어도 모든 차량이.. 2024. 2. 2.

티스토리툴바