프림 알고리즘과 다익스트라 알고리즘의 공통점 그래프 최소 비용의 관점에서, 최소 비용을 탐색한다는 것이 가장 큰 공통점 구현 방법에서 반복문과 우선순위 큐 모두 사용 가능 프림 알고리즘과 다익스트라 알고리즘의 차이점 프림 알고리즘 다익스트라 알고리즘 간선 선택 기준 선택한 정점과 인접한 정점들 중 최소비용의 간선이 존재하는 정점 선택 해당 노드로 향하는 경로의 최소값, 간선의 가중치의 합이 최소인 경로 시작 노드의 차이에 따른 결과값 변화 없음 (모든 정점에 대해 동일한 결과) 있음 (정점마다 결과값이 달라짐) 저장 핵심 데이터 간선의 가중치 해당 정점에 도달하기 위한 최소 cost 저장 (경로를 포함) 🖥️코드 구현 import java.util.*; public class 다익스트라_우선순위큐 { s..
알고리즘/개념정복
*본 포스팅은 분할정복 알고리즘에 관한 학습을 위해 작성되었습니다. #분할정복 알고리즘 ✍ 하나의 큰 문제를 작은 문제들로 나누어 문제를 해결하는 방법 #설계과정 분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다. 정복 (Conquer) : 나눈 작은 문제를 각각 해결한다. 통합 (Combine) : (주어진 문제 요구 시) 해결된 해답을 통합한다. #분할정복의 종류 이진검색 병합정렬 퀵정렬 ( 호어파티션, 로무토파티션) #이진검색 (Binary Search) :자료의 중앙값과 찾으려는 값의 비교를 통해 다음 검색의 위치를 결정하여 키 값을 찾는 검색 방법 👉 검색 범위를 반으로 줄여가며, 검색 수행 ( 자료 정렬 선행 필수 ) #시간복잡도 ⏰ 입력데이터가 N이라 할 때, 한 번 시..
오늘은 조합 (Combination)에 대해 포스팅하도록 하겠습니다. 학창시절 순열과 조합시간에 배우셨겠지만 개념을 한 번 더 짚고 넘어가볼게요. #조합 📝 nCr : 서로 다른 N개 중 순서의 관계없이 r개를 뽑는 경우의 수 뽑는 순서의 관계없다는 것은, 뽑힌 두 원소들의 위치가 구분되지 않는다는 뜻입니다. 이는 순열과는 구분되는 조합의 중요한 특성입니다. 그럼 재귀함수를 활용한 구현 코드를 볼까요? #구현_재귀함수1 💻 함수호출 부분 N-R+sidx를 통해 sidx에 따른 반복문의 구간을 변경시키는 것이 핵심 로직입니다. import java.util.Arrays; public class 조합1재귀함수 { // 데이터 배열 static String[] 자동차부품 = {"토크컨버터","터보자처부품","..
안녕하세요 오늘은 부분집합에 대한 간단한 설명 및 구현 코드를 통해 코드로 수학시간에 배웠던 부분집합을 새롭게 느껴보려고 합니다. 부분집합 (Powerset) 학창시절 수학의 정석을 펼치면 늘 1단원에 있던, 집합 저희는 모두 1단원 반복문에 갇혀 나오지 못한 경험이 있으니 집합에 대해서 다들 알고 계시겠죠? 부분집합은, literally 어떤 집합의 부분들에 대한 집합입니다. 나만의 라면 레시피를 만든다고 가정해보겠습니다. 들어갈 수 있는 재료는 다음과 같습니다. {치즈, 계란, 대파, 새우, 홍합} 이제 이 재료들의 부분집합을 계산한다면, 각 재료들에 대해 들어가는 경우와 들어가지 않는 경우를 나누어 2*2*2*2*2 = 32 그럼 이제 32가지의 집합들을 출력하는 코드를 구현해보겠습니다. 반복문을 ..
안녕하세요 오늘은 백트래킹에 대한 포스팅을 작성해보겠습니다. 목차 1. 백트래킹 기법 2. DFS와의 차이점 3. 대표적 문제예시 4. N-Queen 코드 한 줄 요약 백트래킹은 모든 후보 검사가 아니다, 즉 완전탐색이 아니다. 1. 백트래킹 기법 어떤 노드의 유망성을 점검한 후 에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 간다. 가지치기(pruning): 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다. 2. 백트래킹과 DFS와의 차이 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써, 시도 횟수를 줄인다. 깊이 우선 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단할 수 있다. N! 가지의 경우..
*본 포스팅은 BFS에 대한 학습을 목적으로 작성되었습니다. 탐색의 방법을 고민할 때, 전체 노드를 모두 탐색하는 완전 탐색 방법으로 BFS와 DFS가 있습니다 이 두 가지 방법은 완전 탐색을 한다는 공통점이 있지만, 탐색의 순서에 큰 차이가 있습니다. 따라서 주어진 문제에 따라 어떤 방식이 더 효율적일지 판단할 수 있어야 합니다 오늘은 먼저 너비우선탐색 BFS에 대해 자세히 알아보겠습니다. BFS (Breadth First Search) 너비우선탐색,루트 노드의 자식노드들을 먼저 차례로 방문한 후에, 방문했던 자식 노드 기준, 다시 해당 노드의 자식 노드를 차례로 방문하는 탐색 알고리즘의 한 방법입니다. 횡방향을 우선적으로 탐색합니다. 구현 방법 BFS의 경우 노드 하나를 탐색할 때, 같은 너비에 있는..
