kark's

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 조건 수열의 크기는 1

해당 카테고리는 가장 긴 부분수열만 다룰예정 위와같은 수열이 있을때 가장 길게 증가하는 수열은 10 20 30 50 으로 이루어진다. 이처럼 여러 문제의 조건에 따라 어떻게 접근하는지에 대해 정리해볼 예정이다.

동적 계획법은 복잡한 문제를 여러개의 간단한 문제로 분리해 부분문제를 해결함으로 복잡한 문제의 답을 구하는 방법을 의미한다. 핵심 이론은 ① 큰 문제를 작은 문제로 나눈다. ② 작은 문제들이 반복되고, 작은문제들의 결과값은 항상 같아야한다. ③ 모든 작은문제는 한번만 계산돼 DP 테이블에 저장한 뒤 재사용할때는 이 테이블을 이용한다 동적계획법에는 두가지 방식 탑다운 방식과 , 바텀업 방식으로 나눠진다. 탑다운 문제를 파악하고 점차 내려오는 방식으로, 주로 재귀함수 형태로 코드를 구현한다. 이 방식은 코드의 가독성이 좋고, 이해하기 편한 장점이 있다. int[] memo; int Fibo(int n) { if (memo[n] != -1) return memo[n]; if (n

메모이제이션은 동적 프로그래밍 기법의 일환으로, 이전에 계산된 결과를 저장해두고 필요할때 재사용해 중복 계산을 피하는 최적화 방법이다. 예로, 재귀적으로 피보나치의 수를 구할때 같은값을 여러번 계산하는 것을 메모이제이션으로 방지할수 있다. 기본 재귀함수의 경우 어떠한값이 필요할때 비효율적인 중복되는 계산을 여러번 처리해야한다. 메모이제이션 기법을 사용함으로써 한번 계산된결과를 저장해둔 뒤에 똑같은 계산결과가 필요할때 계산과정을 거치지 않고 필요한 값을 바로 불러오는 방법이다. 이처럼 눈에 보이는 장점과 단점이 있는데, 장점이라면 피보나치의 수처럼 계산 비용이 높은 경우 프로그래밍의 성능을 개선시킬수 있다는점 단점이라면 추가적인 메모리가 필요한점이다. 사용해야하는경우는 비용과 이익을 고려해봐야 하겠지만 보..

이진트리란 하나의 노드가 있을때, 자식노드가 2개 이하인 트리를 말한다. 자식노드가 3개라면 이진트리라 부를수 없다. 트리를 사용하는 이유는 데이터를 계층적으로 구성하며 효율적으로 관리하기 위해 사용된다. 계층적 구조를 이룸으로써 빠른 검색, 삽입, 삭제가 가능하다. 이러한 트리구조에서 모든 노드를 빠르게 확인하거나, 처리를 하기위해선 순회 방법을 알아야한다. 순회 방법으로는 전위순회 중위순회 후위순회가 있다. 전위순회 Preorder , 중위순회 Inorder , 후위순회 , Postorder 각 접두사를 확인해보면 Pre, In, Post 로 앞에 , 안에 , 뒤에 로 유추할수 있다. 단어의 각 위치는 트리의 Root의 위치를 의미한다. 위와 같은 간단한 트리가 있을때, Root는 A 로 Left는 ..

함수 안에서 자기 자신의 함수를 호출되는 형태를 의미 재귀를 사용함으로 복잡한 문제를 간단하게 해결할수 있다. 재귀함수는 반복적인 작업을 수행할때 반복문을 사용하는 대신 자기 자신을 호출해 문제를 해결한다. 재귀 함수는 보통 2개의 단계로 구성된다. ① 기저조건 재귀호출을 멈추는 조건을 의미 이 조건이 없다면 함수는 무한하게 호출되므로 프로그램이 정상적으로 작동되지 않는다. ② 재귀단계 자기 자신을 호출하는 부분이다. 이구간을 통해 문제의 규모를 줄여가며, 최종적으로 ① 기저조건을 만나 재귀 호출이 종료되게된다. 장점 복잡한 문제를 간결한 코드로 작성할수 있으며 반복문보다 좀더 직관적일수도 있다. 단점 호출이 많아지면 스택 오버플로우가 발생될수있음 깊은 재귀의 경우 스택 메모리사용량이 증가된다. 시각화와..

프림 알고리즘또한 MST 를 해결하는 알고리즘이다. 이 알고리즘의 특징은 그리디한 방식으로 문제를 접근하며, 프림 알고리즘은 어떠한 자료구조를 사용하는지에 따라 효율성이 달라진다. Priority Queue 를 활용하면 간선의 선택을 효율적으로 할수있고 이경우 시간복잡도는 O((V+E log V)) 가 된다. ① 시작 정점을 기반으로 인접한 정점을 확인한뒤 우선순위 큐에 가중치 기준으로 데이터를 넣어준다. 이때 시작 정점은 방문된 상태라고 표기해준다. ② 큐에서 추출된 정점을 방문으로 표기해준뒤 인접한 정점을 확인한뒤 ①의 과정과 마찬가지로 큐에 넣어준다. ③ 위 과정을 반복하며 모든 정점을 방문하게 되면 MST가 구해진다. 시작 1번 정점으로 부터 인접한 정점과 가중치를 확인 큐에 넣어주고 1 정점은 ..

탐욕법으로 매순간 주어지는 상황에 가장 답이 될것같은 해를 선택하는 방식의 알고리즘 수행과정 ① 현재 상태에서 가장 좋은 해를 선택 ② 선택된 해가 문제의 조건에 벗어나진 않는지 확인 ③ 현재까지의 선택한 해(집합) 이 전체적인 문제를 해결할수 있는지 확인하며, 해결되지 않을것같다면 ① 로 다시 되돌아간다. 위의 표처럼 각 화폐로 800원을 만들되, 가장 적은 수량의 화폐로 800원을 만들어야한다라고 가정해보자. 가장 큰 단위의 화폐부터 확인해보면, 800원을 만들수있는 가장큰 단위의 화폐는 500원으로 확인된다. 그리디한 방식으로 바로 500원을 선택해준다. 이후 만들어야 하는 금액은 300원으로 500원으로는 300원을 초과하기에 적합하지 않다. 다음으로 큰화폐를 조회하며 탐색을 이어간다. 문제 ht..

신장 트리는 그래프 내 모든 정점을 거치며 사이클이 없는 트리다. N개의 정점이 있다면 간선의 수는 N-1 로 구성된다. 최소 신장트리란 각 간선의 비용을 최소화하여 구성된 모든 정점을 거치는 트리이다. 이번 글은 크루스칼(Kruskal) 알고리즘으로 해결한다. 크루스칼 알고리즘은 MST를 해결하기 위한 방법중 하나이며, 크루스칼 알고리즘 방식으로 문제를 접근하기 위해서는 유니온 파인드 자료구조를 활용해야한다. 크루스칼 알고리즘은 모든 간선의 가중치를 오름차순으로 정렬하여 순서대로 간선을 선택하며 트리를 추가하는 방식으로 작동한다. 이 알고리즘의 효율성은 간선을 정렬하는 과정과, 사이클을 형성하는지 검사하는 과정에 크게 의존된다. 간선정렬 O(E log E) 유니온-파인드 사이클형성 검사는 거의 상수시간..

해당 알고리즘 설명은 자료구조탭의 'DisjointSet 서로소집합' 글 참조 https://kark.tistory.com/15 서로소집합 DisjointSet 각 원소가 집합을 이루게 하거나, 집합을 관리하기 위해 사용되는 자료구조 각 원소가 어떤 집합에 속하는지 빠르게 찾아내고 두개의 집합을 하나로 합치는 연산을 지원한다. 최소 신장트리 알 kark.tistory.com 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www...