tsi03136   5일 전

long long 으로 반복제곱할 횟수의 크기를 입력받았습니다.

[0] = x^1, [1] = X^2, [2] = X^4, X^8, X^16, X^32 ... [N-1] = X^(2^N) 을 반복하며 배열에 저장해 둡니다. 

그리고 다음은 계산에 적용한 방법입니다.

제곱해야 할 특정 값이 들어왔을 경우 ex) 1932

비트 연산을 위해  1932 를 0111 1000 1100 으로 인식합니다.

0001부터 0010 => 0100 => 1000 ... 반복하며 1932를 구성하는 비트를 순회합니다.

첫 번째로 0100를 찾으면 log2(4) = 2, 첫번째로 곱하는 것이기 때문에 배열 2번째에 저장된 행렬값을 [1,1,1,... ,1] 에 곱합니다.

다음으로 1000을 찾으면 log2(8) = 3, 배열 3번째에 저장된 행렬값을 기존 값에 곱합니다.

1932는 각 자리 비트들이 더해져서 나온 값이지만 이 문제는 1932번 곱해야하기 때문에 이런 식으로 풀었습니다.

따라서 Big-O(log2(N)) 의 시간 복잡도를 가지는데

문제는 채점을 시작하자 마자 틀립니다.

https://matrixcalc.org/ko/#%7B... 행렬 계산 사이트를 통해 여러 케이스를 시도해보았는데 모두 문제 없어서

특이한 테스트 케이스가 입력되어있는 것 같은데 예측이 되지 않습니다....

혹시 짐작 가시는 분이 계시면 알려주시면 정말 정말 감사하겠습니다....!!!

slah007   5일 전

statechange의 업데이트는 %2가 아닌 statechange = 1-statechange로 쓰는 것이 편합니다.

44~47줄이 예외를 찾기 아주 까다로운 상황을 만들어냅니다. arr1[i][j]는 이미 0으로 초기화했으니 앞의 조건은 의미가 없고, 뒤의 마지막으로 계산한 arr1[1-state][i][j] == 0만을 검사하는데 이것이 0이라고 곱셈 후 arr1[i][j]를 바로 결정할 수는 없습니다. 초기화 문제는 arr1이 0인지가 아닌 현재 사용하는 비트가 최초인지를 검사하도록 해야 합니다. (또는 맨 처음에만 arr1을 단위행렬로 초기화하면 됩니다)

지금은 아마 문제없긴 한데 38줄과 같이 실수형을 사용하는 log, pow 등을 int에 바로 대입하면 +-1 정도 오차가 생기기 쉽습니다. 어차피 bit<<=1당 log ++이므로 bit와 log를 따로 업데이트하거나 아예 bit = 1LL << log로 정수를 통해 계산하는게 좋습니다.

tsi03136   18시간 전

@slah007

답변해주셔서 무척 감사드립니다!!

고민 끝에 질문을 올렸는데 올리고 다시 시도해보다가 코딩 실수를 발견하고 문제 해결을 할 수 있었습니다....

statechange = 1-statechange 팁 무척 감사합니다! 앞으로 직관적으로 보일 수 있게끔 이 방식을 사용하겠습니다.

지저분한 코드를 바로 올려서 죄송합니다.

비트가 최초인지 검사하는 것

실수형을 사용하는 log, pow 등을 int에 바로 대입하면 +-1 정도 오차

이 부분은 명심하도록 하겠습니다!!

다시금 감사드립니다~~!!


혹시 필요하신 분이 계실까봐 수정한 코드도 올리도록 하겠습니다.

댓글을 작성하려면 로그인해야 합니다.