본문 바로가기

전체 글

 (9)
[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번째 숫자까지..
[Rust] 백준 10250 ACM 호텔 use std::io; use std::io::stdin; use std::io::Read; fn main() { let mut n = String::new(); stdin().read_line(&mut n).unwrap(); let n: usize = n.trim().parse().expect("Fail"); let mut input = String::new(); //입력 받는 부분 아님 io::stdin().read_to_string(&mut input).unwrap(); let mut inp = input.split_ascii_whitespace().map(str::parse).flatten(); for _ in 0..n { let h: i32 = inp.next().unwrap(); let w: ..
[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를 접어야 할 지 고민을 하고 있었다 백준 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

티스토리툴바