📑 문제🌱 아이디어순열과 중복순열을 3차원 배열을 컨트롤해 보자! 문제를 접하고 나서, 3차원 배열의 미로 찾기는 이미 몇 번 해보았기 때문에 어렵지 않았다.가장 고민했던 점은 어떻게 최적의 3차원 미로를 만드냐였다... 그래서 순열과 중복순열로 배열을 컨트롤할 수 있는 파라미터를 만드려고 했다 중복순열은 배열 한 층을 90도, 180도,  270도를 핸들링할 때 사용했고당연하게도 인덱스가 겹치면 안 되기 때문에 순열은 3차원 배열의 층을 조립할 때 사용했다 순열, 중복순열을 구하고 배열을 핸들링해도 시간초과가 나지 않는다고 확신하고 구현했다. 먼저 중복 순열, 순열 구하고2중 for문으로 각각의 각도에서 배열의 층을 쌓는 방식으로 모든 3차원 배열의 경우의 수를 체크했다.만든 큐브마다 BFS로 미로..

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