728x90 Do it! 알고리즘 코딩 테스트 자바 편26 Day-17 다익스트라 1. 다익스트라 알고리즘 그래프에서 출발 노드와 모든 노드 간의 최단 거리를 구하는 알고리즘이다. 시간 복잡도는 O(에지 수 * log 노드 수)이다. 2. 다익스트라 과정 인접 리스트로 그래프 구현 최단 거리 배열을 만들고 출발 노드는 0, 그 외 노드는 무한으로 초기화 최단 거리 배열에서 값이 가장 작은 노드 선택 선택한 노드에 연결된 노드의 값을 Min(선택 노드 최단 거리 값 + 에지 가중치, 연결 노드 최단 거리 값)으로 업데이트 모든 노드가 선택될 때까지 과정 3, 4를 반복 3. 예제 문제 [1753] 최단경로 (JAVA) # 문제 설명 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. .. 2024. 4. 12. Day-16 위상 정렬 1. 위상 정렬 위상 정렬(topology sort)는 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 시간 복잡도는 O(노드 수 + 에지 수)이다. 항상 같은 값으로 정렬되지 않는다. (결과가 다를 수 있음) 2. 위상 정렬 과정 자기 자신을 가리키는 에지의 개수를 나타낸 진입 차수 배열을 생성 진입 차수가 0인 노드를 선택하고 정렬 배열에 저장 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 감소 모든 노드가 정렬 배열에 저장될 때까지 과정 2, 3을 반복 3. 예제 문제 [2252] 줄 세우기 (JAVA) # 문제 설명 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방.. 2024. 4. 12. Day-15 유니온 파인드 1. Union, Find 연산 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산 노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b)는 A ∪ B이다. 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산 노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다. 위 두 연산으로 구성되어 있는 알고리즘이 유니온 파인드이다. 2. 유니온 구현 1차원 배열을 이용하여 유니온 파인드를 표현한다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 2개의 노드를 선택해 union 연산을 수행한다. union(1, 4)의 경우, 4번 노드의 대표 노드를 1번 노드로 하여 연결한다. union(4, 6)의 경우, 6번 노드.. 2024. 4. 10. Day-14 그래프의 표현 1. 에지 리스트 에지를 중심으로 그래프를 표현한다. 구현이 쉽다. 특정 노드와 관련되어 있는 에지를 탐색하기가 어렵다. 벨만 포드, 크루스칼 알고리즘에 사용한다. 가중치가 없는 그래프인 경우 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 1에서 2로 가는 에지는 [1, 2]로 표현한다. 가중치가 있는 그래프인 경우 배열에 출발 노드, 도착 노드, 가중치를 저장하여 에지를 표현한다. 1에서 2로 가는 가중치가 8인 에지는 [1, 2, 8]로 표현한다. 2. 인접 행렬 2차원 배열을 자료구조로 이용하여 노드 중심으로 그래프를 표현한다. 구현이 쉽다. 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다. 노드 개수가 많은 경우 사용할 수 없다. 노드 개수가 5이므로 5 x 5 행렬을 사용.. 2024. 4. 10. Day-12 오일러 피 1. 오일러 피 오일러 피 함수 P[N]은 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 서로소란 공약수가 1 밖에 없는 수를 의미한다. 2. 오일러 피 원리 오일러 피 함수의 원리는 소수 구하기에서 사용한 에라토스테네스의 체와 비슷하다. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화 2부터 시작해 현재 값이 소수이면, 현재 값의 배수에 해당하는 수에 P[i] = P[i] - P[i] / K 연산을 수행 배열의 끝까지 과정 2를 반복 3. 예제 문제 [11689] GCD(n, k) = 1 (JAVA) # 문제 설명 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 n (1 ≤ n ≤ .. 2024. 4. 7. Day-13 확장 유클리드 호제법 1. 확장 유클리드 호제법 확장 유클리드 호제법은 방정식의 해를 구하기 위해 사용된다. 해를 구하고자 하는 방정식은 ax + by = c 이다. 위 방정식은 c가 a, b의 최대 공약수의 배수인 경우에만 정수해를 가진다. 즉, c의 최솟값이 GCD(a, b)이다. 2. 확장 유클리드 호제법 구현 a와 b의 최대 공약수를 구해 c를 gcd로 둔다. a, b로 유클리드 호제법을 반복 실행하며 몫과 나머지를 저장한다. 나머지가 0이 될 때까지 반복한다. 반복으로 구한 나머지와 몫을 이용하여 x = y', y = x' - y' * q를 계산한다. x', y'는 이전 x, 이전 y를 의미하고, q는 현재 보고 있는 몫을 의미한다. 처음 시작하는 x, y는 x', y'를 1, 0으로 설정한다. 구한 x, y에 c를.. 2024. 4. 6. Day-13 유클리드 호제법 1. 유클리드 호제법 두 수의 최대 공약수를 구하는 알고리즘이다. % 연산을 사용하여 구현한다. 2. 유클리드 호제법 구현 '큰 수 % 작은 수' 연산을 수행 '작은 수 % 과정 1의 결과값' 연산을 수행 나머지가 0이 되는 순간의 작은 수가 최대 공약수이다. 3. 예제 문제 [1934] 최소공배수 (JAVA) # 문제 설명 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 6 spicyrisotto.tistory.com [1850] 최대공약수 (JAVA) # 문제 설명 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약.. 2024. 4. 4. Day-12 소수 구하기 1. 소수 소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. 같은 의미로 1과 자기 자신 외에 약수가 존재하지 않는 수이다. 2. 에라토스테네스의 체 원리 에라토스테네스의 체를 이용하여 소수인지 판별할 수 있다. 구하고자 하는 소수의 범위만큼 1차원 배열 생성 2부터 시작하며 현재 숫자가 지워지지 않았으면, 현재 선택된 숫자의 배수를 배열을 탐색하며 삭제 현재 선택한 숫자는 지우지 않음 배열의 끝까지 과정 2를 반복 반복이 끝난 후 남아 있는 수는 모두 소수이다. 3. 예제 문제 [1929] 소수 구하기 (JAVA) # 문제 설명 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M .. 2024. 4. 4. Day-10,11 그리디 알고리즘 1. 그리디 알고리즘 (탐욕법) 현재 상태에서 보는 선택지 중 최선의 선택지를 고르는 알고리즘이다. 탐욕법의 결과는 주어진 선택지에서 최적의 결과를 보장해주는 것은 아니다. 2. 그리디 알고리즘 과정 현재 상태에서 가장 최선인 해를 선택 선택한 해가 문제의 조건에 부합하는지 검사 현재까지 선택한 해 집합이 문제를 해결할 수 있는지 검사, 해결할 수 없으면 1로 돌아가 같은 과정을 반복 3. 예제 문제 [11047] 동전 0 (JAVA) # 문제 설명 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구 spicyrisotto.tistory.com [2839] 설탕 배달 (JAVA.. 2024. 4. 3. 이전 1 2 3 다음 728x90
