이동식 저장소

계절학기를 대면수업할 줄은 몰랐는데.. 덕분에 매일 출근길 지하철을 타고 있다. 너무 덥다. 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개까지만 풀자고 생각한 적도 있었는데, 지금은 다시 알고리즘이 재밌어졌다. 아마 앞으로도 한동안은 더 풀 것 같다. 어차피 알고리즘 스터디도 해야 하..

몇 달 동안 프로젝트와 과제에 치여 살다가, 시험기간을 맞아 오랜만에 백준 문제를 풀었다. 분명 시험기간인데 평소보다 더 여유로운 건 뭐지..? 이것이 오픈북 효과인가? 3665번: 최종 순위 문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 �� www.acmicpc.net 작년 순위와, 올해 순위가 바뀐 팀의 쌍이 주어진다. 이때 올해 순위를 결정할 수 있을까? 순위라는 말에서 위상 정렬을 생각해 내야 한다. 기존에 주어진 순위에서 두 팀간의 순위 관계를 알 수 있고, 올해 변경된 순위 관계를 반영하여 위상 정렬을 하면 된다. 위상 정렬을 하기 위해 먼..

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 숫자의 배치 순서를 바꿔서 수를 최대로 만들어야 하는 문제이다. 무식하게 풀어보기 모든 가능한 $(i, j)$ 쌍을 바꿔 보는 방법을 생각해 볼 수 있다, 그러나 경우의 수가 최대 $\left(\begin{array}{c}7\\ 2\end{array}\right)^{10}=16,679,880,978,201$개나 있으므로 완전 탐색으로는 문제를 풀 수 없다. 그렇다면 기억해 보자 메모이제이션을 활용하여 중복 계산을 줄여 보자. 다음을 정의한다. $ans(n, dep) = dep$번 교환하여 얻은 수가 $n$일 때, 교환을 완료하여 얻..

이 문제의 대회 데이터가 공개되어 있으니 사용해 보자. 원문 제목은 labudovi이다. 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX www.acmicpc.net 얼음을 녹이면서 백조가 만날 수 있는지 확인해야 한다. 물과 인접한 얼음이 녹는다는 설명에서 BFS를 적용해야..