본문 바로가기

Problem Solving

 (59)
Goodbye, BOJ 2019! 후기 Intro 굿바이, BOJ 2019! 라는 대회는 어떻게 보면 제 주도로 만들어진 대회입니다. leejseo님과 rdd6584님과 작년 백준에서 진행했던 디디포스를 끝내고, 다음 대회를 진행해 보자는 말이 나왔었습니다. 10월 초 경에 생각이 나서 대회를 열고 싶었는데 만약 12월 말에 대회를 개최하게 된다면 디디포스와 거의 1년 간격이 된다는 것을 알았습니다. 구데기컵과 키파컵을 보고 백준에도 매년 정기적으로 개최되는 대회가 있었으면 좋겠다고 생각했는데 마침 대회를 여는 시기가 연말이었기 때문에, 낼름 연말 대회 자리를 먹기로 시도했습니다. 백준 대회란이 백준 고유 콘테스트가 아닌 다른 교내대회 오픈컨으로만 가득 채워진 것이 조금 안타까워서도 있었습니다. 그런 고로 자주 활동하는 알고리즘 채팅방에서 사..
BOJ: 코딩 테스트를 위한 길라잡이 (미완성) 들어가기에 앞서 미완성인 길라잡이입니다!!!!! 링크 지금 거의 다 깨져서 조만간 수정 예정입니다 최근 많은 기업들이 코딩테스트를 진행한다고 들었습니다. 왜 코딩 테스트를 진행할까요? 아직 기업 코딩 테스트에 목숨을 걸 나이는 아니지만, 아무래도 기업에서는 대학에서 커리큘럼을 모두 소화했다면 이 정도는 코딩해서 풀 수 있지 않을까라고 생각하기 때문 아닐까 합니다. 실제로 회사에서 해결하기를 원하는 과제가 엄청 대단한 수준을 요구하는 것 또한 아니고요. 하지만 많은 분들이 이를 굉장히 힘들어 합니다. 또 왜 이런 생고생을 해야 하냐고 물으시는 분들도 있습니다. 하지만 이런 간단한 과제조차 효율적으로 해결하지 못하고 또 버그를 내서 제대로 잡지 못한다면, 실무에서 코드가 훨씬 길어졌을 때도 마찬가지로 수렁에..
PS: 뉴비를 위한 Simulated Annealing 입문 (2) INTRO 국내에서 가장 널리 사용되는 온라인 저지인 BOJ에는 Simulated Annealing으로 풀 수 있는 유명한 문제가 하나 있습니다. 바로 동전 뒤집기 2 (https://www.acmicpc.net/problem/2582) 입니다. 많은 사람들이 KOI에도 시뮬레이티드 어닐링 같은 특수한 알고리즘을 시용해서 푸는 문제가 나오냐고 의아해 하는데, 저 당시에는 서브태스크가 아닌 테스트 케이스 당 부분점수가 있었고, 따라서 정해가 적절한 가지치기를 동반한 백트래킹이었다고 추측해 볼 수 있을 것 같습니다. 하지만, 고생고생해서 백트래킹에 휴리스틱 함수를 적용시키는 것 보다는 시뮬레이티드 어닐링을 배워서 써먹는 쪽이 아무래도 훨씬 빠르겠죠. 시뮬레이티드 어닐링은 이러한 종류에 문제에 더 일반적으로 ..
PS: 뉴비를 위한 Simulated Annealing 입문 (1) INTRO PS에서 우리가 푸는 평범한 알고리즘 문제들은 결정론적 문제입니다. 이 말은, 이미 출제자에 의해서 밝혀진 고정된 시간 안에 동작하는 해법이 있고, 우리는 그 해법을 찾아서 구현하기만 하면 된다는 뜻입니다. 그렇지만 NYPC 예선에서 나오는 출력 파일 문제라던가, IOI의 "그 문제"인 nowruz로 대표되는 Output Only 문제, Topcoder에서 진행되는 Marathon Match 등에서는 완벽한 최적해를 찾아내는 것이 불가능하기도 합니다. 이럴 때에는 많은 사람들이 휴리스틱 알고리즘을 사용합니다. 사실 휴리스틱 알고리즘이라고 하면 어떤 특정한 알고리즘을 지칭하는 것이 아닌데, 보통 저는 휴리스틱을 완전 탐색을 할 때 속도 향상을 위해 사용하는 일반적인 휴리스틱과 전역에서 최적점과 ..
[BOJ] 13309 트리 문제 링크: https://www.acmicpc.net/problem/13309 13309번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부모 정점을 나타내는 정수 a가 주어진다 (1 ≤ a ≤ N). 다음 Q개의 줄 각각에는 세 정수 b, c, d가 주어진다. d = 0이면, b와 c를 연결하는 경로가 존재하는 지 묻는 질의만 수행함을 의미한다. d = 1이면, b와 c를 연 www.acmicpc.net 문제 요약: 정점이 20만개인 트리가 주어진다. 이때 어떤 정점 a, b를 잇는 경로가 있는 지에 대한 쿼리 20만개에 응답..
BOJ 길라잡이 (Beta) 내년 동아리 활동을 대비해서 만들어 놓는 [BOJ를 여행하는 히치하이커를 위한 안내서]입니다. 아직 미완성이라 부족한 부분이 있습니다. 보완해야 할 것 같은 부분은 댓글로 달아주시면 감사하겠습니다. ryute.tistory.com/68 한 세트는 총 4개의 소단원으로 구분되어 있습니다. 각 소단원에는 4~5개정도의 문제가 실려 있으며, 난이도 순은 아닙니다. *가 달린 문제는 심화 문제이거나 매우 유사한 문제입니다. 알고리즘 초보 딱지를 떼기 위한 목적으로 다양한 유형의 기초 문제들을 계단식으로 학습할 수 있도록 주제들을 배치하였습니다. C를 문제 해결에 무리 없이 활용할 수 있는 수준에 도달했을 때 시작하는 것을 전제 조건으로 하였습니다. 1-1. 탐색과 정렬 (1) 1-2. 기초 자료구조 (1) 1-..
[CF] 100551A Connect and Disconnect 문제 링크: https://codeforces.com/gym/100551/problem/A 문제 설명: 정점 $n$개로만 이루어진 그래프에 $k$개의 쿼리가 주어지는데, 쿼리는 +, -, ? 이렇게 세 종류가 있다. +는 존재하지 않는 간선 하나를 추가하고, -는 이미 존재하는 간선 하나를 삭제한다. ?는 현재 그래프의 컴포넌트 개수를 출력한다. $n$과 $k$는 둘 다 30만 이하이다. 문제 풀이: - 쿼리가 오직 + 와 ?만 들어온다면...?Union-Find Tree를 이용해서 정점들을 쉽게 합쳐줄 수 있고, 시간복잡도는 $O(k alpha(k) )$가 되겠다. - 제거 쿼리가 추가되었을 때 만약에 정직하게 모든 쿼리들을 다 처리해 준다면...?Union-Find Tree를 그대로 첫번째 풀이에 적..
[USACO] 2018 January Contest (Silver) 풀이 [15589] Lifeguards (Silver)문제 링크: https://www.acmicpc.net/problem/15589문제 설명: $N$ 마리의 소가 1부터 10억 까지의 단위 시간 사이의 임의의 구간을 덮고 있다. 이 소들 중 한 마리를 제거할 때, 여전히 덮혀 있는 구간의 길이를 최대화 하는 문제이다.문제 풀이: $N$의 범위가 10만밖에 되지 않으므로, 사용하는 좌표 역시 20만개를 초과하지 않는다. 따라서 정렬 및 좌표압축 후 스위핑 비슷하게 단 하나의 소만으로 덮혀 있는 구간과 하나 이상의 소로 덮혀 있는 구간의 길이를 prefix sum으로 계산해 주고, 이를 바탕으로 각 소를 한 번씩 제거해주면서 기존에는 덮혀 있었지만 이제 덮혀지지 않는 구간의 길이를 $O(1)$로 계산해 줄 수 ..

티스토리툴바