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);
    }

입출력

  • endl'\n'로 대체하기: 속도 개선
  • getline(cin, s): 공백까지 통째로 한 줄 입력
  • cout << fixed << setprecision(n): 소수점 아래 n자리까지 반올림하여 출력

더 읽기댓글 쓰기

Fast I/O 구현 코드

안녕하세요 jinhan814입니다. 제가 문제를 풀면서 자주 사용하는 FastIO 구현 코드를 공유하면 좋을 거 같아서 BOJ 블로그에 글을 작성해보았습니다.؜

(참고 : https://blog.naver.com/jinhan814/222266396476)

؜

더 읽기댓글 쓰기

알고리즘 문제풀이를 함에 있어서 자주 접하게 될 용어들

이런 약자들에 대해 다룬 글이 하나쯤은 있었을 것 같지만, 잘 나오지 않아서 정리해 보았습니다. 이런 종류의 글은 백준 블로그에 어울리지 않았을까 하는 생각이지만, 저도 처음 써보는 거라 이상한 점 있으시면 피드백 주세요^^

OJ들 (Online Judge)

  • BOJ,백준: Baekjoon Online Judge
  • CF,코포: Codeforces
  • 앳코: Atcoder
  • USACO: USA Computing Olympiad
  • xOI: (지명) Olympiad in Informatics (ex. InternationalOI, BalticOI, KoreaOI, JpaneseOI,...)
  • ICPC: International Collegiate Programming Contest

기본 용어들

  • PS: Problem Solving (문제 풀이)
  • CP: Competitive Programming (경쟁 프로그래밍)
  • CS: Computer Science (컴퓨터 과학)
  • STL: Standard Template Library (표준 템플릿 라이브러리)
  • 맞왜틀: 맞는 것 같은데 왜 틀리지
  • 틀왜맞: 틀릴 것 같은데 왜 맞지
  • 솔브닥: Solved.ac 티어 안내 서비스
  • 업솔빙: $\frac{\mathrm{absorbing + upsolving}}{2}$ (≈대회 때 못 푼 문제/헷갈리는 문제를 곱씹어보는 과정)
  • 예제: 문제에서 주어진 input과 output
  • 테케: 테스트 케이스의 약자로, 예제의 일반화. 조건을 만족한다면 다 통용해서 사용함.
  • 섭테: 서브 태스크의 약자로, 부분 문제를 뜻함. 각 부분 문제에는 조금씩 배점이 부여됨.
  • 올솔: All Solve! 다 풀어낸 경우
  • NGD: 노가다. 수학에서 자주 쓰여서 자연스럽게 PS에서도 통용됨.
  • $\mathrm{wlog}$: $\mathrm{Without\, Loss\, Of\, Generality}$의 약자. 일반성을 잃지 않는다는 뜻인데, 예를 들어 $a, b, c$ 세 수의 관계가 대칭적일 경우 $a\leq b\leq c$라고 순서를 강제하는 것이 있다.
  • $\mathrm{isw}$: $\mathrm{In\; the\; Same\; Way}$의 약자. 직역하면 같은 방식으로. 값만 바뀌고 동일한 구조를 유지하는 경우 똑같은 것을 또 쓰는 것을 막기 위함이다.
  • $\mathrm{s.t.}$: $\mathrm{such\; that}$의 약자. '다음을 만족하는' 이라는 뜻이다.
  • ∎: 증명 완료
  • $\mathrm{i.e.}$: $\mathrm{id\; est}$의 약자. 영어로는 that is 정도의 의미이다. '즉,'과 같은 의미이다. (사실 '즉'이 더 짧은 것 같은데?)
  • $\forall$: for all이라는 뜻. "모든 ~에 대해서"
  • $\exists$: exists라는 뜻. "~가 존재한다"

채점 결과

  • AC: Accepted = 맞았습니다!!
  • CE: Compile Error = 컴파일 에러
  • MLE: Memory Limit Exceeded = 메모리 초과
  • PE: Presentation Error = 출력 형식이 잘못되었습니다
  • OLE: Output Limit Exceed = 출력 초과
  • RE: Runtime Error = 런타임 에러
  • TLE: Time Limit Exceeded = 시간 초과
  • WA: Wrong Answer = 틀렸습니다
  • UB: Undefined Behavior, 배열 인덱스 밖으로 벗어난 곳을 참조하는 경우가 대표적. 링크 : UB에 관한 evenharder님의 글 참고!
  • 더 참고할 만한 것들: 링크 : 틀리는 이유에 관한 백준님의 글 참고!

더 읽기댓글 쓰기