할머니의 콤퓨타 도전기

크루스칼 알고리즘(Kruskal Algorithm) 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. (최소비용신장트리를 만들기 위한 대표적인 알고리즘) 여러개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자할 때 실제로 적용합니다. ​ 모든 간선정보를 오름차순으로 정렬한 뒤에 (간선 거리(비용)이 짧은(적은) 순서대로 정렬) 비용이 적은 간선부터 차근차근 그래프에 포함시키면 됩니다. 1. 정렬된 순서에 맞게 그래프에 포함 2. 포함시키기 전에는 사이클 테이블 확인 3. 사이클을 형성하는 경우 간선을 포함시키지 않는다 ​ 사이클이 발생하는 지의 여부는 Union-Find 알고리즘을 적용하면 됩니다. #include #include #include..

문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작..

문제 설명 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 문제 풀이 벨만 포드 알고리즘 문제입니다. https://jioneprogstdy.tistory.com/32 벨만 포드 알고리즘(Bellman-Ford Algorithm) Bellman-Ford Algorithm 시작점으로 부터 다른 모든 정점으로의 최단 경로를 구하는 다익스트라 알고리즘과 유사합니다. 그러나 벨만 포드 알고리..

Bellman-Ford Algorithm 시작점으로 부터 다른 모든 정점으로의 최단 경로를 구하는 다익스트라 알고리즘과 유사합니다. 그러나 벨만 포드 알고리즘은 간선 cost가 음수인 경우에도 사용할 수가 있습니다. (O(VE)의 시간으로 다익스트라 알고리즘보다는 시간이 오래걸림) 위와 같은 그래프에서 0번 정점으로 부터 2번 정점까지의 최단거리를 구하고자 합니다. 최단거리는 0->1->2 를 거쳐서 12+(-9)=3이 됩니다. 그러나 다익스트라 알고리즘에서는 dist[1]=12 > dist[2]=7 이기 때문에 2번 정점을 방문하게 되고 따라서 음의 간선이 존재하는 그래프에서는 최단경로를 제대로 구할 수 없게 됩니다. 벨만 포드 알고리즘은 2중 for문을 통해 가능한 모든 경우를 다 체크합니다. 최단경..

CSV(Comman Separated Values) 몇 가지 필드를 쉼표(,)로 구분한 텍스트 데이터 및 텍스트 파일입니다. 호환되지 않는 포맷을 사용하는 프로그램 끼리 자료를 전달할 때 사용합니다. Split 하여 처리하기 편하다는 장점이 있습니다. List to CSV file import pandas as pd data = pd.DataFrame(db) data.columns = ['키워드','제목', '내용', 'uid', '채널명','채널id','조회수','좋아요','싫어요','댓글 수','태그','구독자 수','영상 등록일','영상 길이','정보수집일'] s = db[0][0].replace('"',"") # 한글깨짐 현상 발생 : encoding utf-8-sig 로 전환 data.to_cs..

문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 입출력 예 N number return 5 1..