위의 그림과 같이 x1,y1,r1/ x2,y2,r2 가 주어진 경우 겹치는 영역의 넓이를 구하는 방법에 대해 살펴 보도록 하겠습니다.

두 원의 중심과 중심 사이의 거리 d는 피타고라스의 정리에 의해서 

d * d = (x1-x2) * (x1-x2) + (y1-y2)*(y1-y2) 가 됩니다.

여기서 부채꼴의 넓이를 구하는 공식을 살펴 보자.

S(부채꼴의 넓이) = πr2 * x/360 으로 구할 수 있다.

각도를 θ/2π 와 같이 나타낼 수 있으므로

S(부채꼴의 넓이) = πr2 * θ/2π  -------------(1)

여기서 겹치는 영역의 값을 구한다고 하면 다음과 같이 구할 수 있다.

S1(부채꼴 1의 넓이) + S2(부채꼴 2의 넓이)를 먼저 구한다. 

그러면 우리가 구하려고 하는 겹치는 영역의 넓이가 2번 포함된 부채꼴의 합이 된다.

이렇게 구한후 위의 그림과 같이 삼각형 2개의 넓이를 빼 주게 되면 겹치는 영역의 넓이만 남게 된다.

이등변 삼각형의 넓이를 각도를 이용해서 구하는 방법을 살펴 보면 다음과 같다.

 

이 원리에 의해서 

a = c * sinA

b= c*cosA

이므로 

이러한 이등변 삼각형의 넓이를 구하는 방법에 대해 생각해 보자.

θ 를 정확히 2등분하면 θ/2 가 되며 직각이 된다.

여기서 cos(θ/2) = 높이/r 이 된다.

따라서 높이 = r * cos(θ/2) 

sin(θ/2) = (밑변/2)/r 로 나눈 값이므로

밑변 = r * sin(θ/2) * 2

따라서 삼각형의 넓이 =  높이 * 밑변 / 2이므로

r * cos(θ/2) * r * sin(θ/2) * 2 / 2

이렇게 나온것을

삼각함수의 성질

sinθ1cosθ2 = (sin(θ1+θ2) +sin(θ1-θ2))/2

θ1 == θ2 이므로

sin(θ/2)cos(θ/2) = (sin(θ) + sin(0))/2 = sin(θ)/2 로 간소화 할 수 있다.

따라서 r * cos(θ/2) * r * sin(θ/2) * 2 / 2 = r * r * sin(θ/2 * 2)/2 = r * r * sin(θ)/2 

삼각형 면적은 r * r * sin(θ)/2  -------------(2)

이렇게 하면 각도 θ 만 구하면 위의 식에 의해서 겹치는 부분의 면적을 구할 수 있다.

 

다음으로 각도를 구하기 위해 코사인 법칙을 살펴 보자.

참고 : https://ko.wikipedia.org/wiki/%EC%BD%94%EC%82%AC%EC%9D%B8_%EB%B2%95%EC%B9%99

 

코사인 법칙 - 위키백과, 우리 모두의 백과사전

기하학에서, 코사인 법칙(cosine法則, 영어: law of cosines)은 삼각형의 세 변과 한 각의 코사인 사이에 성립하는 정리이다. 이에 따르면, 삼각형의 두 변의 제곱합에서 사잇각의 코사인과 그 두 변의

ko.wikipedia.org

a2 = b2 + c2 - 2bc(cosA)

cosA = (b2+c2-a2)/2bc

와 같이 나타낼 수 있으므로 다음과 같은 형식으로 왼쪽 원 θ1 를 구할 수 있다.

cos(θ1/2) = (r12 + d2 - r22)/(2*r1*d)

θ1/2 = cos^-1 * ((r1^2 + d^2 - r2^2)/(2*r1*d))

오른쪽 원 θ2는 같은 방법으로

cos(θ2/2) = (r22 + d2 - r12)/(2*r2*d)

θ2/2 = cos^-1 * ((r22 + d2 - r12)/(2*r2*d))

으로 구할 수 있다.

이렇게 각도를 찾아 내면 공식에 의해 a,b,c 및 각도에 의한 부채꼴의 넓이 등을 계산 할 수가 있다.

 

이러한 두 원의 영역을 구하는 알고리즘 문제인 백준 7869번의 두 원의 문제를 풀어 보자.

https://www.acmicpc.net/problem/7869

 

7869번: 두 원

첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다.

www.acmicpc.net

 

#include <bits/stdc++.h>


using namespace std;

int main()
{
    double x1,y1,r1,x2,y2,r2;
    cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
    constexpr double pi = acos(-1);

    double d = sqrt( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2));

    double res = 0;
    if(r1+r2<=d) ///영역이 없다.
        res = 0;
    else if(abs(r1-r2)>=d) ///큰원에 작은원이 포함된 경우
    {
        res = pi * min(r1,r2) * min(r1,r2); ///작은 원의 넓이
    }
    else{
        double theta1 = acos( (r1*r1 + d * d - r2 * r2)/(2*r1*d) );
        double theta2 = acos( (r2*r2 + d*d - r1*r1)/(2*r2*d));

        double s1 = (r1 * r1 * theta1) - (r1 * r1 * sin(2*theta1)/2); ///부채꼴 넓이에서 삼각형 넓이를 빼자.
        double s2 = (r2 * r2 * theta2) - (r2 * r2 * sin(2*theta2)/2);
        res = s1 + s2;

    }

    printf("%.3f",res);


    return 0;
}

 

인천 서구 원당컴퓨터학원

원당컴퓨터학원에서는?

1. 4차 산업 시대의 흐름은 컴퓨터를 얼마나 이해하느냐에 따라 삶의 질이 틀려 질 수 있다는 것을 항상 염두에 두고 있습니다.

2. 알고리즘은 프로그래밍의 근원이 되는 문제해결 능력이며, 머신러닝은 IoT등에 의해 모여진 데이터를 활용하는 기법입니다.

3. 이에 따라 초,중,고 학생들이 알기 쉽게 이해하는 인공지능 부터 알고리즘까지 학생들의 실력에 맞춰 수업을 진행중에 있습니다.

4. 현재 초등학생이 고등학생이 되는 때에는 고교학점제 도입에 따라 자신이 전공하고자 하는 특기가 크게 부각 될것입니다.

5. IT 업체중 규모가 큰 곳에서는 코딩테스트(알고리즘테스트)로 블라인드 면접을 수행하는곳이 늘고 있습니다.

6. 미래 IT를 꿈꾸는 학생들의 산실이 되기 위해 항상 최선을 다하는 원당컴퓨터학원이 되겠습니다.

 

※ 정보영재 혹은 인공지능 관련 수업에 관해 궁금하신 분은 문의(032-565-5497) 주세요.

 

 

원당컴퓨터학원 커리큘럼

- OA : 학교 수행 평가에 꼭 필요한 컴퓨터 활용능력 향상

- IT 자격증 과정 : 취업대비,대학생인증제,승진을 위한 국가공인 자격증 취득과정

- 정보영재 : 정보올림피아드 및 알고리즘 대회/소프트웨어특기자전형/디미고 특별전형 대비/코딩테스트 대비를 위한 알고리즘 과정

- 프로젝트반 : 응용프로그래밍/웹프로그래밍/앱프로그래밍 등을 통해 직접 만들어 보면서 컴퓨터 프로그래밍 이해(소프트웨어 학생부종합전형/특성화고(디미고,선린고등) 특별전형대비)

- 인공지능 : 인공지능의 이해 및 실습을 통해 빅데이터 가공(4차 산업 시대의 축이 되는 인공지능 시대를 대비)

- 일반고,과고,영재고,특성화고,컴퓨터학과(SW) 대학생을 위한 내신대비 : python,java,c++,자료구조,알고리즘,이산수학 

 

 

 

 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of http://deborah.tistory.com BlogIcon 데보라 2021.09.03 22:14

    알고리즘에 대한 설명 잘 보고 갑니다.

  2. Favicon of https://heysukim114.tistory.com BlogIcon *저녁노을* 2021.09.04 01:10 신고

    어렵네요.ㅎㅎ
    즐거운 주말 되세요

  3. Favicon of https://xuronghao.tistory.com BlogIcon 空空(공공) 2021.09.04 07:15 신고

    학생들 참고가 되겠습니다 ㅎ

  4. 핑구야날자 2021.09.04 12:24

    요런 알고리즘이 학생들에게 실력을 향상시킬 수 있는 좋은 기회가 아닌가 싶어요

  5. Favicon of https://seunmi1981.tistory.com BlogIcon 구름 달빛 2021.09.04 21:57 신고

    포스팅 잘보고갑니다 시원한 밤 보내세요

  6. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2021.09.06 12:21 신고

    역시 수학문제는 어려워 보이네요.ㅎ

  7. 우렁각시 2021.09.06 12:53

    와,,,ㅎㅎㅎ 어렵네요 ㅎㅎ 잘 보고 갑니당~~

  8. Favicon of https://lsmpkt.tistory.com BlogIcon 가족바라기 2021.09.06 22:17 신고

    학생들에게 좋은 공부되겠어욕

Lazy Propagation 이란?

기존 세그먼트 트리에서 i 에서 j 까지의 구간을 업데이트 하기 위해서는 수행시간은 O(NlogN)의 시간이 걸리게 된다.

이 구간 없데이트 시간을 단축 시키기 위한 알고리즘이 필요한데 이때 사용하는 알고리즘이 Lazy Propagation(게으르게 전파) 알고리즘이다. 이 알고리즘의 수행 속도는 O(logN) 이다.

 

 

 

 

Lazy Propagation 동작 방법

배열 {1,2,3,4,5} 가 있는 구간합의 예를 살펴 봅니다.

세그먼트 트리 구현시 다음과 같은 트리가 생성 됩니다.

 

 이때 0번지 부터 2번지까지에 3을 더해 준다고 하면 다음과 같이 계산이 됩니다.

 

 

 

파랑색 부분을 계산하면서 노랑색 부분은 (0~1) 위치는 2번, (0~2) 위치는 3번, (0~4) 위치는 3번 이 계산 됩니다.

따라서 업데이트 소요 시간은 NlogN 의 시간의 소요가 발생합니다.

 

여기서 Lazy Propagation 의 동작은 다음과 같습니다.

 

 

먼저 구간합이 일어나는 0~2 까지의 구간위치에 Lazy 값 3을 입력 합니다.

 

이렇게 Lazy 값을 셋팅 해주고 2번지 부터 4번지까지의 쿼리를 해 보도록 하겠습니다.

 

이 구간의 구간합은 6 + 4 + 5 = 15의 값이 나와야 합니다.

 

이때 방문하는 위치를 보면 다음과 같이 노란색 위치가 됩니다.

 

여기서 쿼리를 위해 자신을 방문할때 하위노드에 Lazy 값을 반영 후에 자신의 Lazy 값을 삭제 합니다.

 

이렇게 계산을 한 후에 6 + 9 의 15 값을 가져 올 수 있습니다.

 

하지만 문제는 상위에 적용이 안되는 부분이 있는데 이 부분은 업데이트 과정에서 빠져 나오면서 적용을 할 수가 있습니다.

 

그러면 업데이트 과정을 다시 한번 살펴 보겠습니다.

 

0~2번지에 3의 값을 누적하는 상황이 된다면 

위와 같이 3의 Lazy 값을 셋팅 후에 나오면서 0~4 구간에 3 * 3 의 값을 셋팅 해 줄수가 있습니다.

 

 

 

문제풀이

 

www.acmicpc.net/problem/10999

 

10999번: 구간 합 구하기 2

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <stdio.h>
 
#define MAXN 1000010
 
 
using namespace std;
 
struct Data{
    long long sum;
    long long Lazy;
};
 
int N,M,K;
Data SegTree[1<<21]; //세그먼트 트리 갯수는 2,097,152 개 이상이어야 한다.
 
void updataSegTree(int cur,int s,int e,int pos,int val)
{
    if(s==e){
        SegTree[cur] = {val,0}; ///내 위치를 찾아 왔으면 업데이트 하자.
        return;
    }
    int mid = (s+e)/2;
    if(mid<pos) updataSegTree(cur*2 + 1,mid+1,e,pos,val); ///오른쪽 자식위치로 이동
    else updataSegTree(cur*2,s,mid,pos,val);  ///왼쪽 자식 위치로 이동
    SegTree[cur].sum = SegTree[cur*2].sum + SegTree[cur*2 + 1].sum; ///자식의 합을 누적
}
 
void updataLazeTree(int cur,int rangestart,int rangeend,int s,int e,long long val)
{
    //lazy가 남아있을 때
    if(SegTree[cur].Lazy != 0){
            SegTree[cur].sum += (rangeend-rangestart+1)*SegTree[cur].Lazy;
            if(rangestart != rangeend){
                SegTree[cur*2].Lazy += SegTree[cur].Lazy;
                SegTree[cur*2+1].Lazy += SegTree[cur].Lazy;
            }
            SegTree[cur].Lazy =0;
    }
    if(e < rangestart || s > rangeend) return//범위를 벗어날때
    if(s <= rangestart && rangeend <= e){  //현재 범위가 구간의 포함되는 경우
            SegTree[cur].sum += (rangeend-rangestart+1)*val;
            if(rangestart != rangeend){
                    SegTree[cur*2].Lazy += val;
                    SegTree[cur*2+1].Lazy += val;
            }
            return;
    }
    updataLazeTree(cur*2, rangestart, (rangestart+rangeend)/2, s, e, val);
    updataLazeTree(cur*2+1, (rangestart+rangeend)/2+1, rangeend, s, e, val);
    SegTree[cur].sum = SegTree[cur*2].sum+SegTree[cur*2+1].sum;
 
}
long long queryLazeTree(int cur,int rangestart,int rangeend,int s,int e)
{
    if(SegTree[cur].Lazy != 0){
            SegTree[cur].sum += (rangeend-rangestart+1)*SegTree[cur].Lazy;
            if(rangestart != rangeend){
                    SegTree[cur*2].Lazy += SegTree[cur].Lazy;
                    SegTree[cur*2+1].Lazy += SegTree[cur].Lazy;
            }
            SegTree[cur].Lazy =0;
    }
    if(s> rangeend || e < rangestart) return 0;
    if(s <= rangestart && rangeend <= e)
        return SegTree[cur].sum;
    return queryLazeTree(cur*2, rangestart, (rangestart+rangeend)/2, s, e)+queryLazeTree(cur*2+1, (rangestart+rangeend)/2+1, rangeend, s, e);
}
int main()
{
    //freopen("input.txt","r",stdin);
 
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(NULL);
    int num;
 
    cin >> N >> M >> K;
    for(int i=1;i<=N;i++)
    {
        cin >> num;
        updataSegTree(1,1,N,i,num);
    }
 
    int cmd;
    int a,b,c;
    for(int i=0;i<M+K;i++)
    {
        cin >> cmd;
        if(cmd==1)
        {
            cin >> a >> b >> c;
            updataLazeTree(1,1,N,a,b,c);
        }
        else{
            cin >> a >> b;
 
            cout << queryLazeTree(1,1,N,a,b) << "\n";
        }
    }
 
    return 0;
}
 
cs

 

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.

 

인천 서구 검단신도시 원당컴퓨터학원

 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://lsmpkt.tistory.com BlogIcon 가족바라기 2021.02.22 22:47 신고

    요즘 아들이 알고리즘 한다고 해서 이름은 익히 들어봤네요
    어려울것같아요

  2. 핑구야날자 2021.02.23 06:50

    알고리즘은 다양한 경우의 수를 생각하는 좋은 기회가 될 거 같아요

  3. Favicon of https://xuronghao.tistory.com BlogIcon 空空(공공) 2021.02.23 07:41 신고

    알고리즘에 대해 학생들과 공부할수 있겠습니다^^

  4. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2021.02.23 10:16 신고

    알고리즘 잘 배우고 갑니다.
    즐거운 하루 보내세요~

  5. 2021.02.23 11:03

    비밀댓글입니다

  6. Favicon of http://deborah.tistory.com BlogIcon 데보라 2021.02.23 21:05

    저도 학생들 응원해요. 이렇게 여러 컴퓨터 관련 상식을 올려 주고 있으니 학원이 성공 할 수밖에 없네요

Convex Hull trick 란

Convex Hull trick 란 Convex Hull(블록껍질) 알고리즘과는 다른 알고리즘이다.

최적의 값을 찾아가는 형태가 Convex Hull 을 닮아서 Convex Hull trick 라고 알려져 있는데~

Convex Hull Optimization 이라고도 한다.

이 알고리즘은 특정 점화식 꼴을 가지는 동적계획법에서 시간을 줄이는 방법이다.

일차 함수식이 위와 같이 여러개가 들어 오는 경우

각 x의 입장에서 최솟값을 찾는 알고리즘

 

동적알고리즘에서 다음과 같은 형태의 점화식 작성시 사용됨

dp[i] = min(dp[j] + a[i]b[j])( 0<=j < i)

여기서 y = ax + b 와 같은 형태를 띄게 되는데

a[i] 는 x 에 해당하는 상수값을 의미

b[j] 는 a에 해당하는 j값에 의해 변하는 값을 의미

dp[j] 는 각 직선에서 b 에 해당하는 변하는 값을 의미

여기서 x는 고정값이고 a와 b 의 값이 변하는 값인데 해당하는 x 값 위치에서 가장 최선의 a와 b를 찾는 것이 Convex Hull Trick 알고리즘이다.

구현 방법은 아래 문제를 해결하면서 확인을 하자.

 

문제풀이

백준- www.acmicpc.net/problem/13263

 

13263번: 나무 자르기

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) a1 = 1이고, bn = 0이며, a1 < a2 < ... < an, b1 > b2 > ... > bn을 만족

www.acmicpc.net

나무자르기 문제가 대표적인 Convex Hull Trick 을 사용하는 문제이다.

이 문제를 처음 접할때 이게 왜 직선의 방정식인지 이해가 안 가는 경우가 발생을 하는데~

이 문제의 두번째 예를 살펴 보자

5

1 2 3 10 20 30

6 5 4 3 2 0 

이 문제를 풀기 위해서 접근을 해 보면

1의 나무를 자르는데는 비용이 발생하지 않지만 1의 나무를 잘라야만 충전을 할 수가 있기 때문에 1을 먼저 잘라야 한다.

30의 나무를 자르고 나면 그 다음 부터는 0의 비용으로 나무를 자를 수 있다.

따라서 1의 나무를 먼저 자른후에 30을 자른다고 하면 30을 자르는 비용은 6 * 30 = 180 의 비용이 된다.

그 다음 부터는 0의 비용으로 충전을 할 수 있으므로 180의 충전 비용으로 나무를 모두 자를수 있다.

그런데 그것이 가장 좋은 방법일까?

1을 먼저 자른후

2를 자르는 비용을 생각하자 => 2 * 6= 12

3을 자르는 비용을 생각하자 => 12 + (3*5) = 27 또는 3 * 6 = 18 중 작은 값 18을 선택 할 수 있다.

10을 자르는 비용을 생각하자 => 18 + (10*4) = 58 또는 12 + (10*5) = 62 또는 10 * 6 = 60 중에서 58을 선택 할 수 있다.

20을 자르는 비용을 생각하자 => 58 + (20*3) = 118 또는 18 + (20*4) = 98 또는 12 + (20*5) = 112 또는 (20*6) = 120 중에서 98 을 선택 할 수 있다.

30을 자르는 비용을 생각하자 => 98 + (30*2) = 158 또는 58 + (30*3) = 148 또는 18 + (30*4) = 138 또는 12 + (30*5) = 162 또는 30* 6= 180 중에서 가장작은 138을 선택 할 수 있다.

이렇게 생각해 보면 다이나믹인것을 확인 할수 있다.

dp[i] = min(dp[j] + a[i]b[j]) 와 같은 형식이 되는 것을 확인 할 수 있다.

하지만 i의 크기가 100000 이라서 이렇게 다이나믹으로 해결 할때 시간초과가 발생하는 것을 알 수 있다.

하지만 점화식이 좀전에 설명한 Convex Hull Trick 에 해당하는 직선의 방정식으로 표현 되는 것을 확인 할 수 있다.

y=ax + b 와 같은 직선의 방정식에서 해당 x의 위치에서 a와 b의 최적값을 찾는 데 이때는 이진탐색을 사용해서 해결할 수가 있다.

소스코드를 살펴 보면 다음과 같이 해결이 가능하다.

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <vector>
#include <algorithm>
 
 
#define MAX 100010
 
using namespace std;
 
struct Line{
    long long a,b; // y=ax+b 형태의 a,b 값
 
    double crossPos; // 앞에 나오는 라인과 만나는 x 위치중에서 가장 작은 x 값을 저장하자.
};
 
vector <Line> S;
int a[MAX],b[MAX],n;
long long dp[MAX];
 
double cross(const Line &l,const Line &r)
{
    /// left 와 right 가 서로 만나는 지점을 찾는 것이므로
    /// l.a * x +l.b = r.a * x + r.b 이다
    /// x = (r.b - l.b)/(l.a-r.a) 이다.
    return (r.b - l.b)/(l.a - r.a);
}
 
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(NULL);
 
    freopen("input.txt","r",stdin);
 
    cin >> n;
 
    for(int i=0;i<n;i++cin >> a[i];
    for(int i=0;i<n;i++cin >> b[i];
 
    /// 0번 위치의 값은 비용이 들지 않으므로 1번 부터 계산해 주면 된다.
    Line imsi;
    for(int i=1;i<n;i++){
        imsi.a = b[i-1];  /// min(dp[j] + a[i]b[j] 에서 y = ax + b 형태에서 a에 해당하는 값은 b[j] 에 해당한다.
        imsi.b = dp[i-1]; /// b에 해당하는 값은 dp[j] 에 해당한다.
        imsi.crossPos = 0;
 
        while(S.size()>0)
        {
            ///기존에 들어온 라인이 있다면 가장 마지막에 입력된 라인과의 교점을 구해 보자.
            imsi.crossPos=cross(imsi,S.back());
 
 
            if(imsi.crossPos<S.back().crossPos)
            {
                S.pop_back(); /// 자신과 만나는 위치가 그 이전에 만나는 값보다 더 작다고 하면 굳이 있을 필요가 없다.
            }
            else break;
        }
        S.push_back(imsi);
 
        long long x= a[i];
        int pos =0;
        int left=0;
        int right=S.size() -1;
        int mid;
        /// 현재 버퍼에서 가장 가까운 값을 찾아서 dp 테이블에 넣어 주자.
        while(left<=right)
        {
            mid = (left+right)/2;
            if(S[mid].crossPos < x)
            {
                pos = mid;  /// 만나는 점이 내 위치보다 작다면 일단 선택해 주자.
                left = mid+1;
            }
            else
            {
                right = mid - 1;
            }
 
        }
        dp[i]=S[pos].a * x + S[pos].b;
    }
 
    cout << dp[n-1];
 
    return 0;
}
 
cs

 

if(imsi.crossPos<S.back().crossPos)
{
       S.pop_back(); /// 자신과 만나는 위치가 그 이전에 만나는 값보다 더 작다고 하면 굳이 있을 필요가 없다.
}

부분의 의미는 

위의 그림에서 3번과 4번을 살펴 보면 3번이 그 이전에 2번을 만나는 위치가 4번이 3번을 만나는 위치보다 더 크기 때문에 굳이 3번 라인을 살펴볼 필요는 없다.

이렇게 하면 x값으로 정렬되어 있는 데이터가 들어갈 수 밖에 없으므로 가장 적합한 위치의 값을 이진탐색으로 탐색이 가능하다.

 

 

인천 서구 검단신도시 원당컴퓨터학원

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
우선순위큐(Priority Queue) 란?

우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선순위가 높은 데이터가 먼저 나가게 된다.

 

응용분야

- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영체제에서의 작업 스케줄링

 

우선순위큐 STL 기본 형태

priority_queue<T,Container,Compare> : 원하는 자료형 및 클래스 T를 통해 생성, 여기서 Container는 Vector와 같은 컨테이너 이며 Compare 는 비교 함수 클래스(단,Compare 조건에서 참인 것이 후 순위로 밀린다.)

 

우선순위큐 함수

push(element) : 우선순위 큐에 추가
pop() : 원소 삭제
top() : top에 있는 원소를 반환
empty() : 비어있으면 true 아니면 false
size() : 우선 순위 큐에 포함되어 있는 원소들의 수를 반환

 

우선순위큐 구현 예

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct INT{
    public :
        int a;
        INT(){};
        INT(int x){a=x;};
};
struct cmp{
    bool operator()(INT a,INT b)
    {
        return a.a < b.a;
    }
} ;
 
int main()
{
    priority_queue<INT,vector<INT>,cmp>pq;
    pq.push(INT(2));
    pq.push(INT(5));
    pq.push(INT(8));
    while(!pq.empty())
    {
        INT imsi = pq.top();
        cout << imsi.a << endl;
        pq.pop();
    }
    return 0;
}
 
cs

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct INT{
    public :
    int a;
    INT(){};
    INT(int x){a=x;};
};
 
bool operator<(INT a,INT b)
{
        return a.a < b.a;
}
 
int main()
{
    priority_queue<INT>pq;
    pq.push(INT(2));
    pq.push(INT(5));
    pq.push(INT(8));
    while(!pq.empty())
    {
        INT imsi = pq.top();
        cout << imsi.a << endl;
        pq.pop();
    }
    return 0;
}
 
 
cs

 

 

문제풀이

www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2630&sca=9010

 

JUNGOL

 

www.jungol.co.kr

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>
 
using namespace std;
 
typedef struct info
{
    int id;
    int w; //시간
    int num; //계산대번호
    bool operator < (const info &r) const{
        if(w>r.w)return true;
        else if(w==r.w)
        {
            if(num<r.num)return true//계산대 번호가 큰걸 뽑자
        }
        return false;
    }
}info;
 
priority_queue <info> pq1;//outq
 
typedef struct data
{
    int id;
    int t;
    int num;
    bool operator < (const data &r) const{
        if(t>r.t)return true;
        else if(t==r.t)
        {
            if(num>r.num)return true//계산대 번호가 작은걸 뽑자.
        }
        return false;
    }
}data;
 
priority_queue <data> pq2;//inq
 
int main()
{
    //freopen("input.txt","r",stdin);
    int n,k,i;
    int a,b;
    scanf("%d %d",&n,&k);
    data tmp;
    info imsi;
 
    for(i = 0;i < n;i++)
    {
 
        scanf("%d %d",&a,&b);
        if(i<k)
        {
            tmp.num = i+1;
            tmp.t = b;
            tmp.id = a;
           // pq2.pop();
            pq2.push(tmp);
 
            imsi.id = a;
            imsi.num = tmp.num;
            imsi.w = b;
            pq1.push(imsi);
        }
        else
        {
            tmp = pq2.top();
            pq2.pop();
 
            tmp.id = a;
            tmp.t += b;
 
            imsi.id = tmp.id;
            imsi.num = tmp.num;
            imsi.w = tmp.t;
            pq1.push(imsi);
            //printf("(%d,%d,%d)\n",imsi.id,imsi.num,imsi.w);
 
            pq2.push(tmp);
        }
 
    }
    int ind=1;
    long long int sum=0;
    while(!pq1.empty())
    {
        sum += (long long)ind*pq1.top().id;
        //printf("%d\n",pq1.front().id);
        ind++;
        pq1.pop();
    }
    printf("%lld",sum);
    return 0;
}
cs
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기

선형리스트

- 배열에서 원소 삽입 방법을 살펴 보자.

질문)  위와 같은 경우 배열의 데이터가 1억개 인경우 0 번지에 데이터를 삽입 하기 위해서 몇번 연산을 해야 할까?

 

 

- 배열에서 원소 삭제 방법을 살펴 보자.

 

질문)  위와 같은 경우 배열의 데이터가 1억개 인경우 0 번지에 데이터를 삭제 하기 위해서 몇번 연산을 해야 할까?

 

 

 

순차 자료구조의 문제점

- 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가 작업과 시간 소요
- 원소들의 이동 작업으로 인한 오버헤드로 원소의 개수가 많고 삽입・삭제 연산이 많이 발생하는 경우에 성능상의 문제 발생
- 순차 자료구조는 배열을 이용해 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가짐 
- 순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한  문제를 개선한 자료 표현 방법 필요

 

 

 

연결리스트(Linked List)

- 자료의 논라적인 순서와 물리적인 순서가 불일치

- 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결된느 방식

(물리적은 순서를 맞추기 위해 오버헤드가 발생하지 않음)

- 여러개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현

(크기 변경이 유연하고 더 효율적으로 메모리를 사용)

 

 

연결리스트의 노드

- 연결 자료구조에서 하나의 원소를 표현하기 위한 단위구조

- <데이터, 주소> 의 구조

    : 데이터 필드 - 원소의 값을 저장, 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성됨

    : 링크필드(주소) - 다음 노드의 주소를 저장, 포인터 변수를 사용하여 주소값을 저장

 

 

순차 자료구조와 연결 자료구조의 비교

 

 

노드에 대한 구조체 정의
typedef struct _Node{
	int data;
    struct _Node *link;
}Node;

 

 

연결리스트 정의
Node *Head;  //맨먼저 접근하기 위한 포인터
Node *CurPos;  //이동하기 위한 포인터

 

연결리스트 마지막에 추가
void LinkedLastAdd(Node *data)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	Head = data;
    }
    else{
    	CurPos = Head;
        while(CurPos->link!=NULL) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        CurPos->link=data;
    }
}

 

 

현재 연결리스트의 값을 출력
void LinkOutput()
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	return;
    }
    else{
    	CurPos = Head;
        while(CurPos!=NULL) //마지막 위치까지 찾아가자
        {
            cout << CurPos->data << endl;
        	CurPos=CurPos->link;
        }
    }
}

 

 

선택된 연결리스트 뒤에 삽입
void LinkedSelectInsert(Node *Select,Node *data)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	Head = data;
    }
    else{
    	CurPos = Head;
        while(CurPos!=Select) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        data->link = CurPos->link; ///추가하는 데이터에 선택된 위치의 다음 정보를 연결한다.
        CurPos->link=data;         ///현재 선택된 위치의 다음 위치 에 추가할 데이터를 연결한다.
    }
}

 

선택된 요소 삭제
void LinkedSelectDelete(Node *Select)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	return;
    }
    else{
        if(Select == Head)
        {
            Head = Head.link; //Head를 삭제하는 경우 Head를 다음 위치에 이동시키자.
            elete Select;       ///선택된 객체는 삭제하자.
            return;
        }
    	CurPos = Head;
        while(CurPos->link!=Select) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        CurPos->link = Select->link; ///선택 된 데이터의 전 링크를 선택된 링크 위치로 이동시키자.
        delete Select;       ///선택된 객체는 삭제하자.
    }
}

 

 

 

 

 

사용예제
#include <iostream>

using namespace std;

typedef struct _Node{
    int data;
    struct _Node *link;
} Node;

Node *Head;
Node *CurPos;

void LinkedLastAdd(Node *data)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	Head = data;
    }
    else{
    	CurPos = Head;
        while(CurPos->link!=NULL) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        CurPos->link=data;
    }
}

void LinkedSelectInsert(Node *Select,Node *data)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	Head = data;
    }
    else{
    	CurPos = Head;
        while(CurPos!=Select) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        data->link = CurPos->link; ///추가하는 데이터에 선택된 위치의 다음 정보를 연결한다.
        CurPos->link=data;         ///현재 선택된 위치의 다음 위치 에 추가할 데이터를 연결한다.
    }
}

void LinkedSelectDelete(Node *Select)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	return;
    }
    else{
        if(Select == Head)
        {
            Head = Head.link; //Head를 삭제하는 경우 Head를 다음 위치에 이동시키자.
            elete Select;       ///선택된 객체는 삭제하자.
            return;
        }
    	CurPos = Head;
        while(CurPos->link!=Select) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        CurPos->link = Select->link; ///선택 된 데이터의 전 링크를 선택된 링크 위치로 이동시키자.
        delete Select;       ///선택된 객체는 삭제하자.
    }
}

void LinkOutput()
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	return;
    }
    else{
    	CurPos = Head;
        while(CurPos!=NULL) //마지막 위치까지 찾아가자
        {
            cout << CurPos->data << endl;
        	CurPos=CurPos->link;
        }
    }

    cout <<"\n\n";
}

int main()
{
    Node *tmp[10];
    for(int i=0;i<10;i++)
    {
        tmp[i] = new Node;
        tmp[i]->data = i+1;
        tmp[i]->link = NULL;
        LinkedLastAdd(tmp[i]);
    }

    LinkOutput();

    Node *add;
    add = new Node;
    add->data = 100;
    add->link = NULL;
    LinkedSelectAdd(tmp[6],add);
    LinkOutput();
    LinkedSelectDelete(add);
    LinkOutput();

    return 0;
}

 

 

 

인천 서구 검단신도시 원당컴퓨터학원

 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
알고리즘이란?

- 입력 : 외부에서 제공되는 자료가 0개 이상 제공된다.

- 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.( 즉 모든 입력에서 하나의 출력이 나오면 안됨)

- 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성

- 유한성 : 유한번의 명령을 수행 후 종료된다.

- 효율성 : 모든 과정은 명백하게 실행가능(검증가능) 한것이어야 한다.

 

 

좋은 알고리즘이란?

- 정확성 : 적당한 입력에 대해서 유한 시간내에 답을 산출하는가? 를 판단.

- 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정

- 기억장소 사용량 : 수행 과정에서 필요한 저장공간

- 최적성 : 그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가?

(단, 최적이란 가장  '잘 알려진' 이 아닌 '가장 좋은' 의 의미이다.)

- 시간 복잡도 : 최적의 시간으로 연산을 수행하는 알고리즘인가?

(단, 빠른 시간안에 해결이 된다고 해도 정확성이 떨어진다면? 혹은 정확성은 약간의 오차가 발생하는데 시간 차이가 많이 발생한다면?)

 

 

 

시간 복잡도

- 문제를 해결하는데 걸리는 시간과 입력의 함수 관계

- 가장 많이 사용하는 빅오표기법(O) : 알고리즘의 효율성을 상한선 기준으로 표기한다.(1부터 5000까지의 수가 있는 경우 어떤 수의 위치를 찾을때 최대 5000 번을 수행한다고 하면 빅오표기법에서 수행시간은 5000 이라고 생각하는 것이다.)

 

 

빅오표기법

- O(1) : 입력 자료에 관계 없이 동일한 실행 시간을 갖는 알고리즘 

예)

int main()
{
	int a[] = {1,2,3,4,5,6,7,8,9,10};
           int b;
           scanf(“%d”,&b);
           printf(“%d”,a[b]);
}

 

 

- O(logN) : 입력자료가 N일경우 log2N의 시간

예)

int f(int n)
{
	int a[] = {1,2,3,4,5,6,7,8,9,10};
           int b;
           int s =0;
           int e = 9;
           while(1){
		if(s>=e) return -1; //찾지 못했다.
		int m = (s+e) /2;
 		if(a[m]==n) return  m;
		if(a[m]>n) s=m+1;
                      else e = m-1;
	} 

}

 

 

- O(N) : 입력 자료가 N일경우 N시간

예)

int f(int n)
{
	int a[] = {1,2,3,4,5,6,7,8,9,10};
           int b;
           for(int i=0;i<10;i++) if(a[i]==n) return I;
	return -1;
}

 

 

- O(NlogN) : 입력자료가 N일경우 Nlog2N의 시간

예)

int quick_Sort(int start, int end)
{
    int tempValue;
    if(start < end)
    {
        int left = start-1, right = end+1, pivot = a[start];
        while(left<right)
        {
            while(a[++left]<= pivot);
            while(a[--right] > pivot);
            if(left >= right) break;
	swap(a[left],a[right]);
        }
        swap(a[start],a[right]);
        quick_Sort(start, right-1);
        quick_Sort(right + 1, end);
    }
}

 

 

- O(N²) : 입력 자료가 N일경우 N * N 시간

예)

int f(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) printf( “%d “,i*j);
		printf(“\n”);
	}
}

 

 

- O(N³) : 입력 자료가 N일경우 N * N * N 시간

예)

int f(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) 
		{
			for(int k=1;k<=n;k++) printf( “%d “,i+j+k);
			printf(“\n”);
		}
	}
}

 

 

- O(2ⁿ) : 입력 자료가 2^n 의 시간

예)

int dfs(int y,int x,int state)
{
	if(y>=n) return 1;
	if(x>=n) y++,x=0;
	int res = dfs(y,x+1,0) + 1;
    	res +=dfs(y,x+1,1) +1;
	return res;
}

 

 

 

수행시간 계산방법

- #include <time.h> 또는 #include <ctime> 선언
- clock() 함수를 이용해 프로그램 수행시간 측정

 

예)

int startTime,endTime;
startTime = clock();
//프로세스 수행
endTime= clock();
printf(“%.3lf”,(double)(endTime-startTime)/CLOCKS_PER_SEC);
 
//여기서 CLOCKS_PER_SEC 는 1000의 값으로 define 되어 있다.

 

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.

인천 서구 검단신도시 원당컴퓨터학원

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기

그리디(greedy) 알고리즘이란?

단어에서 나타내듯이 아주 탐욕스러운 알고리즘 입니다.

이렇게 탐욕스럽다라고 표현 하니 학생들은 아주 나쁜 알고리즘이네요? 라고 말하네요.

하지만 탐욕스러운 것이 정말 나쁜 것일까요?

자신이 항상 손해 보면서 사는 사람은 없을 것입니다.

사람 사는 세상에 주고 받고 하면서 자신이 더 큰 이득을 보기 위해 조금 더 작은 것을 내 주는 것일 뿐입니다.

이와 마찬가지로 그리디 알고리즘은 현재 선택해야 되는 시점에서 자신에게 가장 이득이 되는 것을 취하고 나머지는 버리는 경우를 그리디 알고리즘이라고 합니다.

이러한 알고리즘의 예로 가장 많이 사용 되는 것이 동전 바꿔 주는 문제인데요.

500원,100원,50원,10원,5원,1원 단위의 동전이 있을때

문방구에 가서 1432원짜리 필통을 구매하고 2000원을 지불 했을때 가장 적은 갯수의 동전으로 거스름돈을 받고 싶습니다.

이때 568원을 거슬러 받아야 하는데요.

500원짜리 한개를 먼저 취하고 나머지 68원이 남게 됩니다.

그 다음 50원짜리 한개를 먼저 취하고 나머지 18원이 남으면

10원짜리 한개 5원짜리 한개 1원짜리 3개로 거스름돈을 받을 때 동전의 갯수가 최소가 됩니다.

이렇게 가장 큰 단위부터 취하게 되는데 568원에서는 최선의 선택은 500원입니다.

하지만 68원에서는 최선은 50원이 되겠네요.

이렇게 선택해야 하는 시점에서 최고로 좋은 것을 취하는 것을 그리디 알고리즘이라고 합니다.

 

하지만 알고리즘에서는 이러한 그리디 문제를 해결하기 위해 먼저 작업을 해야 할 일이 있는데,

그것은 동전 단위를 500원,100원,50원,10원,5원,1원 과 같이 순서대로 정렬을 해 놓아야 합니다.

568원에서 첫번째 단위인 500원짜리를 선택 할 수 있는지 확인 하고 선택이 가능하면 가능한 갯수를 선택 후

남은 돈 68원에서 두번째 단위인 100원짜리를 선택 할 수 있는지 확인 하고 선택이 불가능하기에 0개 선택 후

다시 남은돈 68원에서 세번째 단위인 50원짜리를 선택 할 수 있는지 확인 하고 선택이 가능한 갯수 선택 후

남은 18원에서 그 다음 단위 10원짜리 선택 후 나머지 8원에서 그 다음 단위 5원짜리 선택 후 나머지 3원에 대해서 1원짜리 3개를 선택하는 개념으로 이루어 집니다.

 

하지만 이러한 그리디 알고리즘에는 항상 최적이 될 수 있는가 라는 문제가 발생합니다.

동전단위가 1,5,10,50,100,500 단위가 아니라 500원,284원,90원,10원,1원 단위 체계로 되어 있다고 하면 568원을 거스름돈을 주기 위해서는 284원 동전 2개만 주면 되는데...

그리디 알고리즘으로 처리 한다면 500원 하나, 나머지 68원에서 10원 6개,1원 8개 가 필요합니다.

따라서 그리디 알고리즘을 사용하기 위해서 가장 고려해야 할 부분은 바로 "전체적으로 최적이 될 것인가?"  입니다.

 

이러한 그리디 알고리즘을 설계하는 방법은 다음과 같습니다.

1. 설계의 기본은 선택할 것이 여러개 일 경우 그 중 가장 좋은 것을 선택하는 것

2. 문제를 여러 단계로 구분하여 각 단계마다 최적해를 구한다.

3. 각 단계의 최적해를 구할 때 가장 큰것 혹은 가장 작은것을 선택하게 된다.

 

그리디 알고리즘 구현시 유의점

- 현재 시점에 있어서 최적의 해를 선택하는데 그것이 전체적으로 최적의 해가 되지 않는 경우를 고려해야 한다.

 

그리디 알고리즘의 장점

- 전체의 모든 경우를 살피지 않고 현재 단계 단계에서 최선의 경우를 선택하는 경우로 각각의 단계를 한번만 수행하므로 수행 시간이 무척 빠르다.

 

이 정도로 소개를 마치도록 하겠습니다.

이러한 그리디 알고리즘은 실제 생활에서 가장 많이 사용되는 경우가 동전 거슬러 주는 경우에도 발생을 하고...

기차표를 예매할때 종점을 기준으로 정렬을 해서 그 사람의 좌석을 발매해 줄때도 유리합니다.

기차표를 구매하는데 첫번째 사람이 서울에서 대전을 구매 했다고 하면 그 좌석을 대전에서 부산 가는 사람에게 다시 부여 해 준다면 훨씬 유리 할 것입니다.

그리고 회의실 예약 시에도 더 많은 사람이 회의를 하기 위해서 중복 시간을 제거 하는 경우 빨리 끝나는 사람을 기준으로 배정을 해 준다면 좀 더 많은 사람이 할당을 받을 수도 있을것입니다.

 

이렇게 그리디 알고리즘은 다양한 곳에서 사용이 되고 있는데요.

이러한 그리디 알고리즘의 핵심은 데이터 정렬에 있다고 해도 과언이 아닐 것입니다.

 

만약 기차표를 예매하는데 있어서 출발지를 가지고 정렬을 한다고 하면 서울에서 출발해서 부산에 가는 사람,그리고 천안에서 대전에 가는 사람이 있는데 대전에서 대구를 가는 사람이 표를 사기 위해서는 서울에서 출발하는 사람이 어디서 내리는 지 확인해야 되고 천안에서 출발하는 사람이 어디서 내리는지를 확인해야 될것입니다.

만약 종점을 기준으로 정렬을 한다면 천안에서 출발해서 대전에서 내리는 사람이 먼저 조회가 될것이므로 어떤 조건으로 데이터를 정렬해서 먼저 선택을 할 것인가가 무척이나 중요한것 같아요.

 

실제로 컴퓨터 과학은 실생활의 규칙들을 얼마만큼 효율적으로 구현할 수 있는가가 중요하기 때문에...

그리디 알고리즘만으로도 충분히 그러한 규칙들을 생각해 볼수 있는 계기가 될것 같네요.

 

인천 원당 컴퓨터학원

 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://deborah.tistory.com BlogIcon Deborah 2019.11.25 21:24 신고

    알리고리즘에 대한 새로운 생각을 하게 해준 글 감사히 잘 봣네요. 오늘도 날씨가 추워요. 건강유의 하시고 늘 행복하시길요.

  2. Favicon of https://bubleprice.tistory.com BlogIcon 버블프라이스 2019.11.26 04:23 신고

    그리디(greedy) 알고리즘에 대해 몰랐던 내용을 덕분에 알고 갑니다^^
    즐거운 화요일 되세요-

  3. Favicon of https://heysukim114.tistory.com BlogIcon *저녁노을* 2019.11.26 06:16 신고

    자 ㄹ알고 갑니다.
    ㅎㅎ

    즐거운 하루 되세요

  4. Favicon of https://ramideunioni.tistory.com BlogIcon 라드온 2019.11.26 06:37 신고

    그리디알고리즘을 이해가 쉽도록 동전의 거스름돈으로 설명해주셔서 한방에 이해했습니다ㅎ사용사례까지, 좋은 설명으로 하나배워갑니다ㅎ

  5. 핑구야날자 2019.11.26 06:49

    몰랐던 알고리즘 잘 보고 갑니다 즐거운 하루 보내세요

  6. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2019.11.26 08:33 신고

    탐욕스러운 알고리즘?
    재밌는 표현이네요.
    그리드 알고리즘에 대해서 공부하고 갑니다.

  7. Favicon of https://xuronghao.tistory.com BlogIcon 空空(공공) 2019.11.26 08:38 신고

    그리디 알고리즘 개념 알고 갑니다.^^

+ Recent posts