-
루트로 문제 뚫기
서론 수준급의 알고리즘 문제를 풀다 보면 다양한 장벽에 가로막히곤 합니다. 어려운 문제들 중에는 특히 쿼리형1의 문제가 많은데, 이런 문제들은 단순한 방법으로 답을 도출해내는 것은 쉽지만 시간 복잡도를 줄이는 데에 복잡한 자료구조가 요구되어 난이도가 매우 높아지는 경우가 많습니다. 이러한 문제들의 의도는 주로 특수한 형태의 트리2나 이분 탐색 등을 활용하여 $O(Q\log^K{N})$ 꼴의 시간 복잡도를 만들어내도록 하는 것이지만, 일부 문제의 경우 $O((N+Q)\sqrt{N})$과 같이 루트가 시간 복잡도에 포함되는 것이 정해인 경우도 있습니다. 대표적인 것이 이전에 소개한 바 있는 Mo’s...
-
프로그램의 메모리 사용량 측정 방법
안녕하세요? 오늘은 프로그램의 메모리 사용량을 측정할 수 있는 방법에 대해 알아보았습니다. 아래 코드들은 최적화 방지를 위해 -O0 옵션으로 컴파일 후 실행되었습니다. Indroduction 보통 온라인 저지 시스템에서의 채점 결과 중에는, MLT(Memory Limit Exceeded)가 포함되어 있습니다. 문제에서 주어진 메모리 제한을 초과할 경우 이러한 메시지가 뜨게 됩니다. 사실 대부분의 문제에서는 메모리를 꽤 넉넉하게 주기 때문에, 메모리 제한 초과는 특수한 상황이 아니라면 그리 자주 발생하는 편은 아닙니다. 재귀함수가 계속해서 호출된다거나, 큐가 계속 커진다거나 하는 상황에서 그나마 자주 발생하는 편이고,...
-
k번째 최소 컷 찾기
간선에 가중치가 있는 방향 그래프 $G=(V, E)$를 생각해 봅시다. 시작점 $s \in V$와 끝점 $t \in V$가 주어질 때, $s$와 $t$가 서로 다른 컴포넌트에 있게 되도록 몇 개의 간선을 지울 때, 지우는 간선의 가중치의 합을 최소화하는 문제를 우리는 최소 컷(minimum cut) 문제라고 부릅니다. 이 문제는 최대 유량 최소 컷 정리에 의해 최대 유량 문제로 변형되고, Dinic 알고리즘을 사용한다면 $O(V^2 E)$의 시간 복잡도에 해결할 수 있습니다. 또한, 최대 유량 알고리즘을 수행한 후 시작점 $s$에서 유량이 남아...
-
AntiVirus Oracle
서론 CONFidence CTF 2020 Teaser라는 대회에서 Angry Defender라는 문제가 나왔습니다. 해당 문제는 Windows Defender의 특성을 이용해서 문제의 답에 해당하는 Flag를 얻어내는 문제었는데, 이 방법이 흥미로워서 이번에 공유하게 되었습니다. 본론 AV Oracle이란? 일반적으로 보안에서 Oracle이라는 이름이 붙은 공격들은 서버가 원하는 정보를 알고 있고 서버와 Interactive하게 통신이 가능할 때 해당 정보의 일부를 유출시킬 수 있는 공격들입니다. 대표적으로 Padding oracle attack과 RSA LSB oracle attack이 있습니다. (공교롭게도 둘은 모두 암호학적 공격이네요.) AV Oracle은 일반적인 컴퓨터 환경에서 사용되는 Antivirus의...
-
JavaScript의 형변환
JavaScript만큼 프로그래머들이 농담 따먹기를 하는 프로그래밍 언어가 PHP 말고 있을까요? JavaScript의 매력이자 악명 높은 점이 타입의 유연성입니다. 변수를 선언할 때 타입을 지정할 필요가 없으며, 서로 타입이 다른 변수들끼리 연산을 해야 할 때 최대한 에러를 내지 않는 방향으로 진행이 됩니다. 이런 규칙을 통해 ![]+-*만 이용해서 0부터 1000까지 만들라는 이런 문제도 있습니다. 하지만 일반적으로 이런 변환 과정은 갸우뚱할 때가 많으며, 프로그래머 개그의 단골 소재이기도 합니다. 이 포스트에서는 형변환(coercion)에 깔려있는 법칙들을 설명하고자 합니다. Alexey Samoshkin님의 이 포스트에서 지대한...