Machineboy空

완전탐색은 모든 경우의 수를 탐색하는 것이고, 백트래킹은 완전 탐색을 기반으로 하되, 불필요한 연산을 좀 줄이는 것. 경우의 수는 순열과 조합 + 로직으로 풀린다. 이를 재귀 또는 반복문으로 구현할 수 있다. 원상복구 타이밍 잘 처리하기! 상태값이 그 다음 경우의 수에 영향미치지 않게 처리해주는 것 완전 탐색 (brute force, exhaustive key search) 모든 경우의 수를 탐색하는 알고리즘 순열or 조합 + 로직 보통 1억 미만까지는 컴퓨터를 믿고 넘겨라. 예제) https://machineboy0.tistory.com/183 14502 : 연구소 - DFS, deep copy https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바..

https://blog.naver.com/jhc9639/222289089015 [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회 이번주차는 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inord... blog.naver.com 트리 순회(Tree traversal)은 트리 구조에서 각각의 노드를 정확히 한 번만 체계적으로 방문하는 과정 노드를 방문하는 순서에 따라 후위 순회 (postorder traversal) 전위 순회 () 중위 순회 () 보통 설명할 때 이진트리 기반으로 설명하지만 다른 모든 트리에서 일반화시킬 수 있다. *이진트리(binary tree) : 각각의 노드와 자식 노드 수가 2개 이하로 구성되어 ..

탐색이란, 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘이다. 즉, 주어진 데이터 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하다. https://blog.naver.com/jhc9639/222289089015 [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회 이번주차는 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inord... blog.naver.com 그래프를 탐색할 때 쓰는 알고리즘들 깊이우선탐색(DFS, Depth First Search) 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문 방문한 정점은 다시 방문하지 않으며, 각 분기(가지)마다 가능..

https://blog.naver.com/jhc9639/222289089015 [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회 이번주차는 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inord... blog.naver.com 연결된 컴포넌트 (connected component) 연결된 하위 그래프, 연결된 하나의 덩어리 이 덩어리는 연결된 컴포넌트에 속한 모든 정점을 연결하는 경로가 있다. Flood Fill (seed fill) 각 덩어리에 속한 vertex에 같은 숫자를 부여함

https://blog.naver.com/jhc9639/222289089015 [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회 이번주차는 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inord... blog.naver.com 4방향(상하좌우)을 탐색! dy[] = {-1,0,1,0}; dx[] = {0,1,0,-1}; // dy : direction y, ny : next y for(i=0 ~4) ny = y + dy[i]; nx = x + dx[i]; 예제 Q. {0,0} 좌표에서 dy, dx를 만들어 4방향 (상하좌우)을 탐색하며 좌표를 출력하시오. #include using namespace std; const..

https://blog.naver.com/jhc9639/222289089015 [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회 이번주차는 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inord... blog.naver.com 인접해있다 = 연결되어있다. 화살표가 없는 간선을 무방향 간선이라고 한다. 즉, 무방향 간선이 양방향 간선이다. 인접 행렬(adjacneny matrix) 인접행렬이란 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미한다. 0은 두 정점 사이의 경로가 없음, 1은 두 정점 사이의 경로가 있음. a[from][to] i 부터 j 까지는 경로가 있습니다. 느낌으로 사용하..

https://blog.naver.com/jhc9639/222289089015 [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회이번주차는 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inord...blog.naver.com트리(Tree data Structure) 나무 가지를 뒤집어놓은 모양.트리는 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며 무방향 그래프의 일종이자 사이클이 없는 자료구조를 의미.자식 노드와 부모 노드로 이루어진 계층 구조 (회사 조직도 생각하기)무방향 그래프 (즉, 양방향 단방향이 없음)방향그래프(direct graph)와 무방향그래프(indirect graph) 개념방향성 있는 간선(di..

https://blog.naver.com/jhc9639/222289089015 [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회 이번주차는 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inord... blog.naver.com 그래프(Graph) 정점(vertex)와 간선(edge)의 집합 정점(Vertex)와 간선(Edge) 정점(vertex) 노드(node)라고도 불리며 그래프를 형성하는 기본 단위 분할할 수 없는 객체이자 점으로 표현되는 위치, 사람, 물건 등 보통 u와 v 로 많이 나타내는데, u는 from v는 to 간선(edge) 정점을 잇는 선으로 관계, 경로 등 단방향,양방향 간선 Indegree와 Ou..