[TIL] 2019-10-21

알고리즘

종만북

• 9.4 - 광학 문자 인식
  • 드디어 해결했다...

package main

import (
	"fmt"
	"math"

	"algorithm/pkg/scan"
)

var (
	m, q    int
	words   []string
	wordMap map[string]int
	T       [][]float64
	M       [][]float64
	cache   [][]float64
	choice  [][]int
	choice2 []string
	target  []int
)

func main() {
	sc := scan.New()

	m, q = sc.Int(), sc.Int()

	words = make([]string, m+1)
	wordMap = make(map[string]int)
	for wi := 1; wi <= m; wi++ {
		word := sc.String()
		words[wi] = word
		wordMap[word] = wi
	}

	B := make([]float64, m+1)
	for bi := 1; bi <= m; bi++ {
		B[bi] = math.Log(sc.Float64())
	}

	T = make([][]float64, m+1)
	for a := 1; a <= m; a++ {
		T[a] = make([]float64, m+1)
		for b := 1; b <= m; b++ {
			T[a][b] = math.Log(sc.Float64())
		}
	}

	T[0] = B

	M = make([][]float64, m+1)
	for a := 1; a <= m; a++ {
		M[a] = make([]float64, m+1)
		for b := 1; b <= m; b++ {
			M[a][b] = math.Log(sc.Float64())
		}
	}

	for qi := 0; qi < q; qi++ {
		tLen := sc.Int()
		target = make([]int, tLen)

		for ti := 0; ti < tLen; ti++ {
			word := sc.String()
			target[ti] = wordMap[word]
		}

		choice = make([][]int, m+1)
		cache = make([][]float64, m+1)
		for ci := 0; ci <= m; ci++ {
			tmp := make([]float64, tLen)
			tmp[0] = 1

			for ti := 1; ti < tLen; ti++ {
				copy(tmp[ti:], tmp[:ti])
			}

			cache[ci] = tmp
			choice[ci] = make([]int, tLen)
		}

		choice2 = make([]string, tLen)

		ocr(0, 0)
		fmt.Println(reconstruct(0, 0))
		fmt.Println(choice2)
	}
}

func ocr(prev, i int) float64 {
	if i == len(target) {
		return 0.0
	}

	ret := &cache[prev][i]
	if *ret < 0.5 {
		return *ret
	}

	*ret = -math.MaxFloat32

	for cur := 1; cur <= m; cur++ {
		calc := T[prev][cur] + M[cur][target[i]]
		cand := calc + ocr(cur, i+1)

		if *ret < cand {
			*ret = cand
			choice[prev][i] = cur
            
            // 이렇게 답을 구성하면 안되는 이유...
			// 이전 단어가 어떤건지는 상관 없이
			// i번째 단어가 업데이트 될 때마다 바뀌니까
			// 의미가 없네
			// 이전 단어가 a일때 다음 단어가 b가 나올 확률이 가장 높다고 해도
			// 이 코드에 의해 다른 단어, 즉 이전 단어가 b일때 다음 단어가 c가 나와도
			// 걔로 업데이트됨
			// 그러니 완벽한 문장을 구성할 수 없음
			choice2[i] = words[cur]
		}
	}

	return *ret
}

func reconstruct(prev, i int) string {
	if i == len(target) {
		return ""
	}

	choose := choice[prev][i]
	ret := words[choose]

	return ret + " " + reconstruct(choose, i+1)
}

일하다 느낀 것

역시 경험은 중요하다는걸 깨달았다. 급작스럽게 해결해야 될 일이 생겼는데, 경험이 있었더라면 차분하게 뚝딱뚝딱 짰겠지만 경험이 별로 없으니 고민하는 시간이 길어졌고, 또 시간이 촉박하다고 느끼니까 집중도 잘 되지 않았다. 이런 경험은 혼자 공부만 하면 얻을 수 없다. 확실한 데드라인에 따른 책임이 얼마나 정신을 압박하는지, 짧게 나마 느꼈다. 1시간정도 고민하다 해결책을 생각해내서 망정이었지, 그렇지 않았다면 지금도 계속 압박감을 느끼고 있었겠지.

아무튼 나름 잘 해결하고 퇴근한다. 내일 와서 마무리 조금 지으면 될 것 같다.😅

Coding Math

• 12. Edge Handling

물리를 프로그래밍함에 있어서 여러가지 테크닉을 알려주었다. 오늘은 영상을 보고 배운 내용을 간략히 노트로 정리해보고, 내일 구현해보자(졸림...😪)