tonirr

동적프로그래밍 동적프로그래밍 방법의 원리 문제의 크기가 작은 소문제에 대한 해를 저장해놓고, 이를 이용해서 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근방법 각각의 소문제는 원래의 문제와 동일하지만 입력의 크기만 줄어듦 입력의 크기가 아주작은 단순한 문제가 되면 쉽게 해를 구할 수 있고 이런 소문제의 해는 다시 사용될 수 있으므로 테이블에 저장 해당 소문제의 해가 필요할 때마다 테이블에서 결과를 바로 이용 동적 프로그래밍(동적 계획법) 해를 구축하는 테이블을 이용함 최적화 문제에 사용됨(최소값, 최대값 찾기) 분할 정복 방법 하향식 접근 방법 상위 레벨의 큰 문제를 순환적으로 부분배열로 분할하고 이들의 해를 결합해서 원래 문제의 해결하는 방법 분할된 작은 문제들은 서로 독립적 이진탐색, ..

import java.util.HashMap; import java.util.Map; class Solution { public boolean solution(String[] phone_book) { boolean answer = true; Map map = new HashMap(); for(int i=0; i

프로그래머스 고득점 kit 구현 - 완주하지 못한 선수 import java.util.Arrays; class Solution { public String solution(String[] participant, String[] completion) { String answer = ""; Arrays.sort(participant); Arrays.sort(completion); int i; for(i=0; i

전형적인 분할정복 방법이 적용된 알고리즘 분할 배열을 동일한 크기의 두 개의 부분배열로 분할하고 입력 크기 n인 배열을 크기 n/2인 두 부분배열로 분할한다. 정복 각각의 부분배열을 순환적으로 정렬한 후 두 부분배열을 정렬한다. 결합 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만든다. 합병정렬 Merge() Merge(B[], C[], n, m){ i=j=k=0; while(i O(in) 최솟값 찾기 각 데이터를 하나씩 모두 비교하는 방법 n개의 데이터에 대해서 적어도 (n-1)번 비교가 필요 -> O(n) 최솟값과 최댓값 모두 찾기 방법1: 최솟값 찾은 후 최댓값 찾기 n개의 데이터에서 최솟값을 찾는데 (n-1)번 비교 + (n-1)개의..

분할정복 방법 순환적으로 문제를 푸는 하향식 접근방법 주어진 문제의 입력을 더이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고 분할된 작은 문제들을 각각 해결한 후 이 해들을 결합해서 원래 문제의 해를 구하는 방식 특징 분할된 작은 문제는 원래 문제와 동일 단, 입력 크기만 작아짐 분할된 작은 문제는 서로 독립적 순환적 분할 및 결과 통합이 가능 분할정복 방법의 처리 단계 각 순환 호출마다 세 단계의 처리과정을 거침 분할: 주어진 문제를 여러 개의 작은 문제로 분할한다. 정복: 작은 문제를 순환적으로 분할, 만약 작은 문제가 더이상 분할되지 않을 정도로 크기가 충분히 작다면 순환호출 없이 작은 문제의 해를 구함 결합: 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함 ..

주어진 문제를 풀기위한 명령어들의 단계적 나열 입출력 0개 이상의 외부 입력 -> 1개 이상의 출력 명확성 각 명령은 모호하지 않고 단순 명확해야 함 유한성 한정된 수의 단계를 거친 후에는 반드시 종료 유효성 모든 명령은 컴퓨터에서 수행 가능해야함 주어진 문제에 대한 결과를 생성하기위해 모호하지 않고 간단하며 컴퓨터가 수행가능한 일련의 유한개의 명령들을 순서적으로 구성한 것 실용적관점 효율적이어야 함 알고리즘 생성단계 설계 -> 표현기술 -> 정확성 검증 -> 효율성 분석 알고리즘 표현/기술 방법 일상언어 의사코드 순서도 알고리즘의 설계 알고리즘(1): 값들을 하나씩 모두 비교해가면서 찾는 방법 알고리즘(2): 토너먼트 방식 최대값찾기에서 1번과 2번중 어떤것이 더 효율적일까? 효율성을 찾는 기준은 비교..

자료구조와 알고리즘의 관계 자료구조 컴퓨터에서 데이터 사이의 논리적 관계를 표현하고 조직화하는 방법 프로그램 2^i 높이 h인 이진 트리의 최대 노드의 개수-> 2^h - 1 n0 = n2 + 1(n0: 단말 노드의 수, n2: 차수가 2인 노드의 수) 포화(perfect)이진트리 완전(complete)이진트리 맨마지막 레벨전까지는 포화이진트리이며 맨 마지막레벨에서는 빈자리 전(full)이진트리 각 노드의 차수가 0 또는 2인 경우 균형(balanced) 이진트리 왼쪽 서브트리와 오른쪽 서브트리의 높이가 1이내인 것 경사(skewed) 이진트리 각 노드의 가지가 하나밖에 없는 것 그래프 V: 정점의 집합, E: 간선의 집합 무방향 그래프, 방향 그래프 그래프의 구현 인접행렬, 인접 리스트 정리 기본자료구..

교집합 timelimit 난 코드 #include /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; int main() { //freopen("input.txt", "rt", stdin); int n, m, i, j, k, l, tmp, p1, p2, p3; int a[101], b[101], c[201]; scanf("%d", &n); for(i=1; i