📑 문제🌱 아이디어낮, 밤 관련 BFS를 각각 구현하고, "영구적인 저체온증 환자"가 생기는 조건을 찾아보자. 위 문제의 키포인트는 볼드체로 잘 강조되어 있다. 낮, 밤을 나눠서 생각해 보자 - 낮"체온 회복 과정은 낮 사이 충분히 많이 반복될 수 있다."이 뜻은 다른 사람이 체온이 회복이 된다면, 그 주변 사람도 연쇄적으로 체온 회복이 가능하다는 뜻이다즉, 낮 BFS를 통해 단 한 번으로 가능한 모든 사람을 회복시켜야 한다. - 밤K명만큼 밤에는 저체온증 환자가 발생한다 단 "최악의 경우"로 발생한다.이 문제에서 최악의 경우란 낮이 되어도 회복이 불가능한 저체온증 환자이다. 그렇다면 어떤 조건에서 정상체온 환자가영구적인 저체온증으로 변경되는지 캐치해야 한다. 가장 먼저, 낮에서 체온을 회복할 때 정..

📑 문제 🌱 아이디어위 문제에서 친구가 된 순서의 정보를 차례차례 제공한다.그렇다면 단계마다 해당 친구가 속한 네트워크(집합)의 크기를 구하는 문제이다! 크게 생각해야 하는 점은 두 가지가 있다.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을 탐색하게 만들면 된다.🌱 코드 및 풀..

📑 문제🌱 아이디어위 문제에서 말하는 “오등큰수” 는 NGF(i) 일 때 자기 자신 오른쪽에 있는 숫자 중 자신보다 많은등장 횟수를 가지는 숫자 중 가장 왼쪽에 있는 수이다. 예를 들어보자! ex.) 1 1 1 1 3 1 1인 경우 NGF(3) = 1이다. 반대로 NGF(1) = -1이다, 1보다 큰 등장 횟수가 없기 때문이다.그리고 출력은 입력된 순서를 지켜야 하기 때문에 -1 -1 -1 -1 1 -1 -1이다. 위 문제는 스택을 사용해야 한다. 내가 스택을 사용해야겠다고 유추한 근거는 두 가지이다 1. 답을 정하는 조건이 자신의 오른쪽 즉 방향이 정해져 있다.2. N ≤ 1,000,000이며 이는 O(N^2)를 가지는 단순한 구조로 구현 불가능 -> 시간 초과 발생 결론은 효율적인 구조 ex.) ..

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