Algorithm
-
Kruskal Algorithm 크루스칼 알고리즘 ?!Algorithm/Source Code 2022. 3. 22. 14:12
Kruskal Algorithm 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다 다시 말해 최소비용 신장트리를 만들기 위한 대표적인 알고리즘 ! 프로그래머스 섬 연결하기 문제를 풀다가 개념을 정리한다 https://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 programmers.co.kr 노드와 간선 노드 = 정점 = 도시 를 의미하며 동그라미에 해당하는 부분이고 간선 = 거리 = 비용 을 의미하며 선에 해당하는 부분이다 예시로 살펴보면 아래 그래프는 노드가 4개 간선이 5개 이다 핵심개념 간선을 거리가 짧은..
-
[백준 2535] 아시아 정보올림피아드Algorithm/Source Code 2022. 3. 18. 19:59
문제 최근 아시아 지역의 학생들만 참여하는 정보 올림피아드 대회가 만들어졌다. 이 대회는 온라인으로 치러지기 때문에 각 나라에서 이 대회에 참여하는 학생 수의 제한은 없다. 참여한 학생들의 성적순서대로 세 명에게만 금, 은, 동메달을 수여한다. 단, 동점자는 없다고 가정한다. 그리고 나라별 메달 수는 최대 두 개다. 예를 들어, 대회 결과가 다음의 표와 같이 주어졌다고 하자. 이 경우, 금메달 수상자는 1번 국가의 1번 학생이고, 은메달 수상자는 1번 국가의 2번 학생이며, 동메달 수상자는 3번 국가의 4번 학생이다. (1번 국가의 3번 학생의 성적이 동메달 수여자보다 높지만, 나라 별 메달 수가 두 개 이하 이므로 1번 국가 3번 학생은 동메달을 받을 수 없다.) 대회 결과가 입력으로 주어질 때, 메달..
-
[프로그래머스 43163] 단어 변환Algorithm/Source Code 2022. 3. 17. 15:30
문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로..
-
[프로그래머스 42627] 디스크 컨트롤러Algorithm/Source Code 2022. 3. 15. 01:39
문제 설명 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를들어 # 0ms 시점에 3ms가 소요되는 A작업 요청 # 1ms 시점에 9ms가 소요되는 B작업 요청 # 2ms 시점에 6ms가 소요되는 C작업 요청 와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다. 한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다. # A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms) # B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11..