algorithm10 Pair pair STL 컨테이너 : pair, vector 1) 정의 이름이 'first', 'second'인 두 개의 변수를 저장할 수 있는 struct이다. 2) 용도 (1) 이차원 배열의 인덱스 (2) 이차원 좌표평면에서의 좌표 (3) 정점 번호와 해당 정점 번호까지의 최단거리를 묶어서 저장해야 되는 경우 3) 사용법 pair를 사용하기 위해서는 를 include해야 한다. pair는 다른 컨테이너들에 비해 간단한 구조이기 때문에 멤버 함수가 적다. // pair 선언 #include utility pair p; pair p; // pair 생성 int a = 1, b = 2; pair p = make_pair(a,b); pair p = make_pair(1,2); // pair의 멤버 변수에 접군 int.. 2021. 8. 4. Queue Queue 1) 정의 FIFO(First In First Out, 선입선출) 자료구조 2) 용도 (1) BFS (2) 특별한 알고리즘을 사용하는 것이 아니라 직접 문제 상황을 구현하는 문제들 중 FIFO의 구조를 문제를 풀때 3) 사용법 queue q; q.size(); // q의 사이즈(물리적 저장 용량이 아닌 원소의 개수) q.empty(); // q의 사이즈가 0인지 아닌지를 확인 q.front(); // q에 가장 먼저 들어간 원소를 리턴 q.back(); // q에 가장 나중에 들어간 원소를 리턴 q.push(val); // q의 뒤에 val 추가 q.pop(); // q에 가장 먼저 들어간 원소를 삭제 중요한 내용 queue q, emt; swap(q, emt); swap 함수 : queue에.. 2021. 8. 4. Backtracking이란 무엇인가? 백트래킹(Backtracking) 일반적인 알고리즘이다. 백트래킹은 CSP(Constrain Staisfaction Problems)을 해결하기 위해 쓰인다. 백트래킹은 모든 조합의 수를 조건이 만족할 때 살펴본다. N-Queen문제에서 많이 사용된다. N * N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 4 * 4 기준으로 문제를 풀어보자. 퀸은 칸을 기준으로 오와 열, 대각선 이동이 가능하다. 첫 번째 퀸과 공격할 수 없게 배치할려면 2번째 줄은 3, 4번째 위치에 퀸을 놓아야 한다. 첫 번째 퀸의 위치를 (1, 1)로 하면 트리구조는 다음과 같다. 만약 이문제를 가지치기 하지않는 DFS로 풀이했다면 유망하지 .. 2021. 8. 4. DP란 무엇인가? 동적 계획법 동적 계획법(dynamic programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 1. 동적 계획법의 조건 1) 부분 반복 문제(Overlapping Subproblem) 동적 계획법의 등장은 피보나치 수열에서 시작되었다고 한다. 피보나치 수열을 재귀 함수로 표현할 시, 이와 같다. fib(1) = 1; fib(2) = 1; fib(n) = fib(n-1) + fib(n-2); // 메소드로 표현한 피보나치 수열 int fib(int n) { if (n 2021. 8. 4. 이전 1 2 다음
