📑 문제 🌱 아이디어BFS로 각 섬에 번호를 부여하고, 모든 섬을 연결하는 다리잇기(MST)로 구현하자 2차원 평면 상 섬과 바다가 입력으로 주어지고, 다리를 연결해서 모든 섬을 연결하려고 한다.다리는 가장 짧게 연결해야 한다. 즉 모든 섬을 최소비용으로 모두 잇는다면 = 최소스패닝임을 유추해야 풀 수 있다. 아래와 같은 3단계를 거쳐서 구현했다. 1. 모든 섬을 탐색하고 번호를 부여한다 그래야 A -> B를 특정할 수 있다.2. A -> B가 직선으로 장애물 없이 다리를 이을 수 있는지 판단 후 우선순위큐에 시작노드, 목표노드, 비용을 입력하기3. 크루스칼알고리즘으로 모든 섬을 잇기 맵의 크기, 섬의 개수가 매우 작다, 시간초과를 걱정하는 것보다 차근차근 구현에 집중하는 게 좋은 문제인 것 같다!?..

📑 문제🌱 아이디어이분매칭의 아주 살짝 응용 버전?, 이분매칭의 특징을 알면 풀 수 있다. 아마 기본 열혈강호 문제를 풀고 이 문제를 푸는 사람이 많을 것 같다. 기본적인 네트워크 플로우, 이분매칭은 1 대 1 매칭이 디폴트이지만 이 문제에서는 1 대 2 매칭까지 가능하다.즉 사람 한 명이 두 가지 일을 할 수 있다. 가장 처음 사람마다 몇 개의 일을 점유했는지 카운트하는 배열을 생성하고 관리하려 했지만 실패했다. 하지만 이분매칭의 메커니즘을 자세히 보게 되면이분매칭 시 한 사람에 대해 한번만 dfs 함수를 호출하는데 => 1 : 1 매칭, 사실 dfs호출을 여러 번 하는 만큼 1 대 N 매칭을 할 수 있다. 🌱 코드 및 풀이 answer 🌱 느낀 점 기본 DFS 이용한 이분매칭은 시간이 오래 걸..

📑 문제 🌱 아이디어DP 문제처럼 생긴 그리디 문제.... 결국 알고리즘 분류 보고 풀었다.. 이 문제에서 생각해야 하는 부분은 2가지 정도 있다. 1. A메뉴, B메뉴를 어떤 기준으로 선택할 것 인지?2. 5000원 메뉴인 A메뉴를 돈이 부족해 선택을 하지 못할 때. [1번 경우]다른 그리디 문제는 정렬 시 데이터에서 하나의 기준을 잡아 정렬하는 경우가 많다.위 문제는 정렬의 기준을 (A메뉴 - B메뉴)의 차이를 기준으로 내림차순으로 정렬한다 ex) 1000 999 보다 10 1 이 우선순위가 되어야 한다. [2번 경우]1번 경우에서 5천 원 메뉴를 선택하다 보면 나머지 날은 밥을 먹지 못하는 경우가 생길 수도 있다.위 경우를 방지하기 위해 M - 5000 >= 남은 요소 * 1000으로 위 상황을..

📑 문제🌱 아이디어Xφ(X) = N , X의 범위는 N의 약수이다. 풀기 전 가장 크게 고민했던 점은 한 가지이다. X를 어떻게 찾아야 하는가이다.당연하게도 X는 N이하 일 것이다. 하지만 N이 1,000,000,000 경우 탐색범위가 커서, 시간초과가 날것이다 첫 번째 시도는 정수 'X'를 이분탐색으로 찾는 것이다. 물론 X마다 오일러의 피 수가 규칙적이지 않아서, 실패했다. 두 번째는 시도는 A * B = N이라면 -> 결국 A, B는 N의 약수이다. 라는 아이디어로 시작했다.당연하게도 두 수를 곱해서 N 이 되려면 두 수는 N의 약수일 것이다.  약수를 구할 때 제곱근까지만 탐색하여. O(logn)만큼 최적화하고X의 탐색범위를 N의 약수로 획기적으로 줄이고 오일러의 피함수 알고리즘으로 계산하여조..

📑 문제🌱 아이디어숫자 정렬이 아닌 사전순(문자열) 정렬을 사용하자 "큰 수"의 기준이 아닌 사전순 정렬을 사용한다. 9, 30 두 숫자가 있다. 두 수를 조합하여 만들 수 있는 가장 큰 수는930이다. 즉 문자열 정렬을 통해 가장 뒤서는 순(30, 9)부터 숫자를 합치며 풀면 된다. 하지만 하나의 반례가 있다. 3,30 두 숫자가 있다. 두 수를 조합하여 만들 수 있는 가장 큰 수는 330이다.하지만 문자열 정렬 시 가장 뒤서는 번호가 30이 된다 (3,30) 위처럼 출력 시 303이라는 숫자가 만들어진다. 이미 정렬된 문자열에서 앞의 숫자 '3', '3'0 같을 경우 330, 303이 큰지 판단하고, 결괏값에 따라 문자열을 서로 변경해 주는 형식으로 풀면 된다. 입력 값으로 1,000,000,00..