📑 문제🌱 아이디어분할정복을 이용한 행렬제곱 문제, 큰 문제를 작은 단위로 나눠서 풀어보자 분할 정복의 가장 기본적인 개념은 큰 문제를 작은 단위로 나눠서 푸는 것이다.. 예를 들면 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 위와 같이 행렬곱셈과 동시에 분할정복으로 작은 단위 ~ 큰 단위로 답을 도출해야 한다.🌱 코드 및 풀이 만..

📑 문제🌱 아이디어"시간이 되돌아가는 경우" -> 만약 음수 사이클이 존재한다면 무한히 시간을 되돌릴 수 있다즉 그래프 내 음수 사이클을 판별하기 위해 벨만포드 알고리즘을 사용해야 한다! 벨만포드 알고리즘은 최단거리를 구하는 알고리즘입니다. 음수 사이클이 존재한다면 계속 최단거리가 업데이트된다는 특징이 있기 때문에이러한 특징을 바탕으로 밸 만 포드 알고리즘 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내려갈 수 있..