📑 문제🌱 아이디어버블소트의 특징을 활용하자! 위 문제는 C++ 버블 소트 코드를 제공한다. 전형적인 버블 소트 알고리즘이며 O(N^2)의 시간복잡도를 가진다입력으로 1  즉 , 위 문제는 버블 소트를 구현하는 문제가 아닌 버블 소트의 특징을 이용하는 문제이다.  결국 정렬하는 문제이다 버블 소트의 정렬 특징을 생각해 보자 오른쪽 -> 왼쪽으로 숫자가 이동할 때, 한 턴에 연속적으로 다수의 칸을 이동한다.왼쪽 으로 숫자가 이동할 때, 한 턴에 단 한 번만 이동한다. 위 특징을 봤을 때, 결국 버블 소트의 실행 횟수는 왼쪽  그렇다면 어떻게 구현할까? 해당 숫자와  입력된 위치(인덱스)를 저장하고, 한 번에 정렬 후 현재 숫자 위치(인덱스) - 원래 위치(인덱스)의 차를 구한다그중 가장 큰 차가 바로 ..

📑 문제 🌱 아이디어위 문제에서 친구가 된 순서의 정보를 차례차례 제공한다.그렇다면 단계마다 해당 친구가 속한 네트워크(집합)의 크기를 구하는 문제이다! 크게 생각해야 하는 점은 두 가지가 있다.1. 친구의 정보가 이름(문자열)으로 제공되는 점2. 친구 네트워크(집합)에 속한 크기를 구하는 방법. 1번의 경우는HashMap을 사용하여 key : 이름 -> value : 번호로 치환해서 유니온파인드 알고리즘을 실행하면 된다.당연히 해쉬맵에 이름이 있는지 판단해야 하고. 없다면 번호를 부여한다. 2번의 경우는유니온 파인드 알고리즘을 사용하고 그중 union 함수에서 두 노드의 부모노드가 다르다면? -> 서로 다른 노드임 -> 친구가 되었기 때문에 ans [부모노드] += ans [자식노드]로 업데이트 후..

📑 문제🌱 아이디어BFS탐색을 통해 맵밖으로 나가게 된 경우를 모듈러 연산으로 처리하자! 만약 도넛행성에 있다고 상상해 보자! 어떤 방향으로 쭉 직진하게 되었을 때 결국 제자리로 돌아올 것이다.즉 좌표  xy (0,0)에서 한 칸 더 위로 직진한다면 (0, N-1)이 되어야 한다. 이 조건은 동서남북 어디서나 동일하게 적용한다. 위 문제는 기존에 범위체크에서 배열밖 좌표로 이동하는 것을 막아주는 BFS가 아닌맵밖으로 나간다면 반대 방향으로 탐색하게 만들어야 한다. 모듈러 연산을 통해 위와 같은 효과를 얻을 수 있다. 예를 들어 N = 5 일 때 배열의 인덱스는 0, 1, 2, 3, 4 일 것이다 인덱스 5를 탐색하려고 할 때 5 %= N을 통해 다시 인덱스 0을 탐색하게 만들면 된다.🌱 코드 및 풀..

📑 문제🌱 아이디어최단거리를 구하고, 최단거리 루트의 경로 역추적을 통해 풀어보자! 최단거리 문제이다. 하지만 최단거리로 갈 때 바로 첫 노드를 출력하는 문제이다. 가령 1 → 5번 노드로 가야 한다면 여러 가지 루트 중 가장 최단 경로 1 → “3” → 4 → 5 일 때위 문제에서 요구하는 답은 "3"번 노드를 출력하는 게 조건이다. 즉 경로 역추적 알고리즘이 필요하다. 그리고 또 하나 i → j로 갈 때 바로 직행하는 방법도 있지만 이러한 루트는 최단루트가 아닐 수 있다.i → j ,  i → h → j ⇒ 직행루트 와 경유지가 있는 루트를 비교해야 한다결국 플로이드워셜 알고리즘을 사용하는 게 가장 좋아 보이는 문제이다.기본적인 플로이드 워셜 알고리즘을 구현하는 것은 어렵지 않았으나. 경로 역추적..

📑 문제🌱 아이디어분할정복을 이용한 행렬제곱 문제, 큰 문제를 작은 단위로 나눠서 풀어보자 분할 정복의 가장 기본적인 개념은 큰 문제를 작은 단위로 나눠서 푸는 것이다.. 예를 들면 N^8 은 N*N*N*N*N*N*N*N 이다. 즉 N을 8번 곱해야 한다.  분할 정복을 통해 작은 단위로 나눠서 bottom up 방식으로 푼다면  (((N^2)^2)^2) 3번만 연산하면 된다. 이는 O(logn)의 시간복잡도를 가지며 N^B, B가 클수록 좋은 성능을 보여준다.  그리고 행렬 A와 행렬 B를 곱한다면 A =1234 B =5678  A X B =1*5+2*71*6+2*83*5+4*73*5+4*8 위와 같이 행렬곱셈과 동시에 분할정복으로 작은 단위 ~ 큰 단위로 답을 도출해야 한다.🌱 코드 및 풀이 만..