✔ 그래프의 표현 엣지 리스트 엣지를 중심으로 그래프를 표현 가중치가 없는 그래프라면, 배열의 2개의 행에 출발 노드, 도착 노드를 저장하여 엣지를 표현 가중치가 있는 그래프라면, 배열의 3개의 행에 출발 노드, 도착 노드, 가중치를 저장하여 엣지를 표현 엣지 리스트는 구현하기 쉽지만, 특정 노드와 관련되어 있는 엣지를 탐색하기 쉽지 않음 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않음 인접 행렬 노드 중심으로 그래프를 표현 가중치가 없는 그래프라면, 출발 노드에서 도착 노드로 향하는 엣지를 인접 행렬의 출발 행 도착 열에 1을 저장하여 노드를 표현 가중치가 있는 그래프라면, 출발 노드에서 도착 노드로 향하는 엣지를 인접 행렬의 출발 행 도착 열에 가중치를 저장하여 노..
✔ 그래프의 기본 유니온 파인드 그래프의 사이클이 생성되는지 판별하는 알고리즘 위상 정렬 사이클이 없는 방향 그래프일 때, 그래프의 각 노드의 순서를 찾는 알고리즘 순서 (정렬) 값이 유일하지 않다는 특징 수강 신청, 게임 빌드 오더 문제에 활용 다익스트라 시작점에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘 음수 간선이 존재하지 않아야 함 벨만-포드 시작점에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘 음수 간선이 존재해도 됨 음수 사이클이 있는지 확인하는 문제에 활용 플로이드-워셜 임의의 모든 노드에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘 시간 복잡도가 좋지 않음 최소 신장 트리 모든 노드를 연결하는데 최소의 비용(가중치)으로 간선을 연결하는 알고리즘 유니온 파인드를 ..
✔ 유클리드 호제법 유클리드 호제법이란? 두 수의 최대 공약수를 구하는 알고리즘 최대 공약수와 최소 공배수 최대 공약수(GCD)란 두 자연수의 공통된 약수 중 가장 큰 수 최소 공배수(LCM)란 두 자연수의 공통된 배수 중 가장 작은 수 최소 공배수는 두 자연수의 곱 / 최대 공약수 MOD 연산으로 구현하는 유클리드 호제법 큰 수를 작은 수로 나누는 MOD 연산을 수행 앞 단계에서 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택 ✔ 확장 유클리드 호제법 확장 유클리드 호제법이란? 방정식 ax + by = c의 해를 구하는 알고리즘 (a, b, c, x, y는 정수) 이 때 위 방정식은 c % gcd(a, b) = 0인 경우에만 정수해..
✔ 오일러 피 오릴러 피란? 1부터 N까지 범위에서 N과 서로소인 자연수의 개수 서로소란? 공약수가 1 이외에 존재하지 않는 것 오일러 피 함수의 원리 구하고자 하는 오일러 피의 범위만큼 배열을 초기화 2부터 시작해 현재 배열의 값과 인덱스가 같으면 (소수일 때) 현재 선택된 숫자의 배수에 해당하는 수를 배열 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행 예) P[6] 서로소가 될 수 있는 후보의 개수로 초기화 : P[6] = 6 (1, 2, 3, 4, 5, 6) 2의 배수로 인한 후보 탈락 : P[6] = 6 - (6 / 2) = 3 (1, 3, 5) 3의 배수로 인한 후보 탈락 : P[6] = 3 - (3 / 3) = 2 (1, 5) 배열의 끝까지 위를 반복하여 오일러 피 함수를 ..
✔ 소수 구하기 소수란? 1과 자기 자신 외에 약수가 존재하지 않는 수 에라토스테네스의 체 소수를 구하는 대표적인 판별법 현재 코딩 테스트에서 소수를 구하는 일반적인 방법으로 통용 이중 for문을 사용하므로 시간 복잡도가 O(N²) 정도라고 판단할 수 있음 하지만 실제 시간 복잡도는 최적화의 정도에 따라 일반적으로 O(Nlog(logN)) 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문 에라토스테네스의 체 원리 구하고자 하는 소수의 범위만큼 1차원 배열을 생성 1은 소수가 아니므로 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지움 이때 처음으로 선택된 숫자는 지우지 않음 배열의 끝까지 ..
✔ 그리디 그리디란? 현재 알고리즘에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 최적의 해를 보장하지 않으므로 그리드 알고리즘을 선택해야 하는지, 아닌지 고민이 필요 그리디 알고리즘 수행 과정 현재 상태에서 가장 최선이라고 생각되는 해를 선택 현재 선택한 해가 전체 문제의 조건에 벗어나지 않는지 적절성 검사 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사하고 전체 문제를 해결하지 못하면 앞으로 돌아가 반복 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://inf.run/w9Tn
✔ 이진 탐색 이진 탐색이란? 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음 시간 복잡도는 O(logN) 원하는 데이터를 찾을 때 사용하는 가장 일반적인 알고리즘 구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구하는 영역 이진 탐색 과정 현재 데이터의 중앙값을 선택 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터를 선택 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터를 선택 위 과정을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://inf.run/w9Tn
✔ 너비 우선 탐색 너비 우선 탐색이란? 그래프 완전 탐색 기법 중 하나 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 큐 자료구조를 이용하여 구현이 가능 (FIFO) V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(V + E) 목표 노드에 도착하는 경로가 여러 개일때의 최단 경로를 보장할 때 사용 너비 우선 탐색 과정 BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 인접 리스트로 그래프 표현하기 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 방문 배열 초기화하기 시작 노드 큐에 삽입하기 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기 poll을 수행하여 노드 꺼내기 꺼낸 노드를 탐색 순서에 기입하..
