📁문제 풀이

[Python] 백준 6497 전력난 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제 해결 포인트 - 크루스칼 (최소 스패닝 트리) 알고리즘 - find 함수 : 부모 노드(어느 집합에 속하는지) 확인 - union 함수 : 정점 a, b를 같은 집합에 속하도록 parent 업데이트 - 여러 테스트케이스 있으므로 n, m이 0, 0 일때 종료 조건으로 무한 반복 - edges : 간선을 비용 기준 오름차순으로 저장 - parent : 각 ..

[Python] 백준 4386 별자리 만들기 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 해결 포인트 - 크루스칼 (최소 스패닝 트리) 알고리즘 - alist : 각 정점의 x, y 정보 저장 - edges : 정점 간 모든 간선 길이( sqrt((x1 - x2)**2 + (y1 - y2)**2) ) 를 오름차순으로 저장 - parent : 집합정보 ( 연결된 정점 정보) - find 함수 : 같은 집합에 속해있는지 확인 - unio..

[Python] 백준 1922 네트워크 연결 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 해결 포인트 - 크루스칼 알고리즘 (최소 스패닝 트리 알고리즘) - 서로소 집합을 위한 find_parent, union_parent 함수 - edges : 간선 비용, 간선a, 간선b를 저장하여 오름차순으로 저장 - parent : 각 정점 별 집합 정보 저장 - 정렬된 edges 를 하나씩 방문하며 사이클이 발생하지 않는다면 간선 연결 - find_parent(a) != find_parent(b) 즉, 같은 집합에 속해있지 않다 ..

[Python] 백준 1647 도시 분할 계획 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 해결 포인트 - 최소 스패닝 트리 문제 (크루스칼 알고리즘) - edges : 간선 비용을 오름차순으로 저장할 리스트 - parent : 서로소 집합 정보 저장할 리스트 - find_parent(x) : 서로 같은 집합에 속해있는지 확인하는 함수 - union_parent(a, b) : a, b 정점에 대해..

[Python] 프로그래머스 순위 | 플로이드-워셜 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 플로이드 워셜 알고리즘으로 해결 가능한 문제 - 정점 i가 1부터 N까지 모든 정점으로 갈 수 있다면 순위를 알 수 있다. - 초기 인접 행렬은 무한수로 초기화, 연관이 있는 두 정점 results는 1로 초기화한다. 이는 1번에 걸쳐 a 정점과 b 정점이 관계가 있다는 뜻이다. - a 정점에서 b 정점으로 바로 가는 방법 (a..

[Python] 백준 1197 최소 스패닝 트리

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 해결 포인트 - 문제 이름에서 알 수 있듯 최소 스패닝 트리 알고리즘 문제입니다. - parent : 서로소 집합 개념에서 각 정점이 어느 집합에 속해있는지 정보를 저장 - edges : 간선의 정보를 저장하는 공간. 가장 작은 비용이 발생하는 간선부터 연결해나간다 - find_parent : 해당..

[Python] 백준 18405 경쟁적 전염 | BFS

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 해결 포인트 - 특정 위치를 중심으로 상하좌우 뻗어가므로 BFS가 적절 - 숫자가 작은 바이러스가 우선되어야 하므로 리스트로 받아 정렬 후 큐로 전환한다! - 큐에 값이 없어질 때까지 꺼내 상하좌우의 각 값이 다시 큐에 넣는 조건에 부합하는지 확인한다. - 큐에서 꺼낸 값의 시간이 S와 같다면 종료 - X-1 행 ..

[Python] 백준 14502 연구소 | BFS

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 포인트 - 0인 값의 모든 위치를 리스트 (blank)에 넣어서 cominations 모듈을 사용해 3개 위치 랜덤 추출(nCr) - 베이스가 되는 기존 정보에 해당 하는 3개의 위치를 1로 설정하고 check 함수 호출 - check 함수 ~ BFS를 위한 큐를 선언하여 값이 2인 위치를 넣는다. ~ 큐에 값을 하나씩 꺼내 해당 하는 위치에서 위, ..

[Python] 프로그래머스 문자열 압축 | 2020 KAKAO BLIND RECRUITMENT

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 [Python] 2, 4, 7, 17, 18, 20 실패 해결 방안 다른 분의 풀이를 보고 참고하여 공유합니다 본인은 반복 발생이 1이라도 전부 문자열에 포함하여 이후 '1'을 제거하는 방식으로 진행했습니다. 이는 2자리 이상의 카운드가 발생하면 문제가 됩니다. '10' -> '0' '11' -> '' '12' -> '2' ... ..