백트래킹 백트래킹은 그야말로 컴퓨팅적 사고의 정수.. 까지는 아니고 기초쯤 되는듯 싶다. 아직 적은 문제지만 풀어봤을때 괜찮았던 문제는 N과 M시리즈 인 것 같다. 가장 대표적인 문제는 N-Queen 문제. 백트래킹은 간단하게 선택지가 몇 개 있으면, 발 담가보고 안되면 다시 되돌아가는(Back Tracking) 기법이다. [기초 자료구조] 스택 Stack이란 LIFO(Last In First Out)의 개념을 가진 자료구조로, 먼저 들어간 것이 나중에 나오는 구조이다. 즉 아래와 같이 바닥이 막힌 유리병을 생각할 수 있다. STL에서는 라이브러리를 포함하여 사용하며, index로 접근이 불가능하다. #include using namespace std; int main() { int a=5, b=6; stack stk; return 0; } 위와 같은 상태에서 stk.push(a); stk.push(b)를 해주면 다음과 같다. 여기서 stk.pop()을 해주면 다음과 같다. stk의 원소에 접근하기 위해선 stk.top()을 사용한다. 이 경우 원소를 참조는 하지만 stack에서 빼지는 않는다. 즉 이 상태에서 stk.top() == 5이다. 스.. BFS와 DFS void BFS(int x, int y){ deque dq; dq.push_back({x,y}); while(!dq.empty(){ x = dq.front().first; y = dq.front().second; dq.pop_front(); for(int i=0; i Knapsack 알고리즘 Knapsack 알고리즘은 대학 학부 강의에서도 나올 정도로 유명한 알고리즘이다. 배낭에 물건을 담는데, 최대 가치의 물건을 담으려고 한다는 배경이 있다.. 전형적인 다이나믹 프로그래밍(DP) 문제다. DP의 기본은 과거의 값을 사용한다는 점이다. 코드를 짜보기 전에 어떻게 짤 것인지 대략적인 틀을 짜야한다. DP를 몇차원 배열로 사용할 것인가를 먼저 정해보자. 예를 들어 물건 4개가 있는데, 물건 하나씩 집어 무게와 가치를 본 후 넣을까 말까 고민한다고 생각해보자. 첫번째로 이 물건을 넣었을 때 갱신해줘야 하는 값은 배낭의 무게와 배낭 안에 들어있는 물건의 가치이다. 즉 DP[무게] = 가치로 놓을 수 있다. 즉 각 배낭의 무게에서 최대 가치를 DP에 저장한다. 그런데 이 때 각 물건을 각 배낭의 무게.. 이전 1 다음
