본문 바로가기

전체 글

 (15)
Lua를 접어야 할 지 고민을 하고 있었다 백준 1766번 문제가 안 풀리길래 Lua가 느려서 그런 줄 알았는데... 알고 보니 그냥 내가 우선순위 큐 구현을 잘못한 거였다..(dlrgus041님의 코드를 참고했다.) 근데 내가 컴공을 갈 것도 아닌데 언제까지 Lua로 PS를 할 지, 만약 다른 언어를 한다면 C++을 해볼 지 Rust를 해볼 지가 고민이다. 취미로 PS를 하는 게 맞나 하는 생각도 든다.
[Lua] 백준 13913 숨바꼭질 4 "숨바꼭질 3" 문제에서 간단한 역추적 코드만 넣어주면 되는 문제이다. backtbl에 경로를 저장하고 tracker라는 이름의 변수를 갱신하면서 경로를 저장하고, 저장된 경로를 출력해주면 된다. 나는 51퍼랑 86퍼에서 "틀렸습니다"를 받았는데, n=0인 경우랑 n=k=0인 경우의 예외 처리를 하지 않아서였다... q={} track={} q.first,q.last=1,2 local MAX=100001 function pushFirst(value) q.first=q.first-1 q[q.first]=value end function popFirst() local value=q[q.first] q[q.first]=nil q.first=q.first+1 return value end n,k=io.read(..
[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])

티스토리툴바