본문 바로가기

algorithm19

크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘을 이해하기 위한 필수 개념 1. 신장 트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 없는 부분 그래프를 의미한다. 2. 최소 신장 트리 : 신장 트리 중에서 최소한의 비용으로 구현된 신장트리를 의미한다. 크루스칼 알고리즘은 최소 신장 트리 알고리즘이며 그리디 알고리즘으로 구현된다 ! 크루스칼 알고리즘의 동작 과정 1. 간선 데이터를 비용에 따라 오름차순 정렬한다. 2. 모든 간선을 한번씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 사이클 발생하지 않는 경우 => 최소신장트리에 추가한다. 사이클 발생하는 경우 => 최소신장 트리에 추가시키지 않는다. 1. 간선 데이터를 비용에 따라 오름차순 정렬 간선 ( 3 , 5 ) ( 4 , 5 ) ( 1 , 3 ) (.. 2024. 3. 4.
프로그래머스 땅따먹기 파이썬 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.
프로그래머스 모음사전 파이썬 완전탐색 알고리즘에 관한 문제이다. 이 문제는 permutations함수를 사용할 사용할 수 없고 재귀 함수를 이용해야 하는 문제이다. dfs를 돌면서 현재 값의 순서를 1씩 증가시켜주고 word와 동일한 단어가 되면 해당 단어의 순서를 ans에 넣어주었다. ans=0 cnt=0 alphabet=['A','E','I','O','U'] def dfs(word,str): #arr에 알파벳 추가 global alphabet,ans,cnt if str==word: ans=cnt #현재 단어와 word값 일치시 정답에 현재단어순서(cnt)를 넣음 return for i in range(len(alphabet)): if len(str) 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.
백준 1010 다리놓기 (파이썬) https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 1. 문제 설명 왼쪽엔 N개, 오른쪽엔 M개의 사이트가 존재한다. 왼쪽 오른쪽 사이트를 연결하는데 겹쳐지는 건 불가능하다. 2. 문제 접근 (실패) 왼쪽을 기준으로 오른쪽 사이트를 연결해 보았을 때 연결할 수 있는 가짓수를 세보았다. 왼쪽에 첫번째 사이트가 오른쪽 첫번째 사이트를 가리키고, 왼쪽 두번째 사이트가 오른쪽 두번째 사이트를 가리키고, 왼쪽 세번째 사이트가 오른쪽 세번째 사이트를 가리키면.. 2024. 2. 2.

티스토리툴바