Algorithm/알고리즘4 [알고리즘] DFS, BFS 개념 BFS와 DFS 두가지 모두 그래프를 탐색하는 방법 그래프: 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종 그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것 DFS 깊이 우선 탐색 (Depth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방식 예를 들어 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더이상 갈 수 없게되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길로부터 다시 다른 방향으로 탐색을 진행하는 방식 BFS 너비 우선 탐색 (Breadth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한.. 2023. 2. 24. [알고리즘] Linear Search [Algorithm - Linear Search] ※ 검색 알고리즘 - 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘에 대해 살펴보자. ※ 선형 검색- 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하면 되는데 이것이 선형 검색(linear search) 또는 순차 검색(sequential search) 알고리즘이다. - 선형 검색(순차 검색)은 결과가 두 조건으로 나누어짐 - 배열의 요소를 맨 앞부터 순서대로 검색함 - key 값인 14를 맨 앞부터 찾는다면 4번째 인덱스에서 key 값을 찾게 되고 검색 성공 - key 값인 99를 맨 알부터 찾는다면 배열을 순차적으로 검색해도 값이 없기 때문에 검색 실패 ※ 선형 .. 2019. 3. 1. [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) ※ 그래프의 개념 - 정점과 간선으로 이루어진 자료구조의 일종. G = (V, E) ※ 그래프 탐색 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 ※ 깊이 우선 탐색 (DFS, Depth-First Search)의 개념 - 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 1. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으.. 2018. 10. 24. [알고리즘] 코딩인터뷰 알고리즘 참고사이트 코딩인터뷰 알고리즘 참고 사이트 "좋은 환경에서 근무하는 좋은 프로그래머가 되자!"좋은 환경의 개발회사에서 근무하고 싶다면 그만큼의 노력이 필요하다.코딩 인터뷰 때문이 아니더라도 좋은 프로그래머가 되고 싶다면 알고리즘에 대한 지식, 이해 그리고 실전 활용은 필수인 것 같다. 아래는 코딩 테스트와 관련하여 도움이 될만한 사이트 링크들이다. [알고리즘 사이트] 코딜리티(SK계열, 이스트소프트) : https://codility.com/programmers/ 해커랭크(이베이, 외국계) : https://www.hackerrank.com/ 리모트인터뷰(라인플러스) : https://www.remoteinterview.io/ 백준 온라인저지(한글) : https://www.acmicpc.net/ 코딩도장 : ht.. 2018. 5. 21. 이전 1 다음
