본문 바로가기

코딩

 (11)
PIMM 알고리즘 대회 후기 내가 가진 뱃지들 중, 소유자가 1000명보다 작은 뱃지들을 모아봤다. 올해 얻은 뱃지들이 희귀도가 높은 느낌이다. 사실 이 대회에 참여한 건 상반기 대회에서 지급한 '양말대와 핌파티' 뱃지가 마음에 들어서였는데, 비슷하게 생긴 뱃지가 나올 것이라는 예상은 빗나갔지만 그래도 내가 가지고 있던 뱃지들이랑 다른 느낌이고 받은 사람도 별로 없어서 결과적으론 나쁘지 않다. 뱃지를 받은 사람이 별로 없는 이유는, 높은 난이도 때문이었던 것 같다. 보통 A번은 날먹 문제로 나오는데 이번엔 그렇지 않았다. A번인 만큼 브론즈 난이도의 쉬운 문제였지만 거저 주는 문제는 아니었어서 A번만 풀고 뱃지를 받아가던 사람들이 뱃지를 받지 못했고, 받은 사람 수가 크게 줄어든 것 같다. 물론, 대회가 어렵기도 했다. 상반기 대회..
월간 향유회 8월 오프 대회 후기 대회 끝나고 찍은 사진이다. 내가 누군지 굳이 말하지 않아도, 혼자 어색하게 사진을 찍은 사람 한 명을 고르면 바로 찾을 수 있다. PS를 제대로 시작한 건 올해 2024년인 거 같고, 나에게 있어 첫 오프라인 대회였기에 의의가 컸던 거 같다. 알고리즘 그 자체를 정말 좋아하는 나지만, Competitive Programming에 쥐약인 스타일이라 그동안 대회에서 골드 이상 문제를 푼 적이 없었는데, (기존에 푼 가장 어려운 문제는 미적확통컵에서 푼 실버2 문제였다.) 난이도가 매겨지고 보니 골드5를 2문제나 풀었어서 놀랐던 기억이 있다. 현장에서 꼴지(19위)를 하기도 했고, 내가 푼 3문제 (A, C, E) 모두 코드가 굉장히 짧은 편이었기에 그냥 거저 주는 문제만 풀었다 생각했고, 0솔이 아니라는 ..
[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번째 숫자까지..
[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] 백준 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(..

티스토리툴바