비트마스크(Bitmask)는 정수의 이진수 표현을 자료구조로 쓰는 기법입니다.집합의 크기가 작은 집합을 나타내기 위해 많이 사용되며정수형 변수 하나로 이들을 나타낼 수 있어 함수의 인자로 넘겨주거나배열의 인덱스로 사용하여 접근이 가능하기에 익숙해지면 유용한 기법입니다.완전탐색, DP를 사용하는 문제를 풀 때 원하는 자료를 간단하게 표현하기 위해,또는 추후 트리파트의 구간트리에서 배우게 될 팬윅트리에서도 이 기법을 응용하여 사용합니다.여러가지 테크닉이 존재하기에 많이 사용해보시는 것이 좋습니다. 기본 문제 11723번: 집합2098번: 외판원 순회1102번: 발전소
수치해석(Numeric Analysis)은 직접 풀기 힘든 수학문제를 근사적으로 푸는 알고리즘입니다.프로그래밍 대회에서 자주 나오는 기법은 이분법으로그래프 상에서 x축 윗부분에 위치한 점 하나와 아랫부분에 위치한 점 하나를 찾은 뒤이 범위에서 0이되는 지점을 수치적으로 빠르게 찾아내는 기법입니다.또한 삼분 검색이라는 기법은 최대점, 최소점이 있는 그래프에서 이러한 점을 찾아내는 기법입니다.주어진 문제를 다음과 같은 기법으로 풀 수 있는 문제로 변형하여 답을 찾아내야하는 경우가 많습니다.이분법의 경우 범위가 N일 때 O(lgN)번만에 0이 되는 지점을 찾을 수 있기에수의 범위가 큰 문제에 대하여 이 기법을 생각해 볼 수 있습니다. 기본 문제 2805번: 나무 자르기1300번: K번째 수15732번: 도토리..
정수론(Number theory)은 수학의 한 분야입니다.그 중에서 프로그래밍 대회에 기본적으로 자주 나오는 기법을 소개합니다.빠르게 소수를 찾는 기법인 에라토스테네스의 체빠르게 최대공약수(Greatest Common Divisor)를 찾는 기법인 유클리드 알고리즘C언어에서의 표현할 수 있는 수의 범위가 제한 되어있기에 큰 수 연산에 사용되는 나머지 연산나누기의 나머지 연산을 대신하여 사용하는 나머지 연산의 곱셈 역원이를 구하는 두가지 방법인 확장 유클리드 알고리즘과 페르마의 소정리를 알아두시면 좋습니다. 기본 문제 1929번: 소수 구하기2609번: 최대공약수와 최소공배수10430번: 나머지11401번: 이항 계수 3
탐욕법(Greedy)은 각 단계마다 지금 가장 좋은 방법만을 선택하는 기법입니다.이러한 방법을 이용하여 원하는 답을 무조건 찾을 수 있는지 증명하는 방법은 매우 어렵기에 대회에서는 이러한 방법이 예외가 없다고 생각이 된다면 증명없이 기법을 사용합니다.가장 좋은 방법만 선택하여 가기에 구현이나 시간복잡도는 크지 않지만문제가 탐욕법을 이용하여 푸는 문제인지 파악하기는 어렵기에 자주 나오는 유형을 풀어보는 것이 좋습니다. 기본 문제 11047번: 동전 015729번: 방탈출1931번: 회의실배정11000번: 강의실 배정
DP(Dynamic Programming)는 동적계획법이라고도 불리며중복되는 부분문제를 저장하는 기법입니다.문제의 답을 구하는 방법이 점화식을 이용하여 이전의 값들이 반복적으로 쓰이는 문제일 경우기저사례, 점화식을 기반으로 반복적으로 쓰이는 값들을 저장하면서 코드를 작성합니다.푸는 방법은 크게 재귀적 동적 계획법, 반복적 동적 계획법이 있으며재귀적 동적 계획법은 메모이제이션 기법을 사용하여 점화식을 그대로 코드로 옮기기에 직관적이다는 장점,반복적 동적 계획법은 슬라이딩 윈도우라는 기법을 이용하여 공간복잡도를 줄일 수 있다는 장점이 있습니다.DP를 응용한 문제 중 어떠한 방법을 거쳐서 이러한 최적화 답을 구하였는지,조건에 맞는 k번째 답을 계산하고 싶을 경우에도 작성했던 DP의 함수를 조금만 변형하여 구할..
완전탐색(Brute Force)은 무식하게 가능한 방법을 전부 만들어보는 알고리즘으로문제에 주어진 입력 범위가 모든 경우를 봐도 시간 내에 할 수 있는 문제라면 사용할 수 있는 기법입니다.특정 문제에서는 되추적(Backtracking) 기법도 같이 사용하여원하는 답이 현재 상황으로 절대 나타나지 않는다고 판단이 되는 경우에는이전 상황(부모 노드)으로 돌아가서 시간을 단축 시키기도 합니다.느리지만 다른 더 빠른 알고리즘을 찾는 기본적인 아이디어가 되는 경우가 많습니다. 기본 문제 1182번: 부분수열의 합15728번: 에리 - 카드2580번: 스도쿠9663번: N-Queen