알고리즘

LIS (Longest Increasing Subsequence)가장 긴 증가하는 수열 (최장 증가 부분 수열)원소가 n개인 배열의 일부 원소를 골라내서 새로 만든 수열을 부분 수열 이라고 하며, 그 수열 중 각 원소가 이전 원소보다 크다는 조건(오름차순)을 만족하고, 그 길이가 최대인 부분 수열  사진의 왼쪽 부분은 `[1, 4, 3, 7, 11]` 이라는 배열에서 만들 수 있는 첫번째 조건을 만족하는 부분 수열들입니다.그중 가장 최대 길이인 `[1, 4, 7, 11]`, `[1, 3, 7, 11]` 이 LIS이며, 길이는 4입니다. LIS를 구현하는 방법은 대표적으로 DP와 이분탐색이 있습니다.DP는 O(N^2) 시간 이분탐색 O(NlogN) 시간입니다.LIS 구현 - DP구현하기 전에 짚고 넘어가야..

알고리즘 개념: 유니온-파인드유니온 파인드에 대해 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천합니다.[알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법 [알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법유니온 파인드 개념상호 배타적 부분 집합(Disjoint Set : 서로소 집합)을 표현할 때 사용여러 노드가 존재할 때 두 노드를 같은 집합으로 묶어주고 같은 집합에 속하는지 판별 연산•Union (합집합)mint10.tistory.com 백준 20040번 사이클게임 https://www.acmicpc.net/problem/20040예제 보려면 더보기 클릭더보기예제 입력 16 50 11 22 35 40 4예제 출력 10예제 입력 2 6 50 11 21 ..

알고리즘 개념: 유니온-파인드유니온 파인드에 대해 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천합니다.[알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법 [알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법유니온 파인드 개념상호 배타적 부분 집합(Disjoint Set : 서로소 집합)을 표현할 때 사용여러 노드가 존재할 때 두 노드를 같은 집합으로 묶어주고 같은 집합에 속하는지 판별 연산•Union (합집합)mint10.tistory.com 백준 1976번 여행 가자https://www.acmicpc.net/problem/1976 예제 보려면 더보기 클릭더보기예제 입력 1330 1 01 0 10 1 01 2 3 예제 출력 1YES문제풀이  i번째 줄의 j..

알고리즘 개념: 유니온-파인드유니온 파인드에 대해 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천합니다.[알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법 [알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법유니온 파인드 개념상호 배타적 부분 집합(Disjoint Set : 서로소 집합)을 표현할 때 사용여러 노드가 존재할 때 두 노드를 같은 집합으로 묶어주고 같은 집합에 속하는지 판별 연산•Union (합집합)mint10.tistory.com 백준 1717번 집합의 표현https://www.acmicpc.net/problem/1717예제 보려면 더보기 클릭더보기예제 입력 17 80 1 31 1 70 7 61 7 10 3 70 4 20 1 11 1 1예제 출..

유니온 파인드 개념상호 배타적 부분 집합(Disjoint Set : 서로소 집합)을 표현할 때 사용여러 노드가 존재할 때 두 노드를 같은 집합으로 묶어주고 같은 집합에 속하는지 판별 연산•Union (합집합) : 노드 x가 포함된 부분 집합과 노드 y가 포함된 부분집합을 합치는 연산•Find (x): 노드 x가 포함된 부분집합을 찾는 연산  최적화 기법1. Path Compression2. Union by Rank (Union by Height)3. Weighted Rule (Union by Size)  유니온 파인드구현초기화부모 노드를 지정할 parent 배열 선언 (코드로 구현할땐 편하게 p로 선언하겠다)parent를 자기 자신으로 지정하여 초기화n개의 원소가 각각 하나의 부분집합 이룸for(int ..

알고리즘 분석 정확성(correctness): 가능한 입력에 대해서 항상 옳은 답을 출력하는가? 자원(resources): 얼마나 많은 자원을 사용하는가? 자원은 알고리즘 실행 시간과 필요한 메모리의 양이 있다. 이 자원을 측정하기 위해 만든 것이 가상의 컴퓨터 RAM (Random Access Machine) 모델순차적으로 수행되는 보통의 컴퓨터에 기반을 두고 있다. -> 직렬구조로 명령어가 사용된 개수에 따라 달라질 수 있다.사칙연산, 비교, 치환 등 간단한 명령어를 가지고 있는데 이 연산을 모두 단위 시간에 수행할 수 있다고 가정한다. 실제 컴퓨터와 마찬가지로 정수의 고정된 길이(32bit, 4byte)로 표현한다무한한 양의 메모리를 가지며, 단위 시간에 메모리에 접근할 수 있다고 가정한다알고리즘 ..