알고리즘 문제 (기초) (14) 썸네일형 리스트형 알고리즘_LCS 출처 : https://www.youtube.com/watch?v=EtGqdy-9w9M 알고리즘_기초개념_힙 정렬 출처 : https://blog.naver.com/ndb796/221228342808 힙 정렬 힙 정렬은 고급 프로그래밍 기법으로 갈수록 자주 등장하는 개념 힙을 이해해야하고, 그 전에 이진트리의 개념을 이해해야 한다. 이진트리 이진트리란? 모든 노드의 자식 노드가 2개 이하인 노드 (트리의 최상단: 루트 (노드), 트리의 최하단: 리프 (노드)) 완전이진트리 데어터가 루트 노드부터 시작해서 자식 노드가 왼쪽부터 차례대로 들어가는 이진 트리 힙 힙은 최솟값과 최댓값을 완전이진트리를 이용하여 빠르게 찾아내는 트리 부모 노드가 자식 노드보다 무조건 커야된다. 만약에 자식 노드의 값이 크면 부모 노드와 자식 노드를 바꿔준다. (힙 붕괴가 되면 부모,자식 바꿔줌) 시간 복잡도 힙 정렬을 위해 힙 생성 알고리즘을.. 백준 알고리즘_11053번_가장 긴 증가하는 부분 수열_LIS 문제 출처 : https://www.acmicpc.net/problem/11053 우선, 문제를 풀기 전에 LIS의 개념을 이해해야 한다. LIS = Longest Increasing Subsequence Length 가장 긴 증가 수열의 길이 HOW? 어떻게 구하냐!? 알고리즘에선 DP(동적계획법)를 이용하여 구할 수 있다! 예시를 통해서 이해해보자! 3 4 -1 0 6 2 3 주어진 배열은 위와 같다. 3 4 -1 0 6 2 3 1 1 1 1 1 1 1 우선, 밑에 증가 길이를 구할 배열을 준비하고 모두 1로 채워준다. 3 4 -1 0 6 2 3 j i 1 2 1 1 1 1 1 j와 i의 위치를 첫번째와 두번째로 우선 잡아준다. 이 때 j가 위치한 3과 i가 위치한 4를 비교하면 i가 더 크다. i가.. 알고리즘 백준_1463번_1로 만들기_자바_동적계획법(DP) 출처 : https://www.acmicpc.net/problem/1463 이 문제는 dp에 관한 문제이며, dp는 점화식을 세우는 것이 중요 -1, ÷2, ÷3을 이용하여 1로 만드는 연산의 최솟값을 구하는 문제 점화식 입력값을 1로 만드려면, "입력값-1"을 1로 만드는 가장 적은 연산횟수, "입력값÷2를 1로 만드는 가장 적은 연산 횟수", "입력값÷3를 1로 만드는 가장 적은 연산 횟수"를 중 최솟값 + 1이 된다 ----- 가장 중요한 부분! 점화식을 세웠으면 이제 구현을 해보자! (Top-down방식과 Bottom-up방식) 1 Top-down import java.util.Scanner; public class Main{ public static int input, arr[]; public .. 알고리즘_기초개념_병합 정렬 출처 : https://www.youtube.com/watch?v=ctkuGoJPmAE&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=9&t=0s 병합 정렬 병합 정렬은 퀵 정렬과 마찬가지로 분할 정복 방법으로 이용한 알고리즘이다. 퀵 정렬은 피벗값에 따라서 최악의 경우 시간 복잡도가 O(N^2)가 나오지만 병합 정렬은 일정하게 O(N*logN)이라는 시간복잡도를 가진다. 병합 정렬은 기본 아이디어는 '반으로 나눠두고 나중에 합쳐주자'이다. 병합 정렬은 '기존의 데이터를 담을 배열 공간이 필요하다는 것에서 메모리 활용이 비효율적이다. 병합 정렬 알고리즘 진행 과정 1. 7 6 5 8 3 5 9 1 일단 계속 반으로 나누어 한 개가 될 때까지 나누어준다. (나누어진 1개.. 알고리즘_기초개념_퀵정렬 출처 : https://www.youtube.com/watch?v=O-O-90zX-U4&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=6&t=60s 퀵 정렬 선택, 버블, 삽입 정렬은 복잡도가 O(N^2)이므로 데이터 갯수가 많을수록 데이터 처리속도가 기하급수적으로 증가한다. 이러한 단점을 극복한 대표적인 알고리즘이 퀵 정렬 알고리즘이다. 퀵 정렬 알고리즘의 시간 복잡도는 O(N*logN)이다. 퀵 정렬은 기준값을 사용하여 왼쪽과 오른쪽으로 나누어 방법을 이용 (분할 정복) 퀵 정렬 알고리즘 진행과정 3 7 8 1 5 9 6 10 2 4 배열에서 가장 앞에 있는 값을 기준값으로 사용 3 7 8 1 5 9 6 10 2 4 그 다음에 왼쪽에서부터는 기준값(3)보다 큰 값을.. 알고리즘_기초개념_삽입정렬 참고 url : https://www.youtube.com/watch?v=16I9Z7bS1iM&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=4 삽입 정렬 각 숫자를 앞의 숫자들과 비교하여 적절한 위치로 삽입하는 방법 삽입 정렬 알고리즘 진행 과정 1 10 5 8 7 6 4 3 2 9 1은 가장 앞에 있기 때문에 앞 쪽으로 삽입할 위치가 없기 때문에 제자리 1 10 5 8 7 6 4 3 2 9 10은 앞에 1이 있지만, 1보다 크기 때문에 제자리 1 10 5 8 7 6 4 3 2 9 1 5 10 8 7 6 4 3 2 9 5는 앞에 1과 10이 있고 1보다 크고 10보다 작으므로 1과 10 사이의 자리로 들어간다. 1 5 10 8 7 6 4 3 2 9 1 5 10 8 7.. 동적 계획법 (Dynamic Programming) 1. 동적 계획법? 동적 프로그램이은 주로 재귀랑 연관이 있다. 동일한 입력을 반복적으로 수행할 때 재귀적 방법보다는 동적 프로그래밍을 사용하는 것이 좋다. 미리 하위 문제의 결과물들을 따로 저장하여 필요할 때마다 다시 계산하는 작업을 피해준다. 그렇기 때문에 동적 계획법은 시간복잡도를 줄여준다. 피보나치 수열이 가장 대표적인데, 재귀적 방법으로는 시간 복잡도(지수)가 높고, 하위 문제들의 해결로 저장하여 최적화 시기키면 시간 복잡성이 선형으로 감소한다. => 재귀적 용법보다는 동적계획법이 시간복잡도가 낮으니 동적계획법을 이용하자! 2. Overlapping Subproblem (계산 중첩) 동적 계획법은! 하위문제들의 해결을 반복적으로 해결해야할 때 주로 사용된다(재귀). 하위 문제들의 계산 결과값을 .. 이전 1 2 다음
