여름 언덕에서 배운 것

📚 문제 각 자리가 숫자로만 이루어진 문자열 가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. ✔️ +보다 x를 먼저 계산하는 일반적인 방식과 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정 ✔️ 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어짐 📝 문제 해설 두 수 중 하나라도 1 이하인 경우 -> 더하기 두 수가 모두 2 이상 -> 곱하기 💻 코드 package greedy; import java.util.*; public class greedy08 { public static void main(String args[]){ S..

📚 문제 한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 모험가 길드장은 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹의 최댓값을 구하는 프로그램을 작성하시오. 예를 들어 N=5이고, 각 모험가의 공포도가 2 3 1 2 2과 같다고 가정하자. 이때, 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되면, 총 2개의 그룹을 만들 수 있다. 또한 ..

위상 정렬이란? 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 1) 진입차수가 0인 노드를 큐에 넣는다. 2) 큐가 빌 때까지의 다음의 과정을 반복한다. ⑴ 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. ⑵ 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 💡 진입차수란? 특정한 노드로 들어오는 간선의 개수를 의미 이때 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 다시 말해 큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것이다. 📍 알고리즘 동작 과정 step0. 진입차수가 0인 노드를 큐에 넣는다. 현재 노드 1의 진입차수만 0이기 때문에 큐에 노드 1만 삽입 step1. 먼저 큐에 들어 있는 노드..

서로소 집합 자료구조 : union과 find 2개의 연산으로 구성 1) union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인 ⑴ A와 B의 루트 노드 A', B'를 각각 찾는다. ⑵ A'를 B'의 부모 노드로 설정한다. 2) 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다. 예를 들어, 전체 집합 {1, 2, 3, 4, 5, 6}이 6개의 원소로 구성되어 있는 상황을 생각해보자. 이때 다음과 같은 4개의 union 연산이 주어져 있다. (union 1,4) (union 2,3) (union 2,4) (union 5,6) 이러한 union 연산들은 그래프 형태로 표현될 수도 있다. 각 원소는 그래프에서의 노드로 표현되고, '같은 집합에 속한다'는 정보를 담은 uni..