PS/Algorithm-Python

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있다. 또한 길마다 길을 유지하는 데 드는 유지비가 있다. 마을의 이장은 마을이 너무 커서 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 즉 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 하고, 마을에는 집이 하나 이상 있어야 한다. 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 학생들에게 0부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어 총 N+1개의 팀이 존재한다. '팀 합치기' 연산은 두 팀을 합치는 연산이다. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는 지를 확인하는 연산이다. M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하라 입력 조건 첫째 줄에 N, M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 ≤ N, M ≤ 100,000) 다음 M개의 줄에는 각각의 연산이 주어진다. '팀 합치기' 연산은 0 a b 형태로 주어진다. 이는 a번 학생이 속한 팀과 b번 학생이 속한..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 위상 정렬(Topology Sort) 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 진입 차수(in-degree): 특정한 노드로 들어오는 간선의 개수 진입 차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다. 이때 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 기본적으로 위상정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 많으므..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 신장 트리(Spanning Tree) 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 이때 "모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다"는 조건은 트리의 성립 조건이기도 하다. 크루스칼 알고리즘(Kruskal Algorithm) 대표적인 최소 신장 트리 알고리즘 최소 신장 트리 알고리즘: 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선을 하나씩 확인하며 현재..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 서로소 집합 (Disjoint Sets) 서로소 집합: 공통 원소가 없는 두 집합 서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다. "union-find 자료구조"라고 불리기도 한다. union(합집합) 연산: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find(찾기) 연산: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조 서로소 집합 자료구조는 트리 자료구조를 이용하여 집합을 표현한다. 서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 그래프 이론 코딩 테스트에서 자주 등장하는 기타 그래프 이론 다양한 그래프 알고리즘 앞의 "DFS/BFS"와 "최단 경로"에서 다룬 내용은 모두 그래프 알고리즘의 한 유형으로 볼 수 있다. 이외의 다양한 그래프 알고리즘에 대해 알아보자 예를 들어 크루스칼 알고리즘(Kruskal Algorithm)은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘(Topology Sort Algorithm)은 큐 자료구조 혹은 스택 자료구조를 활용해 구현할 수 있다. 그래프 그래프(Graph)란 노드(node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조를 의미한다. 알고리즘 문제에서 "서로 다른 개체가 연결되..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 어떤 나라에 N개의 도시가 있다. 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내 해당 메시지를 전송할 수 있다. 하지만 X도시에서 Y도시로 전보를 보내기 위해서는 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다. 어느 날 C 도시에 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로의 정보가 주어졌을 때, 도시 C에서 보낸 메시지를 받게 되는 도시의 총 개수와 도시들이 모두 메시지를 받..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 방문 판매원 A는 현재 1번 회사에 있으며, X번 회사에 방문해 물건을 판매하고자 한다. 공중 미래 도시에서 특정 회사에 도착하기 위해서는 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 도로는 정확히 1만큼의 시간으로 이동할 수 있다. 또한 방문 판매원 A는 소개팅에도 참석하고자 한다. 소개팅 상대는 K번 회사에 존재한다. 따라서 방문 판매원 A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표이다. 이때, 방문 판매원 A는 가능한 한 빠르게 이동하고자 한다. 방문 판매원이 회사 사이를 이동하게 되는 최소 시간을 계산하..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 최단 경로 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 가장 빠른 길 찾기 최단 경로(Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. "길 찾기" 문제라고도 불린다. 보통 그래프를 이용해 표현하는데, 각 지점은 "노드", 지점 간 연결된 도로는 "간선"으로 표현된다. 자주 사용하는 최단 거리 알고리즘은 다익스트라, 플로이드 워셜, 벨만포드 3가지이다. 예제에서는 코딩 테스트에서 많이 등장하는 다익스트라와 플로이드 워셜 알고리즘 유형만 다룬다. 다익스트라(Dijkstra, 테이크스트라) 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 ..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 N가지 종류의 화폐를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 입력 조건 첫째 줄에 N, M이 주어진다. (1