Algorithm (62) 썸네일형 리스트형 [코딩 테스트 준비 - 기초] 8. 다이나믹 프로그래밍(DP) 1. 다이나믹 프로그래밍 개념 아래 두 가지 속성을 만족하는 문제를 다이나믹 프로그래밍으로 풀 수 있다. 1) 문제들이 겹쳐야 한다. 문제를 작은 문제로 쪼갤 수 있어야 한다. 큰 문제와 작은 문제를 같은 방법으로 풀 수 있어야 한다. 2) 최적 부분 구조를 만족해야 한다. 문제의 정답을 작은 문제의 정답에서 구할 수 있어야 한다. 한 문제의 정답은 항상 일정하다. 즉, 각 문제는 한 번만 풀어야 하고 그 정답을 어딘가에 메모해 놓아야 한다. 즉, 우선 문제가 작은 문제로 나누어지는지 확인하고, 이후 작은 문제의 정답을 이용해서 원래의 정답을 구할 수 있는지 확인한다. 이 경우, 다이나믹 프로그래밍을 이용하면 된다. 구현 방식 Top-down 재귀를 통해 구현 큰 문제를 작은 문제로 나누어 함수를 호출한.. [코딩 테스트 준비 - 기초] 7. 비트마스크(Bitmask) 1. 비트 연산 NOT, AND, OR, XOR A B ~A A & B A | B A ^ B 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 1 1 0 not 연산의 경우 자료형에 따라 결과가 달라지는 것을 주의해야 한다. 특히, unsigned와 signed에 따라서 정수로 보여지는 값이 달라진다. (2의 보수 때문) Shift Left, Shift Right A B A를 B비트만큼 오른쪽으로 밀기 A / (2^B) ex. 2 >> 4 = 2 / 2^4 = 2 / 16 = 1 / 8 2. 비트마스크 개요 비트마스크는 비트 연산을 이용해 부분집합을 표현하는 것이다. 비트마스크를 통해 집합을 정수로 나타낼 수 있다. 단, 이때 집합에 저장할 수 있는 수의 범위가 정해져 있어야 한.. [코딩 테스트 준비 - 기초] 6. 브루트 포스 - 순열 1. 다음(이전) 순열 구하기 순열은 순서가 중요한 경우 사용한다. 순열을 사전순으로 나열했을 때, 첫 순열은 배열을 오름차순 정렬한 것이고, 마지막 순열은 내림자순 정렬한 것이다. 다음 순열이란 i번째 순열이 주어진 경우 i+1번째 순열을 의미한다. (이전 순열은 반대) 시간복잡도는 배열의 크기가 N인 경우 O(N * N!)이다. 따라서 N 다음 순열 이용 내림차순 정렬 -> 이전 순열 이용 [백준 10972 다음 순열 & 백준 10973 이전 순열] #include #include using namespace std; int main() { int n; cin>>n; int arr[n]; for(int i=0; i>arr[i]; if(next_permutation(arr, arr + n)){ //이전.. [코딩 테스트 준비 - 기초] 5. 브루트 포스 - 재귀 & 백트래킹 1. 재귀함수 작성 방법 이전 글에 더해 재귀함수 작성법을 자세히 설명한다. 재귀함수는 i 번째 방법과 i+1 번째 방법의 패턴이 동일한 경우 사용한다. 재귀함수를 작성할 때는 기준을 정해야 한다. 어떤 기준에 따라서 함수를 호출할지 정하는 것이다. 다음으로 넘어갈 때 변화하는 것에 집중해 이를 함수의 인자로 만들거나 따로 관리해야 한다. 재귀함수의 기준과 인자를 결정한 다음에는, 다음으로 넘어갈 때 함수를 어떻게(각각의 경우에 값이 어떻게 변화하는지, 변화에 따라 어떻게 호출할 것인지) 호출할 것인지 파악한다. 정답을 찾은 경우를 파악한다 = 재귀 종료 조건 불가능한 경우를 파악한다 (문제의 조건이 지켜지지 않은 경우 or 답을 찾을 수 없는 경우) 구현 Point 재귀함수 호출 전, 그 함수를 호출하.. [코딩 테스트 준비 - 기초] 4. 브루트 포스 - N과 M & NM과 K 1. 재귀함수 작성 방법 재귀함수는 i 번째 방법과 i+1 번째 방법의 패턴이 동일한 경우 사용한다. 다음으로 넘어갈 때 변화하는 것에 집중해 이를 함수의 인자로 만들거나 따로 관리해야 한다. 구현 Point 재귀함수 호출 전, 그 함수를 호출하기 위한 상태를 미리 준비해둬야 한다. 재귀함수 호출이 끝난 것은 해당 경우가 끝난 것으로, 원 상태로 돌려줄 필요가 있다. 재귀의 종료 조건을 설정하는 것이 중요하다. 2. N과 M [백준 15649 N과 M(1)] index번 위치에 올 수 있는 수를 결정하는 함수를 재귀함수로 작성한다. 1번 위치에서 2번 위치로 넘어갈 때 변화하는 것은 위치와 앞에서 1번 위치에서 사용한 숫자 i의 사용 여부이다. 벡터를 사용하기 때문에 배열의 현재 위치를 따로 관리하지 않.. [코딩 테스트 준비 - 기초] 3. 브루트 포스 - 그냥 다 해보기 1. 브루트 포스 브루트 포스는 모든 경우의 수를 다 해보는 것이다. 가능한 경우의 수의 시간복잡도를 계산해보고 제한 시간 내에 풀 수 있는 지 확인한다. 대부분 O(경우의 수 * 방법 1개를 시도해보는데 걸리는 시간)이 걸린다. 참고) 제한 시간이 1초인 경우 N N! N 2^N 2. 그냥 다 해보기 for문 사용 [백준 3085 사탕 게임] string vector로 입력을 받는다. (처음에는 char로 받을 생각만 했는데..!) algorithm 헤더의 swap을 사용한다. vector box(n); for(int i=0; i>box[i]; [백준 1476 날짜 계산] 모든 가능한 경우의 수는 15 x 28 X 19 = 7980 로 다 해보면 답을 찾을 수 있음을 알 수 있다. [백준 1107 리모.. [코딩 테스트 준비 - 기초] 2. 수학 (나머지 연산, 약수, 최대공약수와 최소공배수, 소수) 1. 나머지 연산 (A + B) % M = ((A % M) + (B % M)) % M (A * B) % M = ((A % M) * (B % M)) % M (A - B) % M = ((A % M) - (B % M) + M) % M 📌 백준 참고 문제 https://www.acmicpc.net/problem/10430 https://www.acmicpc.net/problem/4375 2. 약수 1) N의 약수를 모두 구하는 방법 1부터 N까지 모든 자연수로 나누기 -> O(N) 1부터 √N까지 모든 자연수로 나누기 -> O(√N) C가 A의 약수라면, A/C도 A의 약수임을 이용 코드를 작성할 때, i [코딩 테스트 준비 - 기초] 1. 시간 복잡도와 언어별 유의사항 알고리즘을 체계적으로 접근해 보고자 코드플러스에서 코딩 테스트 준비 묶음을 구매했다. 해당 강의를 수강하고 기억할 만한 것들을 기록할 것이다. 유료 강의이기 때문에 모든 것을 남길 수는 없지만 시간이 흘러 기억이 희미해졌을 때 스스로 복기할 수 있을 정도는 정리할 것이다. 세부적인 내용이 궁금하면 강의를 구매하자! 1. 시간 복잡도 알고리즘 문제를 해결하는 데 있어 수행시간이 가장 중요하다. 코드를 작성하기 전에 문제의 크기를 먼저 확인하고 시간복잡도를 계산해보자. 각 시간 복잡도 별로 1초가 걸리는 입력의 크기는 다음과 같다. 시간 복잡도 입력의 크기 O(1) 상관 없음 O(logN) 대충 1억 O(N) 1억 O(NlogN) 5백만 O(N^2) 1만 O(N^3) 500 O(2^N) 20 O(N!) 10.. 이전 1 2 3 4 5 6 7 8 다음
