Prim Algorithm 특징 무향 그래프에 적용 가능 모든 꼭지점을 포함하는 최소 신장 트리를 알 수 있다. ( MST ) 개념 0-4까지 5개의 노드가 있고 아주 특별한 주머니가 하나 있다. 이 주머니는 안에 들어있는 값들 중 가장 작은 값을 뱉는다. 이제 정점들을 모두 포함하고 가중치의 합이 가장 작은 신장 트리를 Prim Algorithm을 이용해 구해보자. 아무 노드 하나를 골라보자. 2번을 선택하자. 2번 정점을 이제 주머니에 넣자. 현재 거리 합계 : 0 방문 상황: 0 -> 미방문 , 1 -> 방문 0번 0 1번 0 2번 0 3번 0 4번 0 특별한 주머니에서 하나 꺼내보니 방금 넣었던 2번 정점이 들어있다. 이제 2번 정점으로 가자. 2번 정점은 방문 처리를 한다. 2번이 시작 거리이므..

정렬 알고리즘 이번 시간에는 정렬 알고리즘 6개에 대해 설명과 시간복잡도, 그림, 구현 코드를 정리하고 손코딩으로 꼭 외울 수 있게 암기하는 시간을 가져보겠습니다. 아래 참고 사이트 https://www.toptal.com/developers/sorting-algorithms Sorting Algorithms Animations Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions. www.toptal.com https://visualgo.net/en/sorting Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - Vis..

백트래킹이 무엇인가요?? 백트래킹 기법은 해를 찾는 중에 어떤 시점에서 해가 될 수 없다 판단되면 가능했던 시점까지 돌아가 다른 경우로 다시 탐색하는 과정이라고 합니다. 백트래킹은 왜 사용하나요?? 백트래킹은 모든 경우를 따져볼 때 사용하기 좋습니다. 대표적으로 dfs와 함께 사용하는데 모든 경우를 깊이 탐색하면 각 노드를 확인할 때 백트래킹으로 불가능한 시점을 탐색하지 않고 다음 경우로 넘길 수 있어 효율적으로 모든 경우를 탐색 가능하게 합니다. 백트래킹은 어떻게 구현하나요?? N-Queen 문제 출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/12952 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래..

다익스트라 알고리즘 다익스트라 알고리즘은 무엇인가요?? 다익스트라 알고리즘은 대표적인 최단 경로 탐색 알고리즘입니다. 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. 언제 사용하나요?? 말했다시피 목적지로 가기 위한 최단 경로를 구하기 위해 사용합니다. 특징은 음의 간선이 포함되지 않아 현실 세계에 데이터를 가지고 사용하기 좋습니다. 그래서 인공위성 GPS 내비게이션 등 다양한 곳에서 사용합니다. 문제가 그래프로 나와 최단 경로를 구해야 한다면 생각해 볼 만합니다. 왜 사용하나요?? 다익스트라 알고리즘은 다이내믹 프로그래밍입니다. 최단 경로로 가기 위해서는 가는 길도 최단 경로여야 합니다. 이전까지의 최단 경로를 저장해 구하려는 최단 경로를 구하기 때문에 작은 문제를 가지고 큰 문제를 ..

DFS ( Depth First Search ) 깊이 우선 탐색 / BFS( Breadth First Search ) 너비 우선 탐색 DFS와 BFS는 그래프의 전체를 탐색하는 완전 탐색 알고리즘의 기법 중 하나입니다. 아래에 애니메이션이 있습니다. 그림을 보시면 이해하기 수월하실 것입니다. 왼쪽의 그림은 DFS이고 오른쪽이 BFS 입니다. 먼저 DFS는 맨 위 정점부터 끝에 도달하면 돌아가 분기의 처음으로 돌아가 넘어가는걸 보실 수 있습니다. 이처럼 DFS는 가장 끝까지 가보고 그 다음 경우의 끝까지 계속해서 확인하며 가는 경우입니다. 오른쪽의 BFS는 갈 수 있는 분기를 하나씩 처리하며 가는 경우입니다. a가 b, c 로 갈 수 있고 b는 d,e c는 f,g 로 방문 처리를 하며 끝까지 갈 수 있습니..

아래에 3개의 문제가 있습니다. 1. 디펜스 게임 https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 시소 짝꿍 https://school.programmers.co.kr/learn/courses/30/lessons/152996 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 3. 입국 심사 ..