이동식 저장소

그래프의 노드에 자연수 번호가 붙여져 있다고 가정할 때, 그래프를 인접 행렬로 저장하려면 vector의 vector를 저장하거나 set의 vector를 저장해야 한다. 나는 중복을 제거하고 싶을 경우에만 뒤의 방법을 쓰고, 평소에는 거의 앞의 방법을 사용한다. 그런데 오늘 2-SAT - 4를 풀면서 조금 생각이 바뀌었다. 위가 vector, 아래가 vector를 사용한 코드이다. 분명 자료구조만 바꿨는데도 시간 차이가 크게 난다. 이쯤되면 중복 제거할 때도 set을 사용하지 않을 것 같다. vector에서도 $NlogN$ 시간에 중복을 제거할 수 있기 때문이다. // https://stackoverflow.com/questions/1041620/whats-the-most-efficient-way-to-e..

거의 대부분의 프로그래밍 언어에는 흔히 상수라고도 불리는 불변값을 선언하는 키워드가 있다. 예를 들어 C의 const, Java의 final 말이다. 이 글에서는 그러한 키워드를 const로 통칭하겠다. // Kotlin val a = 3 a = 4 // Compile error 그런데 이렇게 선언된 변수를 간혹 절대로 변하지 않는다고 오해하는 경우가 있다. 나조차도 가끔 그럴 때가 있다. 주로 C나 Java의 primitive type(int, double 등)을 많이 사용하는 경우 이런 생각을 하기 쉽다. 왜냐면 저런 값들은 실제로 값이 변하지 않기 때문이다. 그런데 객체지향 언어에서는 조금 다르다. 예를 들어 이런 코틀린 코드가 있다. data class Person(var name: String,..

계절학기를 대면수업할 줄은 몰랐는데.. 덕분에 매일 출근길 지하철을 타고 있다. 너무 덥다. 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차�� www.acmicpc.net 일방통행인 길을 따라 교차로를 지나가며 현금을 최대한 많이 인출하면서 레스토랑에 가야 한다. 만약 길이 일방통행이 아니었다면 실버 5 문제가 되었을 텐데.. 아쉽게도 유향 그래프이기 때문에 다른 방법을 생각해야 한다. 문제의 그림에서도 볼 수 있듯이 그래프에는 사이클이 존재할 수 있다. 사이클은 갈 수 있다면 가는 것이 무조건 이득이다. 돈을 얻거나 적..

2018년 3월 7일에 나는 첫 번째 BOJ 코드를 제출하였다. 당시에는 아마 C를 공부하려고 인터넷을 돌아다니다가 우연히 사이트를 발견했던 것 같다. 그 와중에 첫 제출이 골드1 실화? 하여간 문제 보는 눈이란.. 2년 4개월이 흘러, 2020년 7월 5일 바로 지금! BOJ 누적 1000문제를 달성하였다. 그동안 백준 사이트도 많이 변했지만, 내가 생각했을 때 가장 많이 변한 건 내가 아닌가 싶다. C 붙잡고 낑낑대던 새내기가 어느새 3학년이 되어 앱을 만들 수 있게 되었다. 1000번째 문제는 4176. 도미노였다. 한때 권태감에 빠져서 백준은 1000개까지만 풀자고 생각한 적도 있었는데, 지금은 다시 알고리즘이 재밌어졌다. 아마 앞으로도 한동안은 더 풀 것 같다. 어차피 알고리즘 스터디도 해야 하..

17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 �� www.acmicpc.net 쿼리 문제의 특징은 쿼리가 매우 많다는 점이다. 보통은 쿼리를 선형 시간보다 더 빠르게, 즉 로그 시간이나 상수 시간에 처리해야 한다. 이 문제 역시 쿼리의 수 Q가 20만, 합성 횟수 N이 50만으로 O(QN) 시간에 해결할 수 없다. 내가 지금까지 풀었던 쿼리 문제는 보통 쿼리를 로그 시간에 처리했다. 이번에도 로그 시..