📑 문제🌱 아이디어좌표 (0,0)과 (x, y)의 기울기를 구하고, 기울기가 같은 풍선을 세어보자 풍선의 개수는  N 대충 봐도 모든 좌표를 탐색하는 건 불가능해 보인다    문제에서는 0,0에서 화살을 날려 -> (x, y) 풍선을 맞춰 터트릴 수 있다고 한다. 최대한 많은 풍선을 터트리려면 어떻게 해야 할까? 0,0 -> 1,2로 화살을 쐈다면 자연스럽게 화살의 이동 방향에 존재하는 풍선들은 터질 것이다. 이것을 그림으로 그려보면 위 처럼 된다.즉 풍선 A -> 풍선 B를 잇는 직선의 기울기를 구하고, 같은 기울기에 속한 풍선의 개수를 세면 된다! 기울기 M을 구하는 공식은 M = (y2-y1) /( x2-x1)이다, 그 후 기약분수로 표현하기 위해 최대공약수 도 구해서 나눠주면 된다 🌱 코드 ..

📑 문제 🌱 아이디어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으로 위 상황을..

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