SHA256
43 lines
1.7 KiB
Typst
43 lines
1.7 KiB
Typst
#import "연구실실습일지작성양식.typ": 실습일지
|
|
|
|
#실습일지(
|
|
소속대학: "공과대학",
|
|
소속학과: "컴퓨터소프트웨어학부",
|
|
학번: "2024062806",
|
|
성명: "주하진",
|
|
일시: "2026년 9월 11일 13시 부터 ~ 16시 까지",
|
|
내용: [
|
|
지난 시간에 이어서 트로미노 문제를 해결했습니다.
|
|
|
|
이것도 완전탐색 문제로 33위치 문제랑 거의 비슷한 문제입니다. 다만 33위치 문제는 모양이 단일했지만, 트로미노 문제는 모양이 최대 6가지가 존재합니다. (ㄴ자를 회전한 경우와 ㅡ자를 회전한 경우) 이것을 효율적으로 구하기 위해 2x2 윈도우랑 3x1, 1x3 윈도우를 사용하여 해결했습니다. 2x2 윈도우에서 블럭 하나씩 총 4개의 모양을 확인하고 3x1, 1x3 윈도우를 모두 사용하면 전체 경우의 수를 완전 탐색할 수 있습니다.
|
|
|
|
금 채굴하기 문제는 조금 어려웠습니다. 다만 $n$이 매우 작고 ($< 100$) $k$를 0부터 max of $n$까지 잡아도 시간초과가 나지 않겠다 싶어서 대략 $O(n^4)$으로 풀었습니다. 아마 최적화를 한다면 $O(n^3)$까지 줄일 수 있다고 생각합니다.
|
|
|
|
```rust
|
|
for i in 0..n {
|
|
for j in 0..n {
|
|
for ii in 0..20 {
|
|
let s = drill(&field, n, ii, i, j);
|
|
if s * m >= cost(ii) {
|
|
maxima = maxima.max(s);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
```
|
|
|
|
```rust
|
|
// in drill function
|
|
for i in 0..n {
|
|
for j in 0..n {
|
|
if (i as i64 - r as i64).abs() + (j as i64 - c as i64).abs() <= k {
|
|
s += field[i][j];
|
|
}
|
|
}
|
|
}
|
|
|
|
```
|
|
|
|
],
|
|
)
|