Algorithm/코딩 테스트 준비 - 기초 (10) 썸네일형 리스트형 [코딩 테스트 준비 - 기초] 10. BFS - 최단 거리, 최소 비용 1. BFS만으로 풀 수 있는 문제 DFS와 BFS의 목적은 임의의 정점에서 시작해서 모든 정점을 한 번씩 방문하는 것으로 동일하다. 따라서 모든 인접 정점을 방문하는 목적이라면 DFS와 BFS 중 아무거나 사용해도 상관없다. 하지만, BFS만을 사용해야 하는 문제들이 있다. 바로 모든 가중치가 1일 때, 최단 거리를 구하는 문제이다! cf. 가중치가 1이 아닌 경우 최단 거리를 구하는 문제는 Dijkstra로 푼다. BFS를 이용해 해결할 수 있는 문제는 아래 조건을 만족해야 한다. 최단 거리, 최소 비용 문제이어야 한다. 간선의 가중치가 1이어야 한다. 정점과 간선의 개수가 문제의 조건에 맞춰 해결할 수 있어야 한다. (O(V + E)내에 해결 가능해야 함) 간선의 가중치가 최소 비용의 의미와 일치해.. [코딩 테스트 준비 - 기초] 9. 그래프 - DFS & BFS 1. 그래프 G = ( V , E ) : 그래프는 정점(vertex)과 간선(edge)들의 집합이다. 방향 있는 그래프(유향 그래프) u -> v 방향 없는 그래프(무향 그래프) u - v 2. 그래프의 표현 다음 그래프를 표현하는 방법 세 가지를 알아보자. 1) 인접 행렬(Adjacency Matrix) 2차원 배열로 구현 장점: 임의의 두 정점 사이에 간선 존재 여부를 O(1)에 판단할 수 있다. 단점: 공간 낭비가 심하다 (O(V^2)) 효율성: O(V) 2) 인접 리스트(Adjacency List) 포인터 배열(vector)로 구현 장점: 공간을 효율적으로 쓴다. (O(E)) 효율성: O(정점의 차수) 3) 간선 리스트(Edge List) vector를 사용할 수 없는 환경에서 Linked Lis.. [코딩 테스트 준비 - 기초] 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 리모.. 이전 1 2 다음
