본문 바로가기

코딩

 (11)
[Lua] 백준 27440 1로 만들기 3 간단한 BFS 문제이다. 사실 이 문제의 원본인 "1로 만들기" 는 다이나믹 프로그래밍 Well-known 문제인데, 이걸 BFS로 구현하는 게 더 빠르지 않을까 싶어서 구현해 보았다. 중간에 tbl이라는 테이블(루아의 자료 구조로, 파이썬의 딕셔너리와 비슷하다.) 에 메모이제이션을 하는 부분이 있는데, BFS를 하면서 디버깅 출력을 해 보니 같은 리스트가 q에 계속 push되는 것이 확인되어(무한루프는 아니었지만 상당히 반복 횟수가 많아 시간을 많이 잡아먹는 듯 했다.) 메모이제이션을 하면서 이미 push한 값은 다시 push하지 않도록 했다. (이렇게 하니 작동 속도가 상당히 빨라졌다.) "1로 만들기" 문제는 BFS 방식을 활용해 시간을 줄이지 않으면 Lua로는 풀 수가 없어서 BFS를 활용해서 풀..
[Lua] 백준 2003 수들의 합 2 예전에 풀려고 했을 때는 꽤 애먹었던 문제였는데, 다시 구현하니까 쉽게 풀렸던 문제. 여기서 핵심은 start와 endd가 같을 때에도 while문이 작동하도록 해서 한 개의 원소만 가리킬 수 있도록 하는 것이다. n,m=io.read("*n","*n") arr={} for i=1,n,1 do arr[i]=io.read("*n") end start,endd,sum,cnt=1,1,arr[1],0 while start
[Lua] 백준 14852 타일 채우기 3 분할할 수 없도록 1칸을 채우는 경우가 2가지, 2칸을 채우는 경우가 3가지, 3칸,4칸...을 채우는 경우도 전부 2가지이므로 An=2*Sn-1+2+An-2를 풀면 된다. dp={2,7} dp[0]=1 n=io.read("*n") for i=3,n,1 do dp[i]=(3*dp[i-1]+dp[i-2]-dp[i-3])%1000000007 end io.write(dp[n])

티스토리툴바