BOJ 2671 잠수함 식별 ㅎㅇ! 오랜만에 돌아왔다. 오늘의 문제는 KOI 1996의 중등 2번이자 고등 1번인, 잠수함 식별이다. 풀이법은 양심에 찔리지만 간단한 풀이와 정직하지만 귀찮은 풀이로 총 두 가지 풀이를 소개하고자 한다. 두 풀이의 차이점은 단순히 구현 방식의 차이일 뿐, 기본적 원리의 차이는 없다. 우선, 문자열의 길이가 길지 않아서 백트래킹으로 AC를 받아낼 수 있을지는 모르겠다.
BOJ 13512 트리와 쿼리 3 ㅎㅇ! 오늘은 트리와 쿼리 3을 들고 왔다! 문제: 트리와 쿼리 3 HLD를 안다면, 크게 어려워할 문제는 아닐거라 생각한다. HLD에서 dfs ordering과 chain의 생성을 담당하는 부분(위 글에서 dfs2 함수)을 잘 살펴보면, 1에서부터 모든 정점 v까지의 경로에 포함되는 정점들의 order는 깊이가 깊어짐에 따라 순 증가함을 알 수 있다. 이를 이용해
BOJ 13510 트리와 쿼리 1 ㅎㅇ! 오랜만에 글 쓴다. 사실 그동안 센트로이드 디컴퍼지션 짜다가 짜증나서 얼른 이 문제로 갈아 탔다. 각설하고, 트리와 쿼리 1을 푸는 방법을 알아보자. 선행지식: Heavy Light Decomposition 문제: BOJ13510 우선, HLD 문제 잘 푸는 사람이 이 글을 볼 리는 없다는 가정하에 글을 쓴다. HLD를 배웠다면 HLD의 작동 메커니즘이 간선이 아닌, 노드
팁 코드 길이를 줄이는 방법 H9 ㅎㅇ! ps를 한 기간이 꽤 되는 사람이라면, 문제를 푼 후 소스코드의 길이가 남들에 비해 월등히 우람하고 큼직해 현자타임을 느낀 적이 있을 것이다. 바로 이렇게 말이다. 그렇다면, 코드를 줄이는 방법이 필요하지 않겠는가? 간단한 것부터 시작해 몇 가지 알아보도록 하자. (대부분의 온라인저지 C 컴파일러는 GCC를 사용하므로 GCC를 기준으로 서술한다. 이외의 컴파일러에서는
백준 BOJ 13546 수열과 쿼리 4 H9 하위! 적당히 올릴 거 찾다 수쿼4를 낚아왔다. 뭐.. 풀 때는 고통받으며 푼거 같지만 모스를 안다면 심각히 힘든건 없어보이니 각설하고 풀이하자. 문제: BOJ 13546 수열과 쿼리 4 어떤 수열이 주어졌을 때 같은 두 값이 최대한 멀리 떨어진 거리를 구하는 문제이다. 이 문제를 푼다면, BOJ 13545 수열과 쿼리 0도 가볍게 날먹할
