재귀함수정의정의 단계에서 자신을 재참조하는 함수전달되는 상태인 매개변수가 달라질 뿐 똑같은 일을 하는 함수큰 문제를 작은 부분 문제로 나눠서 풀 때 사용함주의사항반드시 기저사례가 존재해야함(종료조건)사이클이 있다면 쓰면 안됨반복분으로 될 것 같으면 반복문으로(함수호출에 대한 비용)exl순열(Permutation)정의순서와 상관이 있는 경우의 수구현next_permutation(first,last) : 순열을 오름차순으로 구해주는 함수가 제공, 시작 주소와 끝주소를 넣어주면 됨prev_permutation(first,last) : 순열을 내림차순으로 구해주는 함수 제공, 시작 주소와 끝주소를 넣어주면 됨next만 기억했다 사용하면 됨공식$_nP_r =  \frac{n!}{(n-r)!}  $구현do_whil..

원상복귀원상복귀란?완전탐색은 모든 범위를 탐색하는 것이지만 이때 어떤 맵에서 색칠하거나 뭘 세운다 했을 때 경우의 수들끼리 상태 값이 영향을 미치지 않게 하려는 방법보통 모든 방문 배열 visited를 통해 "색칠/세움"을 하고" 다시 지움(원상복귀)"를 통해 되돌리는 것코드로 나타내기#include using namespace std;int visited[4]; vector adj[4];vector v;void print(){ for(int i : v) cout 이 코드의 Go 함수를 보자for문안에 visited[there] = 1로 변경한 후 v.push_back(there)을 한 것을 볼 수 있다이는 방문처리를 하고 v안에 방문한 index를 저장한 것이다그리고 Go 함수를 ..

완전탐색정의Brute Force, Exhaustive Key Search이며 노가다라고 보면 됨모든 경우의 수를 탐색하는 알고리즘경우의 수란?순열 또는 조합을 말한다순열 : 순서와 관계가 있을 때 사용, ex) 1,2,3 이 순서와 상관없이 한번만 카운트조합 : 순서와 관계가 없을 때 사용, ex) 1,2,3 2,3,1... 등 순서에 따라 카운트가 늘어남사용 조건문제에 최대 범위가 1억 미만일 때 완탐을 써도됨종종 1억을 넘어도 시간에 따라 가능하기도 하는데 이럴땐 의심하면서 일단 완탐으로 구현해봐야함반복문을 활용한 완전탐색for or while을 이용한 완전탐색단순히 선형적으로 숫자를 찾는 것도 완탐#include using namespace std; int main() { vector v = ..

DFS, BFS 비교공통점둘 다 시간복잡도와 공간복잡도는 인접 리스트로 이루어졌다면 O(V+E)이고 인접 행렬의 경우 O($V^2$)로 동일하다차이점이름설명DFS메모리를 덜 씀, 절단점 등 구할 수 있음, 코드가 더 짧으며 완탐의 경우 많이 사용, 시작 노드와 연결된 한 노드가 갈 수 있는 끝까지 간 후 돌아와 다음 노드를 탐색BFS메모리를 더 씀, 가중치가 같은 그래프내에 최단거리 구할 수 있음, 코드가 더 김, 시작 노드부터 같은 레벨에 있는 노드들을 탐색하여 마지막 레벨까지 탐색- Tip- "퍼져나간다", "탐색한다"라는 글자가 있으면 반드시 DFS, BFS를 생각해야한다!!!!

BFS정의그래프를 탐색하는 알고리즘으로 어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기 전 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘가중치를 가진 그래프에서 최단거리 알고리즘으로 많이 쓰임레이어별, 레벨별로 탐색한다는 뜻수도코드시작 지점을 방문처리를 하고 queue에 push한뒤 queue가 비어있지 않다면 while 반복문을 통해 queue의 앞단에 있는 값을 꺼내 그 값을 중심으로 인접한 노드들을 탐색하는 방법으로 방문한 정점은 방문하지 않고 그렇지 않았다면 방문처리를 해주면서 queue에 push하면서 방문처리를 함BFS(G, u) u.visited = true q.push(u); while(q.empaty()) u = q.front() q.p..

DFS정의그래프를 탐색할때 사용하는 알고리즘으로 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않으며 각 분기마다 가장 멀리있는 노드까지 탐색하는 알고리즘수도코드DFS(u, adj u.visited = true for each v ∈ adj[u] if v.visited == false DFS(v, adj)어떤 정점의 u의 visited를 참으로 바꾸고 u로부터 연결되어 있는 v지점을 탐색이때 방문하지 않았었다면 노드에 대해 재귀적으로 DFS 호출구현 방법돌다리를 두들겨 보기방문이 되어어있지 않으면 방문을 하고 그렇지 않으면 방문을 하지 않는 방법void DFS(int here{visited[here] = true;for(int there..

연결된 컴포넌트정의연결된 하위 그래프를 말하며 연결된 하나의 덩어리라 보면 된다이 덩어리는 연결된 컴포넌트에 속한 "모든 정점을 연결하는 경로가 있다"는 특징을 갖는다풀르드필(floodfill)위의 그림에서 연결된 컴포넌트의 수는 3개이고 각각의 컴포넌트는 2개, 3개, 2개의 정점을 갖는다즉 연결되어 있는지 아닌지를 토대로 연결된 컴포넌트로 나눠 각각의 컴포넌트에 번호를 붙여 색칠하는 알고리즘이 풀르드필 알고리즘이다

Map으로 된 방향 벡터맵으로 주어짐위의 그림처럼 Map으로 주어지는 그래프 문제들이 있다맵은 하나의 그래프로 4가지 방향으로 한칸씩 움직이며 탐색이 가능하다 생각하면 된다이때 맵은 인접 행렬이 절대 아니다!!!4방향 탐색과 방향 벡터4가지 방향인 상하좌우를 y,x 축을 중심으로 움직일 수 있을 것이다이때 갈 수 있는 방향을 각각 배열로 만들어 움직이는 방향을 저장해준다int dy[4] = { 1,0,-1,0};int dx[4] = {0,1,0,-1};for (int i = 0; i 예시 문제Q1. {0, 0}좌표에서 dy, dx를 만들어 4방향(위, 오른쪽, 아래, 왼쪽)을 탐색하며 좌표를 출력하시오.[출처] [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회..

차이점공간 복잡도인접 행렬 : O($V^2$)인접 리스트 : O(V+E)(연결된 정점만 들어가기 때문에 E가 더해진 것이다)//인접 행렬bool adf[v][v];//인접 리스트vector> adj;시간 복잡도 : 간선 한개 찾기인접 행렬 : O(1)인접 리스트 : O(V)//인접 행렬for(int i = 0;i 시간 복잡도 : 모든 간선 찾기인접 행렬 : O($V^2$)인접 리스트 : O(V+E)사용 예시인접 행렬그래프기 조밀(dense)할 때 인접 리스트보다 인접 행렬이 더 좋음어짜피 다 연결되어있기 때문에 메모리적 효율성은 동일하고 정점 i에서 정점 j까지 간선이 있는 확인 속도가 더 빠르기 때문인접 리스트그래프가 희소(sparse)할 때 인접 행렬이 메모리를 더 많이 쓰기 때문에 인접 리스트가 더..