코딩/Lua (10) 썸네일형 리스트형 [Lua] 백준 23832 서로소 그래프 사실 이 문제는 구현이 핵심이 아니라서 루아가 아닌 언어여도 상관없다. Lua 코드블럭을 제대로 사용할 수 있게 될 때까지는 루아 코드는 안 올릴 것 같다. Phi(2) + Phi(3) .... Phi(N)을 구하면 된다. Jinhan814님 블로그를 보면 오일러 피 함수의 독특한 성질 + 조화수열 DP(?)를 이용해 푸셨다. 이해가 힘들어서 그냥 Euler's sieve를 사용했다. 누적합으로 O(2N)을 O(N)으로 만드는 간단한 최적화를 해줬다. n=io.read("*n")--Euler's sieve + Prefix sumphisum={}phisum[1]=0for i=2,n do if phisum[i]==nil then for j=1,(n//i) do if p.. [Lua] 백준 3117 YouTube (별해) 이 문제는 옛날부터 다른 풀이로도 풀 수 있을 거 같다는 생각을 어렴풋이 했었다. 태그를 보면 '자료 구조' , '희소 배열' 태그가 붙어있고, 이 문제는 희소 배열 기본 문제 중 하나다. 희소 배열은 결국 1,2,4,8....번 뒤의 값을 미리 저장해서 M값이 매우 클 때도 M번 뒤의 값을 빠르게 찾을 수 있는 알고리즘이다. M이 2의 거듭제곱이면 1번, 아니면 최대 logM 번만에 이동할 수 있고, 주로 사이클이 존재하는 그래프에서 간선 이동을 빠르게 처리하는 기능을 한다. 내 풀이에 비해 희소 배열을 구현하는 게 훨씬 쉽고 빠르긴 하지만, 2의 거듭제곱으로 이동한다는 아이디어 없이도 풀 수 있다는 점은 나름 차별화된다. 높은 티어의 한 유저분에게 "희소 배열을 사용하지 않고, 사이클을 저장해서" 풀.. [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를 활용해서 풀.. 이전 1 2 다음
