이거는 시간초과와 무관하게 spars table 자체가 제대로 채워지지 않아요 (시간초과는 무한루프 때문에 날 것 같아요)
table[i][j] 를 채우기 위해서는 table[1~N][j-1] 을 모두 알아야 (table[i][j-1]이 뭐가 나올지 모르기 때문에) 하는데 table[1~N][j-1]을 채우기 전에 table[i][j]를 채우려한다면
table[ table[i][j-1] ][j-1] 이 아직 채워지지 않은 쓰레기 값이기에 제대로 채워지지 않아요
그래서 안쪽 루프에 1~N을 먼저 돌리고 바깥 루프로 1~logN 번 루프를 돌린답니다
unta 1년 전
LCA 테이블을 완성하기 위해서 꽤 큰 이차원 배열을 순회합니다.
그런데 이 정도로 크기가 커질 경우 순회하는 시간이 순회 순서에 영향을 받게 됩니다.
이는 컴퓨터 메모리의 지역성(locality)와 관련이 있는데, 물리적으로 가까운 곳의 메모리를 더 빨리 참조할 수 있게 됩니다.
일반적으로는 행과 열 중 열을 먼저 순회하는 Row-Major 순회 방법이 더 빠른데, 본 문제에서는 Col-Major 순회 시에만 통과가 됩니다.
LCA와 무관하게 같은 크기의 배열을 순회할 때는 Row-Major로 순회 시가 더 빨랐습니다.
LCA 를 생성할 때 [table[i][j - 1]] 를 참조하는 것이 이와 관련이 있을까요?
감사합니다.
맞았습니다: 54952235번 소스 코드 (acmicpc.net)
시간 초: 54953254번 소스 코드 (acmicpc.net)