📑 문제🌱 아이디어여행계획이 주어질 때 A -> B 도시로 갈 수 있는 경로가 있는지 판단하는 문제! 우리가 만약 A에서 B 도시로 이동해야 한다면 두 가지 경우가 있을 것이다. 1. A -> B (직행 경로)2. A -> C -> B (경유 경로) 즉 직행을 못하는 경우는 어떠한 "도시"를 경유해서 목적지로 도착해야 한다. 이런 경우 경유하는 도시를 기준으로최단거리를 구하는 알고리즘인 플로이드-워셜 알고리즘을 사용하면 쉽게 풀 수 있다. 하지만 이 문제는 최단거리를 구할 필요가 없고 갈 수 있는 도시인지를 판단만 하면 되기 때문에 살짝(?)만응용해서 플로이드-워셜 알고리즘을 구현하면 풀 수 있다.🌱 코드 및 풀이 플로이드 워셜 알고리즘에서 최단거리가 아닌 "경로존재 여부"를 판단하는 것 이기 때문..

📑 문제🌱 아이디어"시간이 되돌아가는 경우" -> 만약 음수 사이클이 존재한다면 무한히 시간을 되돌릴 수 있다즉 그래프 내 음수 사이클을 판별하기 위해 벨만포드 알고리즘을 사용해야 한다! 벨만포드 알고리즘은 최단거리를 구하는 알고리즘입니다. 음수 사이클이 존재한다면 계속 최단거리가 업데이트된다는 특징이 있기 때문에이러한 특징을 바탕으로 밸 만 포드 알고리즘 N번까지 실행했을 때 마지막까지 최단거리가 업데이트된다면 음의 사이클이 존재한다는 것을 증명할 수 있다.   위 그래프는 예제 입력 2번을 토대로 만든 그래프와 가중치이다. 밸만포드 알고리즘을 N번까지 실행해 보자1회 차 : 1(-2) / 2(4) / 3(0)2회 차 : 1(-4) / 2(2) / 3(-2)3회 차 : 1(-6) / 2(0) / 3..

📑 문제🌱 아이디어"검을 먹는 경우"와 "검을 먹지 않는 경우"를 구하고 제한시간에 맞는 경우를 출력하자. 기본적인 BFS 알고리즘을 사용하지만 검을 먹는 경우 or 검을 먹지 않는 경우를 분리해서 풀어야 한다.그러기 위해선 BFS 알고리즘을 실행해서 검을 먹을 수 있는지에 대한 여부를 확인하고 먹었다면먹은 위치에서 목표가 있는 위치까지 벽을 부술 수 있기 때문에(장애물이 없다) 맨해튼 거리 로 최단 거리를 구해 더해주면 된다. Way1, Way2 는 도착할 수 없는 경우도 있기 때문에 Max 값으로 설정 후 진행한다Way1 = 검을 먹지 않는 경우 -> 기본 BFS으로 목적지까지 소요시간Way2 = 검을 먹은 경우 -> 검을 먹기까지  소요시간 + 맨해튼거리(한 칸 당 한 시간) 검을 먹기만 한다면..

📑 문제🌱 아이디어LCD에 표시된 숫자의 규칙을 찾고 모듈식으로 조립해서 출력하자! 하나하나 N의 크기에 맞춰서 출력하는 것보다 숫자를 구성하는 규칙을 찾고 가로줄을 기준으로 출력을 하는 게 효율적이다. 예제 출력 1을 보면 숫자를 구성하는 모듈 또는 패턴이 보인다 가장 위 부터 오른쪽 바, 왼쪽 바, 양쪽 바, 공백, 하단 바 총 5가지의 모듈이 필요하다.이 경우는 N = 2인 경우다 당연히 N 이 증가되면 그거에 맞게 가로길이는 길어질 것이다. 예를 들어하단 바는 N = 3 일 때 " --- " 이런 형태의 모듈이 요구된다. 위의 예제 출력을 보면 이런 패턴으로 숫자가 출력되는 것을 알 수 있다. 즉 해당 모듈을 이용하여 해당 숫자를 표현하기 위해  행마다 맞는 모듈을 넣고 다음 행으로 넘어가야 ..

📑 문제🌱 아이디어메모리 제한 4MB이다, 즉 메모리 초과된다면 불필요한 메모리는 줄여야 한다. 처음 풀었을 때 N = 100,000까지 모든 입력을 배열에 받고 저장했다... 그러다 보니 메모리 초과가 나서 틀렸다이 문제는 사실 입력을 저장할 필요 없다 입력되면 -> dp로 처리한다 이를 N번 반복하면 된다 이 문제는 다이내믹 프로그래밍 알고리즘을 사용한다 즉 우리는 3가지 경우에 대한 점화식을 세우면 된다!   최댓값 구하는 경우j =1 , 점화식 = dp1[1] = max(dp1[1], dp1[2])+ n1j =3 , 점화식 = dp1[3] = max(dp1[3], dp1[2])+ n3j =2 , 점화식 = dp1[2] = max(dp[1] , max(dp[2], dp[3])+ n2내려갈 수 있..