✔ 이분 그래프 [백준 1707] 문제 분석하기 노드의 집합을 2개로 나누는데, 인접한 노드끼리 같은 집합이 되지 않도록 적절하게 임의로 분할해야 함 트리의 경우 사이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문에 항상 이분 그래프가 됨 하지만 사이클이 발생하여 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능하다고 판단할 수 있음 손으로 풀어보기 그래프 데이터를 가중치 없는 인접 리스트로 구현 모든 노드로 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행 DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아닌 것으로 판별 그래프의 모든 노드가 이어져 있지 않고, 여러 ..
✔ 그래프의 표현 엣지 리스트 엣지를 중심으로 그래프를 표현 가중치가 없는 그래프라면, 배열의 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) 배열의 끝까지 위를 반복하여 오일러 피 함수를 ..
✔ 소수 구하기 [백준 1929] 문제 분석하기 N의 범위가 1000000이므로 일반적인 소수 구하기 방식으로 문제를 풀면 시간 초과가 발생 따라서 에라토스테네스 방법으로 문제를 풀이 손으로 풀어보기 첫 번째 인덱스가 0인 것을 고려하여 크기가 N + 1인 배열을 선언한 후 값은 각각의 인덱스값으로 채움 1은 소수가 아니므로 삭제 2부터 N의 제곱근까지 값을 탐색하며 값이 인덱스값이면 그대로 두고, 그 값의 배수를 탐색해 0으로 변경 N이 a * b라고 가정했을 때, a와 b 모두 N이 제곱근보다 클 수 없으므로 N의 제곱근까지만 확인해도 전체 범위의 소수 판별 가능 배열에 남아 있는 수 중 M 이상 N 이하의 수를 모두 출력 슈도코드 작성하기 M(시작 수) N(종료 수) A(소수 배열) for(N만큼 ..
✔ 소수 구하기 소수란? 1과 자기 자신 외에 약수가 존재하지 않는 수 에라토스테네스의 체 소수를 구하는 대표적인 판별법 현재 코딩 테스트에서 소수를 구하는 일반적인 방법으로 통용 이중 for문을 사용하므로 시간 복잡도가 O(N²) 정도라고 판단할 수 있음 하지만 실제 시간 복잡도는 최적화의 정도에 따라 일반적으로 O(Nlog(logN)) 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문 에라토스테네스의 체 원리 구하고자 하는 소수의 범위만큼 1차원 배열을 생성 1은 소수가 아니므로 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지움 이때 처음으로 선택된 숫자는 지우지 않음 배열의 끝까지 ..
✔ 동전 0 [백준 11047] 문제 분석하기 그리디 알고리즘으로 풀 수 있도록 뒤의 동전 가격이 앞에 나오는 동전 가격의 배수가 된다는 조건이 부여되어 반례없이 문제를 해결할 수 있도록 하였음 그러므로 동전을 최소로 사용하여 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 됨 손으로 풀어보기 가격이 큰 동전부터 내림차순으로 K보다 가격이 작거나 같은 동전이 나올 때까지 탐색 탐색을 멈춘 동전의 가격으로 K를 나눠 몫은 동전 개수에 더하고, 나머지는 K값으로 갱신 위 과정을 나머지가 0이 될 때까지 반복 슈도코드 작성하기 N(동전 개수) K(목표 금액) A(동전 데이터 배열) for(N만큼 반복하기) { A 배열 저장하기 } for(N만큼 반복 → N - 1 ~ 0으로 역순으로 반복하기)..
