Algorithm (26) 썸네일형 리스트형 백트래킹(Back-Tracking) 핵심 요약 해를 찾는 도중 해가 아니어서 막힐경우, 되돌아가서 다시 해를 찾아가는 기법 시간 복잡도를 감소시킬 수 있는 기법 최적화 문제, 결정 문제 등을 풀 때 활용한다. 유망성 판단(promising)이 중요하다! 사용처 DFS 등 대표 문제 백준 9663, N-Queen 문제. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 분할 정복(Divide & Conquer) 핵심 요약 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 -> 분할 각 문제에 대한 답을 계산 -> 정복 이를 병합해 문제를 해결하는 알고리즘 -> 조합 즉, 알고리즘을 각개 격파한다고 볼 수 있다! 구현 방법 보통 재귀로 많이 구현된다. [C++] 비트마스킹(Bitmasking) 비트마스킹데이터 타입마다 각 메모리 사용 크기가 있다.만약 int 라고 하면 4byte 즉, 32 bit의 크기를 가진다.표현하면 0000 0000 0000 0000 0000 0000 0000 0000이 될 것이다. (0과 1을 씀)만약 아이템이 있고 없고를 구현해야할 때 bool 변수 32개를 쓰는 대신에 하나의 비트를 다룰 수 있을경우,우리는 int 자료형 하나로 32개의 아이템이 있고 없고를 표현할 수 있다. 또한 비트 연산은 연산 속도가 빠르다는 장점을 가지고 있다.만약 2번째 아이템이 있다면 0100 이런식으로 0을 1로 바꾸어 표현하는 것이다. &, |, ~, ^, >>, & - AND 연산자로 하나라도 0 이면 0으로 둘다 1이면 1의 출력값을 가진다.| - OR 연산자로 하나라도 1이면 1.. DP(Dynamic Programming) 핵심요약 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 간단한 구현, 복잡한 점화식 최적의 원리가 성립해야함. 최적의 원리 "어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다.” 문제 풀이 순서 문제 탐색 DP 배열에 어떤 값을 저장할 것이고, 인덱스는 어떤 것을 의미할지 정의를 한다. dp 벡터를 선언할 때 최소값을 찾을경우 MAX로, 최대값을 찾을경우 MIN으로 선언한다. DP식(점화식) 세우기 메모이제이션된 부분 문제들의 해를 이용하여 차례로 더 큰 상위 문제의 답을 어떻게 구할지를 고민한다. 검증 및 구현(시간 복잡도) 문제 유형 결과값들 더하기. 결과값들 중 최대, 최소 구하기. 배낭 채우기(.. 투 포인터(TWO-POINTER) 핵심 요약 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해서 값을 얻는 형태 주로 while문으로 구성 문제 유형 연속된 수들의 합 부분 배열의 합 풀이 방법 포인터 2개가 같은 방향 포인터 2개가 양 끝에서 반대로 진행(이분 탐색과 유사) [C++] 멀티셋[MULTISET] 핵심요약 key값이 중복이 가능한 set이다. 나머지는 set과 모두 동일하다. 사용법 #include //따로 을 추가하지 않는다. 나머지 기능들은 아래 글에서 확인하자. 2023.10.01 - [알고리즘을 위한 간략 정리/자료구조 - 연관 컨테이너] - [C++] 셋(SET) [C++] 셋(SET) 핵심요약 중복 제거 삽입되는 순서에 상관없이 정렬되어 입력된다. 자료구조 이진 트리로 구성되어 있다. 사용 방법 #include SET의 반복자(iterator) s.begin() //set의 시작이 되는 주소값 반환 s.end() //se dmoritle.tistory.com [C++] 셋(SET) 핵심요약 중복 제거 삽입되는 순서에 상관없이 정렬되어 입력된다. 자료구조 이진 트리로 구성되어 있다. 사용 방법 #include SET의 반복자(iterator) s.begin() //set의 시작이 되는 주소값 반환 s.end() //set의 마지막 부분에 대한 주소값 반환(정확히는 마지막 뒤 공백구간) SET의 용량(capacity) s.empty() //비어있을 경우 true, 아닐경우 false를 리턴 s.size() //저장되어 있는 크기를 리턴 SET의 삽입, 삭제(modifiers) s.insert() //값 삽입 s.erase() //저장된 요소 삭제 s.clear() //저장된 요소들 전부 삭제 s.swap() //s1과 s2를 서로 교환 SET의 기능(operator) s.find() .. [C++] 원하는 자리수까지 출력하기(반올림, 올림, 내림) 기본적인 반올림, 올림, 내림 헤더 파일이 필요 기본적으로 반올림은 round( 숫자 ), 올림은 ceil( 숫자 ), 내림은 floor( 숫자 )이다 소숫점 1자리에서 진행된다. #include #include using namespace std; int main(){ float num = 3.47; cout 이전 1 2 3 4 다음