5-J 강의 질문

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

5-J

작성

342

수정됨

안녕하세요 선생님 양질의 코드 매번 감사합니다.

강의를 들으며 살짝 헷갈리는 부분이 있는데요, 가장 먼 미래에 참조되는것을 swap 하는 알고리즘이라 하셨는데 이 가장 먼 미래라는게 상대적으로 먼 미래를 의미하는건가요?

예를들어 콘센트에 2번, 3번이 들어가 있을때

앞으로 나올 2번과 3번이 둘다 있는경우 이 두가지 중 더 멀리있는 거랑 swap 하는 건가요?

추가로 16번 라인에서 j 의 시작이 i + 1이 아닌 i 가 아닌지 생각이 듭니다.

만약 콘센트 2개 공간이 있고 2, 3, 1, 2, 3 순서로 사용을 한다고 할때, 먼저 2와 3이 콘센트에 들어가고 그다음 1이 들어갈때 이미 콘센트 공간이 가득차있으므로 2와 3중에 더 멀리 있는번호를 swap 하는건데 만약 i가 아닌 i + 1 부터 확인하게 된다면 1부터 확인하는게 아니고 2부터 확인하게 되는게 아닌가요? 그럼 한칸을 빼먹는거 같은데 이 부분이 좀 헷갈립니다.

http://boj.kr/680d6abc7e004d7886939b2513c31723

c++코딩-테스트

답변 3

큰돌

지식공유자

안녕하세요 명운님 ㅎㅎ

의를 들으며 살짝 헷갈리는 부분이 있는데요, 가장 먼 미래에 참조되는것을 swap 하는 알고리즘이라 하셨는데 이 가장 먼 미래라는게 상대적으로 먼 미래를 의미하는건가요?

>> 절대적으로 먼 미래입니다.

예를들어 콘센트에 2번, 3번이 들어가 있을때

앞으로 나올 2번과 3번이 둘다 있는경우 이 두가지 중 더 멀리있는 거랑 swap 하는 건가요?

>> 2 3 2 3 2 3 이고 콘센트가 2개 공간이 있다고 하면 2 3 이후에 swap이 이뤄지지 않습니다. 스왑을 해야할 때 가장 먼 미래에 참조되는 것을 기반으로 스왑합니다.

추가로 16번 라인에서 j 의 시작이 i + 1이 아닌 i 가 아닌지 생각이 듭니다.

    for(int i = 0; i < n; i++){
        if(!visited[a[i]]){
            if(v.size() == k){
                int last_idx = 0, pos;
                for(int _a : v){
                    int here_pick = INF;
                    for(int j = i + 1; j < n; j++){

이 부분 말씀하시는거죠?

2, 3, 1, 2, 3 일 때 1일 때

        if(!visited[a[i]]){
            if(v.size() == k){

이부분에 걸리게 되겠죠? 1은 visited에 없으니까요.

그러면 1과 어떤 영역과 스왑을 해야해? (이미 들어가있는 것중)

라고 되기 때문에 1은 절대 포함되지 않습니다. 1은 들어가지 않아있다.는 자명하며 들어가지 않았기 때문에 "스왑조차" 할 수가 없습니다.

그래서 1 이후의 숫자를 탐색하기 위해서

                for(int _a : v){
                    int here_pick = INF;
                    for(int j = i + 1; j < n; j++){

이렇게 드가는 것입니다. 들어가있는 vector v를 기반으로 1 이후의 숫자들을 기반으로 먼 미래에 swap되는 것을 탐색하는 것이죠.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

박희천

저도 질문자 분하고 똑같이 이해했는데...

답변 감사합니다.

이명운

질문자

아 두번째 질문은 이해가 갔습니다! 근데 아직 첫번째 질문은 조금 헷갈리는데, 절대적으로 먼 미래이면 가장 뒤에서 부터 탐색을 해야하지 않나요?

예를 들어 입력이

2 8

2 3 1 4 2 5 3 2

라면 처음 콘센트에 2와 3이 들어가고 그다음 가득 차게되어 swap을 해야하는데 가장 2와 3중 더 뒤에있는 값이 2 이므로(7번째 인덱스) 콘센트 에 들어있는 2를 스왑하는건가요?

코드를 보면 2(4번째 인덱스)와 3(6번째 인덱스)를 비교하여 더 멀리있는 3을 스왑하는것 같아서요

큰돌

지식공유자

안녕하세요 명운님 ㅎㅎ

절대적으로 먼 미래이면 가장 뒤에서 부터 탐색을 해야하지 않나요?

음 먼 미래라는 것은 발견되고 미래에 다시 발견되는 것을 의미하는 것이 아닙니다. 지금 이 시점에서 보았을 때 가장 먼 미래에서 참조되는 것을 골라야 하기 때문에 이 시점에서 오른쪽으로 즉, idx가 증가하는 방향으로 탐색해야 합니다.

제가 답변 드리면서 명운님 질문을 이해했는데요.

상대적이라고 볼 수 있을 거 같습니다.

지금 이 시점에서 보았을 때 처음으로 등장한 것 기준 가장 먼 미래에 참조되는 것

이라는 워딩이 더 정확할 거 같습니다.

아닙니다. 3과 스왑합니다.

2 3 1 4 2 5 3 2

여기서 1에 왔을 때 2가 먼저 참조, 3이 그 다음에 참조되기 때문에 3과 스왑하게 됩니다.

디버깅 코드는 다음과 같습니다.

#include<bits/stdc++.h>
using namespace std;
int k, n, a[104], visited[104], cnt;
const int INF = 987654321;
vector<int> v;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> k >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++){
        if(!visited[a[i]]){
            if(v.size() == k){
                int last_idx = 0, pos;
                for(int _a : v){
                    int here_pick = INF;
                    for(int j = i + 1; j < n; j++){
                        if(_a == a[j]){
                            here_pick = j; break;
                        }
                    }
                    if(last_idx < here_pick){
                        last_idx = here_pick;
                        pos = _a;
                    }
                }
                visited[pos] = 0;
                cnt++;
				cout << "SWAP : " << pos << '\n';
                v.erase(find(v.begin(), v.end(), pos));
            }
            v.push_back(a[i]); visited[a[i]] = 1;
        }
    }
    cout << cnt << "\n";
    return 0;
}

감사합니다.

이명운

질문자

친절한 답변과 디버깅코드 정말 감사합니다! 선생님덕분에 이해하였습니다!

인프런 커뮤니티 질문&답변

5-J 강의 질문