본문 바로가기

코딩/Lua

 (8)
[Lua] 백준 1949 우수 마을 그동안 알고리즘을 조금은 한 것 같다. 자력으로 푼 문제들이 여러 개 있지만 다 애드혹이라서 여기에는 올리지 않았다. 트리 DP를 여러 개 풀었더니 이제 트리 DP 문제는 자력으로 풀리는 것 같다. (라기엔 뉴스 전하기 문제도 자력으로 풀었던 걸 보면 그냥 내가 트리 DP랑 잘 맞나 보다.) 불(백준 4179번) 문제와 싸우느라 최근에는 많이 못 한 느낌이긴 하지만, 그래도 내 코드를 봐주는 사람이 있다는 걸 알게 되어서 기분이 좋다. 4179번은.. 데이터가 빡센 지 Lua로 계속 시간초과가 나길래 최적화를 열심히 하고(미로를 저장 안 했고, 재귀함수도 안 썼으며, 시간의 흐름을 기준으로 반복문을 돌려서 불이 붙은 시간을 무시하고 답을 구할 수 있었다.) 겨우겨우 996ms로 통과했는데, C++로 같은..
[Lua] 백준 19566 수열의 구간 평균 반딧불이 만든 문제고, 내가 다른 분의 풀이를 참고하지 않고 스스로 푼 문제들 중 난이도가 가장 높은 문제이다. 푼 지 꽤 오래되었고 푼 글도 올린 줄 알았는데 안 올라와있어서 지금 올린다. 이 문제를 풀려면 먼저 백준 2015번 수들의 합 4 문제의 풀이를 이해하고 있어야 한다. n,k=io.read("*n","*n") set={} set[0]=1 sum,ans=0,0 for i=1,n do a=io.read("*n") sum=sum+a if set[sum-k]~=nil then ans=ans+set[sum-k] end if set[sum]==nil then set[sum]=1 else set[sum]=set[sum]+1 end end io.write(ans) 이 코드에서 sum 변수는 i번째 숫자까지..
[Lua] 백준 25419 정수를 끝까지 외치자 문제를 풀었으면 문제 풀이의 논리와 배울 점을 기록해 두는 게 좋은데, 최근에 귀찮아서 글을 너무 안 올린 거 같다. 팰린드롬 게임(24553번) 문제를 풀 때 코드는 애드 혹으로 냈지만 처음 떠올린 발상은 DP였는데, 이 아이디어를 기반으로 문제를 풀어보려고 게임 이론+다이나믹 프로그래밍 태그의 문제들을 뒤져보다 이 문제를 발견했다. n,k=io.read("*n","*n") ban={} result={} while 1 do --외칠 수 없는 숫자를 외치는 사람은 진다 m=io.read("*n") if m==nil then break end ban[m]=1 result[m]=false end if ban[n]==nil then result[n]=true else result[n]=false end --n..
[Lua] 백준 1826 연료 채우기 문제집(1766번) 이후로 이런 일은 없을 줄 알았는데... 정해를 무시하고 내 방식대로 하겠다고 깝치다가 틀리거나 시간초과를 받은 게 너무 많아서 66번의 제출 끝에 맞았습니다!! 를 받았다. (참고로, 정해 무시하고 내 방식대로 계속 코드 제출하다가 맞은 건 색종이 붙이기라는 문제 뿐이고, 이마저도 그냥 백트래킹만 한 게 아니라 경로 저장까지 해서 중복되는 경우를 없애서 확실히 맞을 거 같은 코드는 시간초과가 났고, 그 코드에서 함수 호출 횟수를 재서 특정 값을 초과하면 그냥 지금까지 계산한 결과를 반환하는 코드를 냈더니 932ms로 간신히 통과했다. 답에 해당하는 경우는 빨리 나오는데 모든 경우의 수를 다 계산하려면 많은 시간이 걸리는 문제였던 것으로 추정된다. 모든 경우의 수를 세려면 함수를 19..
[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])

티스토리툴바