ABC259 참가 후기

어제 열렸던 AtCoder Beginner Contest 259 후기를 써 보려 합니다.

원래 이런 거 잘 쓰지 않는 성격이긴 한데 한 번 써 보고 싶어서 써 봅니다.


더 읽기댓글 쓰기

Segment Tree with Lazy Propagation의 비재귀 구현

INDEX

  1. Introduction
  2. Lazy Propagation이란?
  3. Point Update Range Query의 비재귀 구현
  4. Range Update Range Query의 비재귀 구현
  5. Segment Tree 구현 코드
  6. 사용 예시
  7. Segment Tree with Lazy Propagation 구현 코드
  8. 사용 예시

؜

더 읽기댓글 쓰기

priority_queue, set의 정렬 기준 커스텀하기

priority_queue, set는 std::sort 등과는 다르게 함수 객체만 사용할 수 있습니다.

따라서 set<int,[](int x,int y)->bool{return x<y;}> s;와 같은 구문은 실행되지 않습니다. 혹은, 함수 cmp에 대해서 set<int,cmp> s;도 실행되지 않습니다.

이를 해결하기 위해서 일반적으로 새 구조체를 작성하는데, 그럴 경우에 다양한 정렬기준에 대해서 전부 구조체를 작성해야 하므로 번거롭습니다. 하지만 다음과 같이 구현하면 별다른 구조체 없이도 제대로 동작하게 됩니다.

더 읽기댓글 쓰기

(C) 다차원 배열 편하게 malloc하기

백준 블로그는 처음이네요! 어떤 소재를 올리는 게 좋을지 모르겠어서 일단 제 다른 블로그에 올린 글에서 소재를 빼와서 쓰려고 합니다. C++에서는 쓸 수 없고 컴파일러도 맞아야 되기 때문에 유용할지는 모르겠네요.

보통 코드를 C로 짤 때는 아래와 같이 다차원 배열을 할당받습니다.

void version1(int h, int w) {
    int **array_2d = malloc(h * sizeof(int *));
    for(int i = 0; i < h; i++)
        array_2d[i] = malloc(w * sizeof(int *));

    // ...

    for(int i = 0; i < h; i++)
        free(array_2d[i]);
    free(array_2d);
}

더 읽기댓글 쓰기

USACO 규칙(2021년 12월 이후)

이 글은 usaco.org의 정보를 바탕으로 작성되었습니다.

소개

USACO(미국 정보올림피아드, USA Computing Olympiad)가 내일부터(17일~20일) 열립니다! 온라인으로 진행되는 대회로, 누구나 참여 가능하고, 무료입니다. 백준에서는 boj.kr/usaco 를 통해 풀어볼 수 있습니다. 다만 득점 정도를 확인할 수 없기 때문에 필요하다면 usaco.org를 사용하는 것도 좋을 것 같습니다.

승급 제도

첫 참가자들은 브론즈 등급으로 시작합니다. 승급 점수 컷을 넘으면 다음 등급으로 승급합니다. 등급은 Bronze > Silver > Gold > Platinum 입니다. 승급 이후에는 이전 등급의 대회를 다시 응시할 필요가 없습니다. 즉, 등급의 강등이 없습니다. 또한 해가 지나도 유지됩니다.

대회 형식

언어는 C/C++, Java, Python을 사용할 수 있습니다. 3~4개의 문제가 출제되고, 3~5시간동안 진행됩니다. 타임 프레임 형식으로, 대회 기간 동안 아무때나 원하는 시간에 참가하면 됩니다. 따라서 종료 후에 문제에 대해 발설하면 안됩니다. 대회에서 만점을 받으면 바로 다음 등급의 대회를 참가할 수 있습니다.

더 읽기댓글 쓰기

문제 검수 체크리스트

현재 BOJ에서 열리는 대회에는 일정 기준을 만족하는 검수진이 필수로 요구되지만, 정확히 무엇을 검수해야 하는지에 대해서는 정리된 바가 없습니다.

출제자, 검수자가 신경써야 할 사항을 이 글에서 정리해 보고자 합니다.

수시로 내용을 채울 예정입니다.

더 읽기댓글 쓰기

(C/C++) 조건부 컴파일로 디버깅용 출력 한방에 없애기

여러분이 방금 틀렸습니다를 받았던 문제의 코너 케이스를 고쳤다고 해봅시다.

들뜬 마음에 점검도 안하고 바로 백준에 코드를 제출해버립니다!

void AddEdge(int v1, int v2)
{
    adjacencyList[v1].push_back(v2);
    adjacencyList[v2].push_back(v1);
    // 어라? 이거 지웠어야 하는데 그냥 제출해버렸네...
    printf("[DEBUG] Add edge (%d, %d)\n", v1, v2);
}

아... 근데 깜빡하고 디버깅하면서 출력했던 문자열을 안 지우고 제출해서 또 틀렸습니다를 받아버렸습니다...

깜빡하지 않았다고 하더라도, 디버깅용 문자열을 여기저기서 출력했다면 그걸 일일히 찾아서 지우는 것도 꽤 귀찮은 일입니다.

더 읽기댓글 쓰기

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

개요

이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다.

이분 탐색 문제를 풀다보면 탈출 조건으로 lo <= hi, lo < hi, lo + 1 < hi 중 어느 걸 선택해야 할 지, 정답이 lo인지 hi인지 (lo + hi) / 2인지 모르겠고, 심지어는 while문이 끝나지 않아서 시간초과를 받기도 합니다.

더 읽기댓글 쓰기

❌ fflush(stdin), rewind(stdin) ❌

들어가면서

질문 게시판에 올라오는 C/C++ 코드 중 종종 fflush(stdin) 또는 rewind(stdin) 을 사용한 코드들이 올라옵니다.

결론부터 말하자면, 이런 문장을 쓰는 프로그램은 호환성이 없으며, 구현체가 달라지면 전혀 다른 행동을 할 수 있습니다.

위 두 문장은 Windows 운영체계에서 Microsoft Visual C++ (이후 MSVC)로 컴파일한 프로그램을 실행하고, stdin 이 키보드인 경우에만 원하는 동작을 하고, BOJ 의 채점 환경인 Linux 운영체계에서 GCC 또는 clang 로 컴파일한 프로그램을 실행하고, stdin 이 파일인 경우에는 전혀 다른 동작을 합니다. 이 두 함수의 원래 의미를 설명하는 것으로 글을 시작하겠습니다.

더 읽기댓글 쓰기

C++ 유용한 기능들

이 글은 유용한 기능들을 소개하는 글입니다. "요약 노트" 정도로 생각해주시면 될 것 같습니다. 그래서 구체적인 원리나 주의사항, 확장 가능성에 대한 이야기는 생략합니다. 의견은 언제든 환영이고, 앞으로도 이 글은 지속적으로 개선해나가겠습니다. 이 글은 C++의 기본 문법을 숙지했고, std::vectorstd::set 등을 사용해본 경험이 있는 분들이 읽기 적합합니다.

  • f, l은 앞 주소와 뒷 주소를 나타내고, 여러 개면 번호를 1부터 차례대로 붙였습니다. (f, l은 first와 last의 약자, [f, l)임에 유의하세요)
  • 비교기반 함수에 대해서는 비교 함수를 추가하는 것이 항상 가능하므로, 생략하였습니다. (e.g sort(f,l)가 있으면 sort(f,l,cmp)가 존재함)
  • max가 있으면 min도 있습니다.
  • 아래의 코드 형식을 기본으로 합니다. 4번 줄은 입출력 속도를 향상하는 구문입니다. 자세한 정보는 입력 속도 비교글, 출력 속도 비교글을 참고해주세요.
#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0)->sync_with_stdio(0);
}

입출력

더 읽기댓글 쓰기