seungineer

다익스트라로 최단 거리를 구하는 방식에서 경로 정보를 추가하는 로직! 11779번: 최소비용 구하기 2 boj.ma 다익스트라 알고리즘은 ‘특정 시작 지점’에서 ‘어떤 마지막 지점’으로 최소 비용으로 이동할 때의 '최소 비용'을 구할 수 있는 알고리즘이다. 그렇다면 경로 정보를 어떻게 추가할 수 있을까?다익스트라에서 heap queue를 pop 했을 때 나오는 정보는 최단 거리 관련 정보라고 할 수 있다. 즉, 유의미한 정보이다. 여기에 경로 정보가 포함되도록 해야 한다.path = [st]hq.heappush(qu, [0, st, path])while qu: 해당 코드를 보면 path 정보가 heap queue에 포함되는 것을 알 수 있다. 다익스트라 알고리즘을 위한 첫 heap queue부터 경로 정..

부분 수열 후보군의 '범위'를 최대한 넓게 갖도록 욕심부리는 문제이다.  30805번: 사전 순 최대 공통 부분 수열 boj.ma 문제 요약수열 A와 수열 B가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하여야 한다. 여기서 사전 순에 대한 정의는 문제에서 내린다. 정리하면, 여러 부분 수열들 중에서 1️⃣ 가장 index가 낮은 수가 큰 것이 사전 순으로 나중이다. 만약 이 값이 같다면 2️⃣ 그 다음 index 값을 순서대로 비교하여 큰 수가 사전 순으로 나중이다. 마지막으로 3️⃣ 부분 수열의 길이가 더 긴 것이 사전 순으로 나중이다.요약하면 부분 수열 중에서 큰 수가 많은 것이 사전 순으로 나중이다! 문제를 풀 때도 이 관점에서 생각해보면 큰 수부터 찾아야 한다는 감이 온다. ..

2차원 배열 내 수를 특정 형태에 맞게 회전시키는 로직을 for문과 while문을 적절히 활용하여야 하는 문제이다. 17144번: 미세먼지 안녕! boj.ma문제요약숫자로 표현된 먼지들은 사방으로 퍼지며 그 크기가 퍼진 만큼 줄어든다. 또한, 숫자 -1로 표현된 공기 청정기로 먼지가 들어가면 해당 먼지는 사라지게 된다. 공기 청정기가 작동하여 먼지의 위치를 이동 시키는 특정 패턴으로 정해져 있다. 몇 달 전에 풀어보려고 시도하였으나 실패했었던 문제이다. 실패의 원인은 공기청정기에 의해서 먼지가 이동하는 것을 어떻게 구현해야 할지 감이 오지 않았기 때문이다. 공기청정기에 의해서 먼지가 어떻게 움직이게 되는지가 해당 문제의 핵심이라고 할 수 있다. 무조건 공기청정기에 의해 순환 기류가 형성된다.문제 조건을 ..

‘flag를 어디에 세울 것인지’에 따라 시간 복잡도가 N의 제곱만큼 차이가 났다. 현재 문제에서 N은 최대 100이므로 TLE가 발생하는지 안 하는지 차이를 내는 중요한 요인이었다. 2638번: 치즈 boj.ma문제 요약숫자 1로 표현된 치즈가 몇 번의 연산 후에 모두 녹을지 구하는 문제이다. 치즈(숫자 1)는 주변에 숫자 0이 2개 이상 있는 경우 해당 연산에서 녹게 된다. 다만, 숫자 0 중 치즈에 둘러싸인 것은 제외한다는 조건이 있어 다소 까다롭다.1트: counting되면 안 되는 영역을 표시한다숫자 1이 모든 숫자 0과 맞닿는 경우를 센다면 쉬운 문제였겠지만, 숫자 1로 만들어진 영역 내에 포함된 숫자 0은 counting 하지 않아야 하여 까다로운 문제가 되었다.숫자 1로 만들어진 영역 내의..