목록Computer/알고리즘 (22)
Machineboy空
탐색이란, 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘이다. 즉, 주어진 데이터 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하다. 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..
순열과 조합의 개념과 공식 순열(Permutaion) 조합(Combination) 서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수. 서로 다른 n개 중에서 r개(n≥r) 취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한 조합. ex. 축구 선수 12명이 서로 인사하는 경우의 수 ex. 3개의 자연수를 이용해 만들 수 있는 3자리 자연수 ex. 다른 색의 공 3개를 순서와 관계있게 3개 뽑는 경우 ex. 다른 색의 공 7개 중 2개를 뽑는 경우의 수. 경우의 수를 구하는 대표적인 방법들로, 뽑는 순서가 관계가 있으면 순열, 없으면 조합이다. 경우의 수를 구하는 다른 방법들로는 모든 경우 완전 탐색하는 브루트 포스(Brute Force) 즉, 합의 법칙 등이 존재한다. 순..
https://machineboy0.tistory.com/57 시간복잡도(Time-Complexity), 빅오표기법(Big-O) 시간복잡도 (Time-Complexity) 복잡도는 시간복잡도와 공간복잡도로 나뉜다. 시간복잡도 알고리즘에서 주어진 문제를 해결하기 위한 연산 횟수 입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸 machineboy0.tistory.com https://blog.naver.com/jhc9639/222283814653 [알고리즘 강의] 1주차. 시간복잡도, 빅오표기법, 공간복잡도, 누적합, 구현 알고리즘 강의 1주차입니다. 시간복잡도, 빅오표기법, 공간복잡도, 누적합, 구현까지 알아보겠습니다. 시간... blog.naver.com # 시간복잡도 예제 # 시간복잡도 1 n^2 몇..