극좌 극우로 부터 시작해서, 높이가 낮은 사이드를 당기면서 최대값을 갱신하면 된다.

 

낮은 쪽을 당기는 이유는, 낮은 쪽 사이드가 정답일 경우가 없기 때문.(현재 최대값이 정답인 경우를 제외하고)

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        ret = 0
        
        while(left < right):
            ret = max(ret, (right - left) * min(height[right], height[left]))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
                
        return ret

Components

 

. 모듈과 주입간의 다리 역할 = injector

. @Component 주석과 연관된 모듈들을 줄줄이 기록해둔다

@Singleton
@Component(modules = {
        NetworkModule.class,
        TwitterModule.class,
})
 
public interface TwitterComponent {
    Tweeter tweeter();
    Timeline timeline();
}
 
TwitterComponent component = Dagger_TwitterComponent.builder()
        .networkModule(new NetworkModule())
        .twitterModule(new TwitterModule("JakeWarton"))
        .build();
 
Tweeter tweeter = component.tweeter();
tweeter.tweet("asdasdasd");
 
Timeline timeline = component.timeline();
timeline.loadMore(20);
for(Tweet tweet : timeline.get()){
    System.out.println(tweet);
}
 

연관된 모듈들을 @Component 뒤에 기록해두었다. 

모듈이 제공하는 인스턴스들이 모두 싱글톤이었으므로, TwitterComponent도 싱글톤으로 지정했다.

 

인터페이스를 구성한 이 후, Dagger에서 제공하는 build()함수를 콜해서 컴포넌트들 만들 수 있다.

이 후 이 컴포넌트만 가지고 인스턴스를 가져올 수 있다.

 

사실 NetworkModule은 기본생성자를 가지고 있기 때문에 컴포넌트 생성코드에 네트워크 모듈은 부르지 않아도 되긴하다.

 

public class TwitterApplicatopn implements Runnable {
    private final Tweeter tweeter;
    private final Timeline timeline;
 
    @Inject
    public TwitterApplicatopn(Tweeter tweeter, Timeline timeline){
        this.tweeter = tweeter;
        this.timeline = timeline;
    }
 
    @Override
    public void run(){
        tweeter.tweet("asdasdasd");
 
        timeline.loadMore(20);
        for(Tweet tweet : timeline.get()){
            System.out.println(tweet);
        }
    }
}
 
@Singleton
@Component(modules = {
        NetworkModule.class,
        TwitterModule.class,
})
 
public interface TwitterComponent {
    TwitterApplicatopn app();
}
 
TwitterComponent component = Dagger_TwitterComponent.builder()
        .networkModule(new NetworkModule())
        .twitterModule(new TwitterModule("JakeWarton"))
        .build();
 

아니면 TwitterApplication 이라는 싱글 엔트리 포인트를 만들어 두었기 때문에, 이를 스레드화시키고 run()만 해서 작동시키는게 더 보편적인 개발패턴이란다.

 

 

 

 

 

 

 

Dagger는 자바와 안드로이드를 위한 빠른 의존성 주입을 제공한다.

 

의존성 주입이란, 구성요소간의 의존 관계가 코드 내부가 아닌 외부의 설정파일등을 통해 정의되게 하는 디자인 패턴이다. 이를 통해 모듈간의 결합도가 낮아지게 되므로, 단위 테스트가 쉬워지며 모듈의 재사용성이 높아진다.

 

public class TwitterApi {
    public void postTweet(String user, String tweet){
        OkHttpClient client = new OkHttpClient();
        Request request = client.newCall(request).execute();
    }
}
 
public class Tweeter {
    public void tweet(String tweet){
        TwitterApi api = new TwitterApi();
        api.postTweet("JakeWharton", tweet);
    }
}
 
 

Tweeter 클래스는 tweet 메소드를 제공하는데, 내부적으로 api 인스턴스를 생성하고, 이를 통해 메소드를 호출해 트윗을 포스트 한다.

또한 이 api는 내부적으로 HttpClient 인스턴스를 생성하고 리퀘스트를 만들어 실행한다.

 

이 코드는 매우 구리다. 왜냐하면 매번 request를 위해선 HttpClient 객체가 생성되므로 매우 낭비적이다.

 

코드를 다음과 같이 바꿔본다.

public class TwitterApi {
    private final OkHttpClient client = new OkHttpClient();
    
    public void postTweet(String user, String tweet){
        Request request = client.newCall(request).execute();
    }
}
 

이제 매 request 마다 OkClient 객체가 생성되지 않는다.

이것을 DI스러운 디자인 패턴으로 바꾸면 다음과 같다.

public class TwitterApi {
    private final OkHttpClient client;
 
    public TwitterApi(OkHttpClient client){
        this.client = client;
    }
 
    public void postTweet(String user, String tweet){
        Request request = client.newCall(request).execute();
    }
}
 

생성자는 외부에서 OkHttpClient 레퍼런스를 받아와서 대입시킬 뿐이다.

생성자가 바뀌었으니까 Tweeter 클래스도 바꿔야 한다. 다음과 같다.

public class Tweeter {
    public void tweet(String tweet){
        TwitterApi api = new TwitterApi(new OkHttpClient());
        api.postTweet("JakeWharton", tweet);
    }
}
 

하지만 여전히 낭비적인 요소가 있는데, 사용자가 tweet 할 때 마다 이 큰 객체를 만들어낸다.

똑같이 DI 스러운 디자인 패텅을 적용해보자.

public class Tweeter {
    private final TwitterApi api =new TwitterApi(new OkHttpClient());
    private final String user;
 
    public Tweeter(String user){
        this.user = user;
    }
 
    public void tweet(String tweet){
        api.postTweet("JakeWharton", tweet);
    }
}
 

생성자는 유저이름을 받아와 대입시킨다.

 

이제 다음과 같이 tweet 할 수 있다.

. Tweeter tweeter = new Tweeter("JakeWharton");

. tweeter.tweet("123123123")

. tweeter.tweet("456456456")

 

헌데 이제 타임라인이라는 추가기능을 넣는다고 가정해보자.

public class Timeline {
    private final List<Tweet> cache = new ArrayList<>();
    private final TwitterApi api = new TwitterApi(new OkHttpClient());
    private final String user;
    
    public Timeline(String user) {
        this.user = user;
    }
    
    public List<Tweet> get() { /*....*/ }
    public void loadMore(int amount) { /*....*/ }
}
 

위 클래스를 통해

. Timeline timeline = new TimeLine("JakeWharton");

. timeline.loadMore(20);

. for(Tweet tweet : timeline.get()) { System.out.println(tweet); }

 

타임라인 객체를 생성하고 트윗을 20개 불러와 get()메소드를 통해 출력하는 코드를 생각해보자.

문제는 타임라인 역시 api를 사용하므로 api 객체를 또 만드는 낭비가 발생할 수 있다는 것이다.

public class Timeline {
    private final List<Tweet> cache = new ArrayList<>();
    private final TwitterApi api;
    private final String user;
 
    public Timeline(TwitterApi api, String user) {
        this.api = api;
        this.user = user;
    }
 
    public List<Tweet> get() { /*....*/ }
    public void loadMore(int amount) { /*....*/ }
}
 

따라서 위에서 Tweeter 객체가 생성되면서 만들어진 api를 재사용할 수 있다.

----------------------------------------------------------------------------------------------------

Dagger v2는 다음과 같은 api를 제공한다.

. @Module + @Provides : 의존성 제공을 위한 메커니즘

. @Inject : 의존성 요청을 위한 메커니즘

. @Component : 모듈과 주입 사이의 다리역할

 

1. 의존성 제공

모듈이란 의존성을 제공하는 메소드들을 가진 클래스를 말한다. @Module을 클래스에, @Provides를 각 메소드에 붙여서 지정하면 된다. Tweeter 예제에 적용시키면 다음과 같다.

@Module
public class NetworkModule {
    @Provides @Singleton
    OkHttpCliet provideOkHttpClient() {
        return new OkHttpClient();
    }
    @Provides @Singleton
    TwitterApi provideTwitterApi(OkHttpClient client){
        return new TwitterApi(client);
    }
}
 
@Module
public class TwitterModule {
    private final String user;
 
    public TwitterModule(String user){
        this.user = user;
    }
 
    @Provides @Singleton
    Tweeter provideTweeter(TwitterApi api){
        return new Tweeter(api, user);
    }
 
    @Provides @Singleton
    Timeline provideTimeline(TwitterApi api){
        return new Timeline(api, user);
    }
}
 

모듈이 두 개 생겨났는데, 네트워크모듈은 api를 제공하고, 트위터모듈은 사용자와 타임라인을 제공한다.

정리해서 의존성 관계를 그래프로 나타내면 다음과 같다.

 

사용자나 타임라인이나 api가 있어야 제공받을 수 있다. 동시에 api는 OkHttpClient가 있어야 제공받을 수 있다.

만약 Tweeter객체를 만든다면 OkHttpClient객체까지 생성되지만, 이 후 Timeline객체를 만든다면 api는 이미 생성되어있으므로 OkHttpClient까지 새로이 만들어지진 않는다.

 

2. 의존성 요청

@Inject 로 표시하면 된다. 이 표시는 생성자, 필드, 메소드에 붙일 수 있다.

 

1) 생성자 주입

public class TwitterApplicatopn {
    private final Tweeter tweeter;
    private final Timeline timeline;
 
    @Inject
    public TwitterApplicatopn(Tweeter tweeter, Timeline timeline){
        this.tweeter = tweeter;
        this.timeline = timeline;
    }
}
 

위처럼 의존성이 private final 필드에 저장될 수 있다.

@Inject 표기로 dagger가 알아서 객체생성을 어떻게 해야 하는지 알게 되고 downstream injection을 가능케 한다. 무슨 말이냐면 만약 TwitterApplication 클래스를 inject하고 싶은 클래스가 있다면, 가능하다는 말이다.

더 자세히 설명하면 TwitterApi 생성자는 OkHttpClient 객체를 요구하는데, 이 객체는 TwitterModule에서 @Povides로 제공되고 있는 상황이다.

여기서 TwitterApi 생성자에 @Inject를 붙여주면, dagger가 알아서 객체를 끌어오므로, 모듈에 무수한 @provides 들을 손수 작성하지 않아도 된다.

문제는 네트워크모듈에서 provideTwitterApi는 싱글톤이었는데 @inject를 생성자에 붙이기만 하면 dagger는 매 번 api 요청이 들어올 때 마다 생성자를 호출할 것이다. 따라서 @Singleton을 붙여줘야 한다.

(뭔 말인지 모르겠다.)

결과는 다음과 같다.

@Singleton
public class TwitterApi {
    private final OkHttpClient client;
 
    @Inject
    public TwitterApi(OkHttpClient client){
        this.client = client;
    }
 
    public void postTweet(String user, String tweet){
        Request request = client.newCall(request).execute();
    }
}
 

2) 메소드 주입

 

@Inject를 메소드들에 붙있 수 있다. 이 메소드들의 매개변수들은 의존성들이다. 주입은 매개변수들이 완전히 인스턴스화 된 이후에 이루어진다. 이러한 사용예시 중에 가장 좋은 케이스는 this 객체를 의존성에 전달하는 것이다.

public class TwitterApplicatopn {
    private final Tweeter tweeter;
    private final Timeline timeline;
 
    @Inject
    public TwitterApplicatopn(Tweeter tweeter, Timeline timeline){
        this.tweeter = tweeter;
        this.timeline = timeline;
    }
 
    @Inject
    public void enableStreaming(Streaming streaming){
        streaming.register(this);
    }
}
 

 

3) 필드 주입

 

필드에 @Inject를 붙일 수 있다. 필드는 private 이나 final이면 안된다. 

 

 

 

-------------------------------------------------------------------------------------------------------------

 

Component

 

component가 모듈과 주입 사이의 다리(Injector)역할을 한다고 했다.

 

~20:00

 

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


수열에서 연속 부분 수열 두개를 골라 그 곱이 가장 클 때 얼마나 클지 알아내야 한다.


연속 부분 수열이 얼마나 클지를 알아내는 방법은 디피 문제를 풀 때 쉽게 접할 수 있는 문제다.


dp[x]를 x번째 인자를 포함한 부분 수열 중 합이 가장 큰 수를 저장하게 정의해 놓으면,


dp[x]는 dp[x-1]이 음수인 경우와 양수인 경우로 나눠 원타임에 값이 정해진다.



또한 새로운 디피 배열 lmax를 정의할 수 있게 되는데,


이번엔 lmax[x]는 x번째 인자를 반드시 포함하지 않아도, x까지 수열의 부분 수열 중 합이 가장 큰 수를 저장한다고 정의해 놓으면,


lmax[x] = max(lmax[x-1], dp[x])로 원타임에 값이 정해진다.


즉 x가 포함되던지 안되던지 두 케이스 중 큰 값으로 정해지는 것이다.



이를 응용해서 왼쪽에서 부터, 오른쪽에서 부터, 최대합 부분수열, 최소합 부분수열을 모두 n타임에 구할 수 있다.


그러고 난 다음 부분 수열 두 개로 나눌 기준점을 n개 중에 골라서 비교하는 작업도 n타임에 수행할 수 있다.


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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int n;
ll arr[100001];
 
ll dmin[100001], dmax[100001];
ll lmin[100001], lmax[100001];
ll rmin[100001], rmax[100001];
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
 
    lmin[1] = lmax[1] = dmin[1] = dmax[1] = arr[1];
 
    for (int i = 2; i <= n; ++i) {
        if (dmax[i - 1] < 0)
            dmax[i] = arr[i];
        else
            dmax[i] = dmax[i - 1] + arr[i];
 
        if (dmin[i - 1] > 0)
            dmin[i] = arr[i];
        else
            dmin[i] = dmin[i - 1] + arr[i];
 
        lmin[i] = min(lmin[i - 1], dmin[i]);
        lmax[i] = max(lmax[i - 1], dmax[i]);
    }
 
    memset(dmin, 0, sizeof(dmin));
    memset(dmax, 0, sizeof(dmax));
 
    rmin[n] = rmax[n] = dmin[n] = dmax[n] = arr[n];
 
    for (int i = n - 1; i >= 1; --i) {
        if (dmax[i + 1] < 0)
            dmax[i] = arr[i];
        else
            dmax[i] = dmax[i + 1] + arr[i];
 
        if (dmin[i + 1] > 0)
            dmin[i] = arr[i];
        else
            dmin[i] = dmin[i + 1] + arr[i];
 
        rmin[i] = min(rmin[i + 1], dmin[i]);
        rmax[i] = max(rmax[i + 1], dmax[i]);
    }
 
    ll ans = LLONG_MIN;
    for (int i = 1; i < n; ++i) {
        ans = max(ans, lmin[i] * rmin[i + 1]);
        ans = max(ans, lmin[i] * rmax[i + 1]);
        ans = max(ans, lmax[i] * rmin[i + 1]);
        ans = max(ans, lmax[i] * rmax[i + 1]);
    }
 
    cout << ans;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 2965 캥거루 세마리  (0) 2018.02.06
백준) 2156 포도주 시식  (0) 2018.02.04
백준) 1463 1로 만들기  (0) 2018.02.02
백준) 2579 계단 오르기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01

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


0 ~ 9 까지 숫자 카드 스티커들을 한 번씩만 사용해 n = a + b 의 a와 b를 만들어야 한다.



여러 풀이 중에 내 생각에 제일 기똥찬 풀이는,


a와 b중에 작은 수를 b라고 하면, b의 가능 범위가 작아지므로, 완탐으로 때릴 수 있다는 것이다.



b에 스티커 5장을 쓰면 a도 5장이 되므로 b엔 최대 5장까지만 쓸 수 있다.


또한 b의 맨 앞자리는 끽 해야 8이므로, 1~87654가 b의 가능범위이다.


b가 정해지면 a도 정해지므로, 구만번 만에 풀리는 문제.



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
#include <bits/stdc++.h>
using namespace std;
 
int n;
 
bool func(int x, int& st) {
    while (x) {
        int tmp = (1 << (x % 10));
        if (st & tmp)
            return false;
 
        st |= tmp;
        x /= 10;
    }
 
    return true;
}
 
int main() {
    cin >> n;
 
    for (int i = 1; i <= 87654 && i < n; ++i) {
        int used = 0;
 
        if (!func(i, used))
            continue;
        if (!func(n - i, used))
            continue;
 
        cout << n - i << " + " << i;
        return 0;
    }
 
    cout << -1;
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 16116 작은 큐브러버  (0) 2018.10.01
백준) 15957 음악 추천 (퇴고전)  (0) 2018.09.11
codeforces educational 50 round div2 참여기록  (0) 2018.09.09
SCC 문제들! 백준) 2150, 4013, 4196  (0) 2018.07.22
백준) 2512 예산  (0) 2018.07.19

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


구현이지만 논리력에 따라 // 관찰력에 따라 코드가 짧아질 수 있는 문제



다음을 관찰하면 코드가 짧아진다.



한 큐브가 [a b c] 였다면, 반드시 나머지 일곱 개 중에 윗 그림과 같은 세 개의 큐브가 존재해야 한다.


헌데 큐브는 요리 조리 돌려도 똑같기 때문에


한 큐브 마다 -> 세 가지 방향으로 -> 나머지 7가지 큐브 중에 -> 두면이 맞닿고 같은 큐브가 존재(중요) -> 그것도 1개만


같은 조건을 전부 만족한다면 조립할 수 있다.


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
#include <stdio.h>
 
char str[6];
char cb[8][4];
 
int main() {
    for (int i = 0; i < 8; ++i) {
        fgets(str, sizeof(str), stdin);
        cb[i][0] = str[0];
        cb[i][1] = str[2];
        cb[i][2] = str[4];
        fgets(str, sizeof(str), stdin);
    }
 
    bool cannot = false;
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 3; ++j) {
            int left = cb[i][j];
            int top = cb[i][(j + 1) % 3];
            int cnt = 0;
 
            for (int k = 0; k < 8; ++k) {
                if (i != k) {
                    for (int l = 0; l < 3; ++l) {
                        if (cb[k][l] == left && cb[k][(l + 2) % 3] == top) {
                            cnt++;
                        }
                    }
                }
            }
 
            if (cnt != 1)
                cannot = true;
        }
    }
 
    if (cannot)
        puts("NO");
    else
        puts("YES");
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 15668 방 번호  (0) 2018.10.02
백준) 15957 음악 추천 (퇴고전)  (0) 2018.09.11
codeforces educational 50 round div2 참여기록  (0) 2018.09.09
SCC 문제들! 백준) 2150, 4013, 4196  (0) 2018.07.22
백준) 2512 예산  (0) 2018.07.19

다들 다익스트라를 배우고 이해는 한다.


아~ 계속 간선 길이를 늘려가면서 점마다 우선순위큐로 dp를 찍어주면 되는구나~


이해는 하고 기초 문제를 풀고 나면 다익스트라를 다 아는 것 같은 착각이 든다 ㅎㅎ



근데 이제 다익스트라를 조금만 꽈서 낸 문제면 풀질 못한다 ㅜㅜ


어느 알고리즘이나 응용이 어렵지만, 내가 느끼기엔 다익스트라가 유독 까다롭더라.


그래서 이제부터 좀 다양한 다익스트라 문제들을 올리려고 한다.


이 글을 호오오오옥시 읽는 분들도 아는 문제가 있으면 추천을 부탁드립니다.


---------------------------------------------------------------------------------------------------------------------------------------------------------------------



1) 백준 16118 달빛 여우


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


조금만 꽈서 낸 문젠데 세 번이나 틀리고 맞았다 ^^


여우의 경우 1번 정점부터 나머지 정점까지 최소경로의 길이는 순수 다익스트라로 구할 수 있다.


늑대의 경우 내가 현재 정점에 오기전에 2배 빠르게 왔는지, 느리게 왔는지 기억해야 한다.


그래서 나는 구현을 쉽게 할려고(정말?), 간선을 2배로 뿔렸다. 즉 2배 빨라지는 길, 2배 느려지는 길을 추가했다.


그러면 전에 빨라지는 길로 왔었다면, 이번엔 느려지는 길로만 갈 수 있게 된다.


dp(fox, wolf)에는 빠르게 왔는지, 느리게 왔는지를 둘 다 기록했다.


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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long ll;
 
int n, m;
int a, b;
ll fox[4001], wolf[4001][2], c;
 
struct edge_f {
    int to;
    ll cost;
 
    bool operator< (const edge_f& e) const {
        return cost > e.cost;
    }
};
 
struct edge_w {
    int to;
    ll cost;
    bool fast; //길 종류
 
    bool operator< (const edge_w& e) const {
        return cost > e.cost;
    }
};
 
int main() {
    scanf("%d %d", &n, &m);
 
    vector<vector<edge_f>> vf(n + 1);
    vector<vector<edge_w>> vw(n + 1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %lld", &a, &b, &c);
        vf[a].push_back({ b, 2ll * c });
        vf[b].push_back({ a, 2ll * c });
 
        vw[a].push_back({ b, c, false });
        vw[a].push_back({ b, 4ll * c, true });
        vw[b].push_back({ a, c, false });
        vw[b].push_back({ a, 4ll *c, true });
    }
 
    //////////////////////여우
    memset(fox, -1, sizeof(fox));
 
    priority_queue<edge_f> pqf;
    pqf.push({ 1, 0ll });
 
    while (!pqf.empty()) {
        edge_f e = pqf.top(); pqf.pop();
 
        if (fox[e.to] != -1) {
            continue;
        }
 
        fox[e.to] = e.cost;
 
        for (auto next : vf[e.to]) {
            if (fox[next.to] != -1) {
                continue;
            }
            pqf.push({ next.to, e.cost + next.cost });
        }
    }
    //////////////////////여우
 
    //////////////////////늑대
    memset(wolf, -1, sizeof(wolf));
 
    priority_queue<edge_w> pqw;
    pqw.push({ 1, 0ll, true });
 
    while (!pqw.empty()) {
        edge_w e = pqw.top(); pqw.pop();
 
        if (wolf[e.to][e.fast] != -1)
            continue;
 
        wolf[e.to][e.fast] = e.cost;
 
        for (auto next : vw[e.to]) {
            if (wolf[next.to][next.fast] != -1)
                continue;
            
            if (e.fast != next.fast) { //종류가 다른 길로 가야 해
                pqw.push({ next.to, e.cost + next.cost, next.fast });
            }
        }
    }
    //////////////////////늑대
 
    int ans = 0;
    ll _min, _max;
    for (int i = 1; i <= n; ++i) {
        _min = min(wolf[i][0], wolf[i][1]);
        _max = max(wolf[i][0], wolf[i][1]);
 
        if (_min == -1) { //못 가는 노드가 있을 경우
            if (fox[i] < _max) {
                ans++;
            }
        }
        else {
            if (fox[i] < _min) {
                ans++;
            }
        }
    }
 
    printf("%d", ans);
 
    return 0;
}
cs


2) bitonic path


scpc 2차 예선 문제였는데 링크를 찾고 있습니다 ㅜ

'알고리즘 > Dijsktra 다익스트라' 카테고리의 다른 글

백준) 1753 최단경로  (0) 2017.09.09
다익스트라 도입  (0) 2017.07.11

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


1. 트리


트리의 루트에 쿼리가 가해지면 자식들의 점수가 모두 더해진다.


-> 트리를 dfs 돌면서 번호를 매기면, 루트 노드 부터 자식들이 연속해서 들어있는 배열을 만들 수 있다. = 트리 순회 배열이라고 한단다.



2. 쿼리


트리 순회 배열에 쿼리가 가해진다.


이제 쿼리는 배열의 일부 구간을 증가시키는 쿼리가 된다.


-> 일부 구간을 빠르게 증가시키는 방법이 필요하다.


-> 증가시켰으면 값이 얼마인지도 빠르게 알아낼 방법이 필요하다. = 펜윅트리의 ( range update & point query ) 모드를 사용하자.



3. 펜윅 트리


이 자료구조는 다음 두 기능을 로그시간에 제공하는 자료구조다.


1) update(p, v) : p번째 원소를 v만큼 증가시킨다.


2) query(p) : 첫번째 원소부터 p번째 원소까지의 합을 알려준다.


즉 point update & range query를 로그시간에 수행한다.


이를 조금만 응용하면 range update & point query 모드로 바꿀 수 있다.



원래 배열을 a라고 하고, 배열 b[x] = a[x] - a[x - 1] 이라고 정의해보자.


그러면 이제 a의 입장에서, a[x]는 b[x] + b[x - 1] + ... 즉 누적합이 된다.


이제 두 기능을 b에 대고 수행한다고 생각해보자.


1) update(p, v)


-> 예를 들어 update(3, v)라면, a[1]과 a[2]는 가만히 있고, a[3]부터 v씩 늘어난 것이다. 왜냐하면 b의 정의 때문에.


따라서 [from, to] 구간을 v만큼 증가시키고 싶다면, update(from, v) 와 update(to + 1, v) 두 번으로 배열 a를 다 조질수 있다.


2) query(p)


-> b[1] + b[2] + ... + b[p] = a[p] 이니까, a의 p번째 원소 값을 구하는 쿼리로 변경되었다.



이처럼 펜윅트리는


1) point update & range query


2) range update & point query


3) range update & range query


총 3가지 모드를 제공한다. 3번째 모드는 차후에 설명하는 것으로.. ㅎㅎ




이제 트리에 가해지는 쿼리를, 펜윅트리에서 로그시간에 수행할 수 있게 되었다.


하지만


1) 모든 쿼리를 수행해보면서 매번 모든 가수가 평균 점수를 넘는지 확인


2) 모든 가수마다 쿼릐를 수행해보면서 언제 평균 점수를 넘는지 확인


어떤 방법으로도 N * K * log(N)으로 시간이 오바된다.



4. 시간 줄이기


포인트는 가수들의 평균점수는 쿼리들이 수행되는 동안 절대 내려가지 않는다는 점이다.


따라서 단조증가하고, 이는 이분 탐색을 떠올리게 해준다.


하지만 가수마다 이분 탐색으로 조지는 것 보다, 모든 가수들의 구간을 줄여나가는 방법이 있단다. -> 병렬 이분 탐색



이 알고리즘의 구조를 보면, 가수마다 구간이 있고 구간의 중앙값은 타겟이 된다.


이제 쿼리를 순차적으로 수행할 텐데, 현재 수행하는 쿼리가 타겟과 같다면 그 가수는 구간을 반으로 줄일 수 있다.


쿼리를 전부 수행하고 나서, 구간이 변화한 가수가 있다면, 다시 처음부터 쿼리를 수행하는 짓을 반복한다.


말로는 머가 개선된건지 모르겠지만, 나중에 코드로 보면 더 빠르겠구나 할 꺼다.




'알고리즘 > 미분류' 카테고리의 다른 글

백준) 15668 방 번호  (0) 2018.10.02
백준) 16116 작은 큐브러버  (0) 2018.10.01
codeforces educational 50 round div2 참여기록  (0) 2018.09.09
SCC 문제들! 백준) 2150, 4013, 4196  (0) 2018.07.22
백준) 2512 예산  (0) 2018.07.19

A를 6분에 풀고


B에서 너무 시간을 오래 잡아먹었다.


관찰결과, (x,y)에서 |x|==|y| 이거나 절대값 차이가 홀수냐 짝수냐에 따라 다 다르길래 마음만 급해서 구현실수하구....


C에서 너무 수학적으로 생각하느라 또 시간 소비.


D는 그나마 빨리 풀었다. 그리디하게 생각한게 적중.


다시 C로 돌아와서 허어ㅓㅓㅓㅓㅓ 하다가 끝나버렸다.




문제의 C문제는 


0이 아닌 자릿수가 3개 이하인 자연수 = Classy number 가 [L, R] 구간에 몇 개나 있는지 세는 문제였다.


조합으로 수식 세우고 구현하면 되기도 하지만, 나처럼 구현상의 실수를 할 수 있다.


그래서 미리 Classy number를 다 구해놓고, (10^18 이하에서) 이분탐색으로 구간 상의 개수를 세면 되는 문제였다고 한다. ㅎㅎ


솔직히 이런 유형의 문제를 처음봤다. 미리 다 구해노코 빠박하는게 좀 더 컴퓨터적인 사고인거 같은데,


수학적으로만 접근 한걸 보면 백준만 허구헌날 해서 그런가 싶기도 하고...



'알고리즘 > 미분류' 카테고리의 다른 글

백준) 16116 작은 큐브러버  (0) 2018.10.01
백준) 15957 음악 추천 (퇴고전)  (0) 2018.09.11
SCC 문제들! 백준) 2150, 4013, 4196  (0) 2018.07.22
백준) 2512 예산  (0) 2018.07.19
백준) 11003 최소값 찾기  (0) 2018.07.13

- 통신 회선

- 위성 마이크로파 : 지상에서 통신 위성으로 마이크로 주파수를 쏘면, 증폭해서 지상으로 송신한다.

1. FDMA = frequency division multiple access : 주파수 대역폭을 일정 간격으로 분할하는 방식

2. TDMA = time ~ : 사용시간을 분할하는 방식

3. CDMA = code ~ : 주파수나 시간을 모두 공유하는 대신 데이터에 특별한 코드를 부여함

- 교환 방식

1. 회선 교환 : 전화망, 데이터 전송전에 경로가 설정되어야 한다.

2. 축적 교환 방식

2-1) 메세지 교환 : 물리적 경로가 성립되지 않는다. 대신에 한 홉씩 뛰면서 전체 메세지가 이동한다.

2-2) 패킷 교환 : 메세지가 너무 크면 중간 홉들이 고생한다. 따라서 패킷으로 분할되어 이동한다.

2-2-1) 가상 회선 방식 = TCP : 미리 논리적인 통신 회선을 성립시킨뒤 운반함. 패킷의 송수신 순서가 같다.

2-2-2) 데이터그램 방식 = UDP : 패킷들이 알아서 날라감.


- 통신 방식

1. 단방향 통신 = simplex : 티비, 라디오

2. 반이중 통신 = half-duplex : 양방향으로 전송이 가능하지만, 동시에 양쪽에서는 전송할 수 없다. 무전기.

3. 전이중 통신 = full-duplex : 동시에 양방향 전송이 가능함. 전화기.


- 전송 방식

1. 비동기식 전송 : 문자들을 전송하는데, 한 문자를 나타내는 문자 코드 앞뒤에 start/stop bit를 붙여 구분하는 방식.

- 효율이 떨어진다. 저속 단거리. 휴지 상태가 존재.

2. 동기식 전송 : 문자열을 프레임으로 만들어 일시에 전송하는 방식.

- 휴지 시간이 없고, start/stop bit가 없어서 전송효율이 좋다. 원거리 통신. 단말기는 버퍼를 내장해야 한다.

2-1) 문자 위주 동기 방식 : SYN 등의 동기 문자로 동기를 맞추는 방식.

2-2) 비트 위주 동기 방식 : 데이터 블록 처음과 끝에 플래그 필드 사용 = HDLC


- 변조 = modulation : 신호를 전송 매체의 특성에 맞춰 적절한 파형으로 변화시키는 것.

1. 아날로그 변조

1-1) 연속파 변조 : AM, FM

1-2) 아날로그 펄스 변조 : PAM, PWM, PPM


2. 디지털 변조 : 디지털 데이터를 아날로그 신호로 변환 = keying

2-1) ASK = 진폭 편이 변조 : 0과 1을 다른 진폭의 신호로 변조. 잡음에 약함.

2-2) FSK = 주파수 편이 변조 : 0과 1을 다른 주파수로 변조

2-3) PSK = 위상 편이 변조 : 0과 1을 서로 다른 위상의 신호로 변조. 한 위상을 1비트/2비트/3비트로 대응시켜 전송할 수 있음.

2-4) QAM = 직교 진폭 변조 : 젤 빠르대. 진폭과 위상의 콤비네이션


- 펄스 코드 변조 : 동영상 같이 연속적인 시간과 진폭을 가진 아날로그 데이터를 디지털 신호로 바꾸는 방식. 코덱을 사용한다.

1. 송신측

1-1. 표본화 : 시간 단위로 끊기 -> PAM

1-2. 양자화 : 값으로 바꾸기 -> PCM

1-3 .부호화 : 2진수로 바꾸기

2. 수신측 : 복호화 -> 여파화


- 오류 제어 수정

1. 전진 오류 수정 = FEC = forward error correction

- 재전송 요구 없이 수신 측이 알아서 고치는 방식. 따라서 역채널이 필요없고, 연속적인 데이터 흐름이 가능하다.

- 하지만 오류 검출을 위한 추가 잉여 비트들이 필요해져서 효율은 떨어진다.

- 종류

1. 블록형

- 해밍코드

- 해밍 거리란 몇 개의 글자가 다른지를 말한다.

- 검출 보장 s + 1 = 해밍거리

- 정정 보장 t * 2 + 1 = 해밍거리

- CRC

2. 합성곱, convolution, 비블록형


2. 후진 오류 수정 = BEC = backward error correction

- 오류가 발생하면 송신 측에 재전송을 요구하는 방식

- 패리티 검사, CRC 등으로 오류가 있음을 알아내고, 오류 제어는 자동 반복 요청 = ARQ에 의해 이루어진다.


- 맨체스터 코딩 방식 : 물리 계층에서 신호를 디지털화 시키는 방법 중에 한 형태

- 데이터를 이진화하고 클록신호화 XOR하여 인코딩한다.



- 맨체스터 신호의 극성이 각 비트 중앙에서 반전되며, 방향이 논리상태를 결정한다.


- baud = 보 = Bd = 초당 펄스 수 = 초당 심볼 수 = 변조 속도

- 트리비트를 사용할 경우 : 전송속도 bps = 변조 속도 * 3


- ARQ = automatic repeat query = 자동 재전송 요구 : 전송계층의 프로토콜

1. 정지 대기 방식 = stop and wait : 한 번에 하나식 ACK을 받고 전송, 받고 전송... 단순하나 비효율적

2. go back and ARQ = continuous ARQ = 연속적 ARQ : 여러개를 보내고 하나의 ACK을 받음. 슬라이딩 윈도우 방식. 오류부터 싹다 재전송해야 함.

3. selective repeat ARQ = 선택적 ARQ = 선택적 재전송 : 연속적 ARQ와 비슷하지만, 오류있는 부분만 재전송하면 됨 ㅎㅎ.


- PAD = packet assembler + disassembler = 패킷 조립 분해 장치 : 비동기형 터미널 사용자가 패킷망에 접속할 때 패킷화/비패킷화를 도와주는 어댑터


- LAN : 한 건물이나 일정 지역 내에서 단말기들을 고속 전송회선으로 연결하여 공유시키는 네트워크 형태

- 망의 구성 형태에 따라 분류


- 케이블에 따른 분류

- ㅁ BASE T : 전송속도가 ㅁMbps, 디지털 신호 전송 방식의 T 케이블(트위스티드 페어 케이블)을 사용함

- ㅁ BASE 2 : 한 세그먼트의 최장 길이가 2*100 미터임을 나타냄.


- 계층 구조

- 물리 계층 = OSI 7계층에서 물리 계층과 동일

- 데이터 링크 계층

- 데이터 링크 : 인접한 두 통신기기 간에 개설되는 통신채널

1. 점재점 링크 : 주소가 필요 없음

2. 점대 다중점 링크 : 한 노드가 여러 노드와 링크되므로 주소가 필요함

- 잡음 가능성이 있는 인접 노드간의 물리적인 회선을 에러가 없는 데이터 링크로 바꿔서 상위 계층이 사용하게 해주는 계층

- 프레이밍, 흐름제어(속도차이 보상), 에러제어, 순서화, 등의 기능 = 전송 제어


1. LLC 계층(상위) = logical link control

- MAC과 네트워크 계층간의 접속을 담당한다. MAC의 다양한 토폴로지에 상관없는 통신을 보장

- HDLC와 매우 유사하고, 부분집합이래.


2. MAC 계층(하위) =  media access contorl

- 여러 단말들이 공유 채널에 접속할 때, 단말 간의 충돌/결합을 제어하는 계층

- 하위 물리계층에서 올라오는 비트열들을 의미있는 단위로 나눠주는 프레이밍 기능


2-1. CSMA = CS(carrirer sense) + MA(multiple access) 반송파 감지 다중 접속

-단말들이 접근하기 전에, 먼저 매체가 사용중인지 반송파 감지를 통해 확인하며 다중접속하는 방식

2-1-1) CSMA-CD = collision detection = 충돌 방지 

- 버스형 LAN에서 사용하는 방식, 구현이 Ethernet이고, IEEE 802.3 표준이다. 

2-1-2) CSMA-CA = collision avoidance = 충돌 회피

- 무선 LAN에선 충돌 방지가 불가능했다. 따라서 노력한답시고 난수화된 시간만큼 미사용상태를 대기한다. 점차 오래 기다린다.


2-2. 토큰 링 : 한 제어 토큰이 링을 순환하며 단말들의 접속을 제어한다.

-  제어 토큰을 갖고 있어야 전송 모드가 되고, 토큰을 보유한채 데이터를 링에 흘리면서 전송되는 방식.

-  이더넷에 밀려 사장되었다. ㅋ


2-3. 토큰 버스 : CSMA + 토큰링

- 물리적으로는 버스형이지만, 논리적으로 제어토큰이 토큰링마냥 돌아댕긴다.

- 충돌이 없어 충돌제어가 필요없고, 한 패킷 전송에 일정한 시간이 걸린다.




- HDLC : 컴퓨터간 데이터 통신에 적합한 프로토콜, 모든 데이터 링크 종류를 지원한다. 단방향, 반이중, 전이중.

- 비트 지향형

- 오류 제어기능 : CRC필드 사용, ARQ, Bit Stuffing(모든 비트에 연속적으로 1이 5개 있으면 0을 강제로 추가하여 오류 감지)

- 흐름 제어기능 : 수신측의 응답을 기다리지 않고, 버퍼로 흐름을 제어함

- 데이터 전송 모드의 종류

1. 표준 응답 모드 = NRM : 반이중 점재점 통신, 종국은 주국의 허가가 있을때만 송신할 수 있다.

2. 비동기 응답 모드 = ARM : 전이중 점대점 불균형 통신

3. 비동기 균형 모드 = ABM : 전이중 점대점 균형 통신

- 프레임 종류

1. HDLC 프레임

2. Information 프레임 : 제어필드가 0으로 시작, 데이터를 주로 담는데, 피기백킹시에도 사용된다.

- piggybacking : 수신측이 데이터 프레임에 ack를 실어서 전송하는 기법

3. Supervisor 프레임 : 제어필드가 10으로 시작, 오류제어, 흐름제어

4. Unnumbered 프레임 : 제어필드가 11로 시작, 오류회복, 어떤 전송 모드인지.

- 플래그필드 : 프레임의 시작과 끝을 알리는 패턴 = 01111110

- 주소부 : 송/수신국을 구분하기 위해 사용. broadcast 방식은 1111 1111

- 제어부 : 프레임 종류 식별용

- 정보부 : 실제 데이터가 들어있다.

- FCS = frame check sequence : 오류 검출용. 주로 crc를 쓴대.


- BSC = binary synchronous contorl : 문자 위주의 프로토콜. 반이중 방식만 가능.

- 전송을 제어하는 문자들

1. EOT = end of transmission : 전송 종료와 데이터링크 해제

2. ENQ = enquiry : 상대방에 데이터 링크 설정과 응답 요구

3. DLE = data link escape : 전송 제어 문자앞에 삽입해 전송 제어 문자임을 알리는 용도 = 투과성

4. ACK / NAK



- IEEE 802의 표준 규격

- 802.1 : 전체구성

- 802.11 : 무선 LAN




- 프로토콜의 삼요소, 삼대장

1. 구문 : 문법

2. 의미 : 비트들의 패턴을 어떻게 해석할지, 무슨 동작인지 정의. 전송 제어, 오류 제어에 관한 규정

3. 타이밍 : 통신속도와 순서제어에 관한 규정


- 라우팅 테이블 관리 프로토콜



- RIP : 벨만 포드 // OSPF : 다익스트라


- 다중화 기법 = 멀티플렉싱 : 저수준 채널들을 고수준의 채널로 통합하기


1. FDM = frequency division multiplexing = 주파수 분할 다중화 : 라디오에 채널 나눠진거랑 똑같음!

2. TDM = time division multiplexing = 시분할 다중화 : 여러 채널들이 한 전송로의 시간을 나눠가진다.

2-1 STDM = synchronous TDM = 동기식 시분할 다중화 : 슬롯에 빈 공간이 있기도 하다



2-2 ATDM = asynchronous TDM = 비동기식 시분할 다중화 = 통계적 시분할 다중화 : 빈슬롯이 없죠?



- 신호대 잡음비 :  S = 신호 전력량, N = 잡음 전력량


- 채널 용량 = 대역폭 * log2(1 + S/N)

- ex) 3000Hz의 대역폭을 가지며 신호대잡음비가 30데시벨인 시스템의 채널 용량은, 3000 * log2(1 + 10^(30 / 10)) = 3000 * log2(1001)


- X.25 : OSI 프로토콜과 비스무리한 프로토콜이래

- 데이터 링크 계층 = 프레임(링크) 계층

- 네트워크 계층 = 패킷 계층


- IPv4 -> IPv6

- 유니캐스트 멀티캐스트 브로드캐스트 -> 유니캐스트 멀티캐스트 애니캐스트

- 천이 기법

1. 터널링 : 캡슐화

2. header translation

3. dual stack


- hand off = hand over 

- 통화 중 기지국간 이동을 원할하게 유지시켜 주는 기술

- 접속을 끊는게 off, 이동하는게 over


- OSI 7 계층 당 데이터 전송 단위

1계층 물리계층(Physical Layer) - 데이터 전송 단위 : 비트(bit)

2계층 데이터링크 계층(Data Link Layer) - 데이터 전송 단위 : 프레임(frame)

3계층 네트워크 계층(Network Layer) - 데이터 전송 단위 : 패킷(packet)

4계층 전송 계층(Transport Layer) - 데이터 전송 단위 : TCP 일 때 Segment / UDP 일 때 Datagram

5계층 세션 계층(Session Layer) - 데이터 전송 단위 : 메시지(message)

6계층 표현 계층(Presentation Layer) - 데이터 전송 단위 : 메시지(message)

7계층 응용 계층(Application Layer) - 데이터 전송 단위 : 메시지(message)



'정보처리기사 공부' 카테고리의 다른 글

단편적으로 정리 - 소프트웨어 공학  (0) 2018.07.30
단편적으로 정리 - 운영체제  (0) 2018.07.25
단편적으로 정리 - 전자 계산기 구조  (0) 2018.07.25
단편적으로 정리 - 데이터베이스  (0) 2018.07.23

+ Recent posts

티스토리툴바