📌문제각 자리가 숫자로만 이루어진 문자열 S가 주어졌을 때 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 X 혹은 + 연산자를 넣어 결과적으로 만들어 질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정 📌풀이대부분은 +보다 x 연산이 값을 더 크게 만듦하지만 두 수 중에서 하나라도 0이나 1인 경우 곱하기 보다 더하기 수행하는 것이 효율적 📌코드data = input()# 첫번째 문자를 숫자로 변경하여 대입result = int(data[0])for i in range(1, len(data)): # 두 수 중 하나라도 0 혹은 1인 경우 더하기 num = int(data[i]) if result 📌참고https..
📌문제한 마을에 모험가 N명이 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했는데 공포도가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 대처 능력이 떨어집니다. 모험가 길드장이 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여하도록 규정했습니다. N명의 모험가 정보가 주어졌을 때 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요. 📌풀이공포도를 오름차순으로 정렬공포도가 낮은 모험가부터 하나씩 확인하며 만약 현재 그룹에 포함된 모험가 수가 현재 확인하고 있는 공포도보다 크거나 같다면 그룹 결성 📌코드n = int(input())data = list(map(int, input().split()))data...
📌문제온라인으로 강의를 들으려 하는데 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 동빈이는 N개의 강의를 듣고자 한다. 모든 강의는 1~N번까지의 번호를 가진다. 또한 동시에 여러 강의를 들을 수 있다고 가정한다. 동빈이가 듣고자하는 N개의 강의 정보가 주어졌을 때 N개의 강의에 대해 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오 📌풀이위상 정렬 알고리즘 사용각 각의에 대해 인접 노드를 확인할 때 현재보다 강의 시간이 더 긴 경우를 찾는다면 더 오랜 시간이 걸리는 경우의 시간 값을 저장하는 방식으로 결과 테이블 갱신 리스트의 경우 단순 대입 연산을 하면 값이 변경될 대 문제가 발생할 수 있기 때문에 리스트 값을 복제해야 할 때는 deepcopy..
📌문제마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을을 분할할 때는 각 분할된 마을 안에 집들이 서로 연결되도록 분할해야 한다.마을의 이장은 계획을 세우다 마을 안에 길이 너무 많다는 생각을 했다. 일단 분리된 두 마을 사이 길은 필요 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하는 프로그램을 작성하시오. 📌풀이전체 그래프에서 2개의 최소 신장 트리 만들어야 함크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중..
📌문제학교에서 학생들에게 0~N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어 총 N+1개의 팀이 존재한다. 이때 선생님은 팀 합치기 연산과 같은 팀 여부 확인 연산을 사용할 수 있다.1. 팀합치기 연산은 두 팀을 합치는 연산이다.2. 같은 팀 여부 확인 연산은 두 학생이 같은 팀에 속하는지 확인하는 연산이다.선생님이 M개의 연산을 수행할 수 있을 때 같은 팀 여부 확인 연산에 대해 연산 결과를 출력하는 프로그램을 작성하시오. 📌풀이경로 압축 방식의 서로소 집합 알고리즘 📌코드# 특정 원소가 속한 집합 찾기def find_parent(parent, x): # 루트 노드가 아니라면 루트 노드 찾을 때까지 재귀 호출 if parent[x] != x: p..
📌위상 정렬순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것ex: 선수 과목을 고려한 학습 순서 설정 진입 차수: 특정한 노드로 들어오는 간선의 개수 1. 진입차수가 0인 노드를 큐에 넣는다.2. 큐가 빌때까지 다음 과정 반복한다. - 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. - 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 📌코드from collections import deque# 노드의 개수, 간선의 개수 입력v, e = map(int, input().split())# 모든 노드 진입차수 0으로 초기화indegree = [0] * (v + 1)# 각 노드에 연결된..
📌신장 트리하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재 하지 않는 부분 그래프 📌크루스칼 알고리즘최소 신장 트리 알고리즘: 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘대표적인 최소 신장 트리 알고리즘이 크루스칼 알고리즘 가장 적은 비용으로 모든 노드 연결모든 간선에 대하여 정렬을 수행한 후 가장 거리가 짧은 간선부터 집합에 포함 1. 간선 데이터를 비용에 따라 오름차순 정렬2. 간선을 하나씩 확인하며 현재의 간선이 사이클 발생시키는지 확인 - 사이클 발생하지 않는 경우 최소 신장 트리에 포함 - 사이클 발생하는 경우 최소 신장 트리에 포함시키지 않음3. 모든 간선에 대하여 2번 과정 반복 📌코드# 특정 원소가 속한 집합 찾기def find_parent(..
📌서로소 집합을 활용한 사이클 판별서로소 집합은 무방향 그래프 내에서의 사이클 판별할 때 사용(방향 그래프 내에서의 사이클 판별은 DFS 사용) 1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다. - 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다 - 루트 노드가 서로 같다면 사이클이 발생한 것이다.2. 그래프에 포함되어 있는 모든 간선에 대해 1번을 반복한다. 📌코드# 특정 원소가 속한 집합 찾기def find_parent(parent, x): # 루트 노드가 아니라면 루트 노드 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return pare..
📌서로소 집합공통 원소가 없는 두 집합 📌서로소 집합 자료구조서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조union, find 2가지 연산union: 합집합, 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산find: 찾기, 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 구현 시 트리 자료구조 사용1. union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. - A와 B의 루트 노드 A', B'를 각각 찾는다. - A'를 B'의 부모 노드로 설정한다(B'가 A'를 가리키도록 한다.)2. 모든 union 연산을 처리할 때까지 1번 과정 반복한다. 📌기본적인 서로소 집합 알고리즘 소스코드# 특정 원소가 속한 집합을 찾기def find_parent(..
📌문제어떤 나라에 N개의 도시가 있다. 그리고 각 도시는 보내고자하는 메세지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메세지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면 그 사이 통로가 있어야 한다. 어느날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메세지를 보내고자 한다. 메세지는 도시 C에서 출발하여 각 도시 사이 설치된 통로를 거쳐 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 베세지를 받게 되는 도시의 개수는 총 몇개이며 도시들이 모두 메세지를 받는 데까지 걸리는 시간을 계산하시오. 📌풀이한 도시에서 다른 도시까지의 최단 거리 문제우선 순위 큐를 이용한 다..