최적화 - 3중 for문을 쓰지 않기 위해 나온 테크닉, flattening the state space

2025년 상반기 오전 2번 문제 개구리의 여행 문제를 풀다 보니 계속 시간초과가 나는 문제가 발생했다.이러한 시간문제에 맞닥뜨리게 되니 자연스레 최적화에 관심이 갔다. 최적화의 방법 중 중첩 for문을 최대한 줄이는 방법이 하나 있더라. 원래1. row2. col3. jumpPower 위 세 변수에 대해 각각 for문을 돌며 3차원 행렬을 관리해야 한다. 근데 Dijkstra 알고리즘의 경우 노드라는 하나의 값에 대한 최단 거리를 계산하다 보니 이러한 하나의 state 값으로 만들어 줄 수 있다고 한다. 그래서 다음과 같이 인덱스를 "펴는" 걸 생각하게 된다.2D 배열을 1D로 변환할 때 row * width + col 같은 걸 사용한다.거기에 추가적인 차원이 더 필요하다면 곱해주는 계수를 하나 더 ..
알고리즘/Team Notes 2025. 6. 9. 11:23
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/06   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
글 보관함