알고리즘89 5주차 알고리즘 - 최소신장트리 (MST) - MST : Minimum Spanning Tree - 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법 : 크루스칼, 프림 노드와 간선정보가 주어졌을 때 최소가 되게 노드들을 한 번만 연결하는 방법 MST 관련 문제들은 내부 알고리즘은 동일. 문제 파악한 후 MST 형태인 것만 떠올면 풀 수 있음 - 크루스칼 (Kruskal) 알고리즘 · 간선 중 최소 값을 가진 간선부터 연결 · 사이클 발생 시 다른 간선 선택 · 주로 간선 수가 적을 때 사용 · O(Elog E) - 간선 정보들을 오름차순 Sorting 작업 필요 - 사이클 발생 체크하는 Union-Find 테이블 초기 : 각 자기 자신으로 초기화 1. 처음에 가장 작은 가중치인 1을 선택해서 1 - 3 노드를 연결하면 3의 부모노드는 연결.. 2023. 8. 10. 5주차 알고리즘 복습 - 다이나믹 프로그래밍 다이나믹 프로그래밍 (Dynamic Programming) DP , 동적 계획법 - 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 재활용하여 문제의 답을 구함 여기까지는 분할정복인데 여기서 차이가 있음. - 중간 계산 결과를 기록하기 위한 메모리가 필요 - 한 번 계산한 부분을 다시 계산하지 않아 속도가 빠름 * 다른 알고리즘과의 차이점 - 분할정복과의 차이점 : 분할정복은 부분문제가 중복되지 않음 : DP는 부분문제가 중복되어 재활용에 사용 - 그리디 알고리즘과의 차이점 : 그리디는 순간의 최선을 구하는 방식 (최적해) : DP는 모든 방법을 확인 후 최적해 구하는 방식 -> 그 과정에서 중복된 연산을 하지 않음 * 그리디가 DP보다 빠름 (당연함) 반드시 최적해를 구.. 2023. 8. 6. 5주차 알고리즘 복습 - 그리디 매순간 현재 기준으로 최선의 답을 선택해 나가는 기법 - 빠르게 근사치를 계산할 수 있다. - 결과적으로는 최적해가 아닐 수 있다. * 정렬 안 된 상태로 그리디 사용 불가 그리디 알고리즘 적용 조건 : 이 두 가지 만족시 적용 가능 * 최적부분 구조 (Optimal substructure) : 전체 문제의 최적해는 부분 문제의 최적해로 이어짐. * 탐욕적 선택 특성 (Greedy Choice Property) 지금 선택이 다음 선택에 영향을 주지 않음. -> 현재 마주하는 문제가 미래에 영향을 받아 최적이 아니게 바뀌지 않는다 ! 이 개념이 좀 헷갈렸는데 500 100 50 10 같은 완벽하게 그리디 적용할 수 있는 것도 내가 지금 500원을 고르냐 안 고르냐에 따라서 100원의 선택값이 달라지니까 영.. 2023. 8. 6. (백준/자바) 힌트문제3 05. 그리디 - 백준 11047번 문제 : 동전 0 11047번: 동전 0 (acmicpc.net) 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 그리디 개념 복습 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { public static void main (String args[]) throws I.. 2023. 8. 6. (백준/자바) 힌트문제3 04. 다이나믹 프로그래밍 - 백준 1890번 문제 : 점프 1890번: 점프 (acmicpc.net) 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 다이나믹 프로그래밍... 공부 하고 와야겠다. 8/8 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Main { static .. 2023. 8. 6. (백준/자바) 백준 3273번 문제 : 두 수의 합 3273번: 두 수의 합 (acmicpc.net) 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 투포인터 개념 아예 다져버릴려고 문제 하나 더 풀어보기로 했다. 특정 target 값을 만족하는 경우의 수 구하는 문제 * 생각해야할 점 1. i < j 이므로 정렬하면 안 됨. 2. 단 두 수의 합이 target이 되어야 하므로 p1, p2 값을 그에 따라 조정. p1 < p2임에 유의 그 안에 어떤 쌍이든 가능한 것임. 인접한 것이 아니어도 됨. impo.. 2023. 8. 6. (백준/자바) 힌트문제3 03. 투 포인터 - 백준 2003번 문제 : 수들의 합2 2003번: 수들의 합 2 (acmicpc.net) 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net * 생각해야 할 점 : 1. 수열을 정렬하면 안됨. 2. p2하나만 써도 됨.p1을 for의 i가 대신 해줌. for문 안에 while문으로 조건 검사 total += arr[p2++] 을 하면서 중간에 total == M이면 다음 p1으로 넘어감 나는 while문 밖에 total==M인 조건 검사를 해줬는데 틀렸다고 함. p2한 번이 씹히는 거 같음. import ja.. 2023. 8. 6. (백준/자바) 힌트문제3 02. 2차원배열 - 백준 2167번 문제 : 2차원 배열의 합 2167번: 2차원 배열의 합 (acmicpc.net) 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 간단하게 풀었다. 근데 다른 알고리즘 같은 거 없이 그냥 단순 이중 for문 문제는 아닐 것 같은데 ... import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class TwoArray_02 {.. 2023. 8. 6. (백준/자바) 힌트문제3 01. 팰린드롬 - 백준 1254번 문제 : 팰린드롬 만들기 1254번: 팰린드롬 만들기 (acmicpc.net) 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 너무 어렵게 생각한 것 같은데 생각보다 간단한 문제였다. 주어진 문자열이 처음부터는 아니더라도 중간 어딘가 ~ 끝에 팰린드롬이 있을 수도 있으니까 문자열 길이만큼 subString으로 잘라서 팰린드롬인지 검사하고 팰린드롬이라면 그 부분을 뺀 자른 인덱스 i 만큼 문자열 길이에 더해주면 되고 팰린드롬이 전혀 없었으면 기존 문자열 길이에 * 2 해야한다. import java.io.BufferedReader; impo.. 2023. 8. 6. 이전 1 2 3 4 ··· 10 다음 728x90
