-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
5-J 강의 질문
23.08.28 16:18 작성 23.08.28 17:30 수정 조회수 258
2
안녕하세요 선생님 양질의 코드 매번 감사합니다.
강의를 들으며 살짝 헷갈리는 부분이 있는데요, 가장 먼 미래에 참조되는것을 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부터 확인하게 되는게 아닌가요? 그럼 한칸을 빼먹는거 같은데 이 부분이 좀 헷갈립니다.
답변을 작성해보세요.
1
큰돌
지식공유자2023.08.29
안녕하세요 명운님 ㅎㅎ
의를 들으며 살짝 헷갈리는 부분이 있는데요, 가장 먼 미래에 참조되는것을 swap 하는 알고리즘이라 하셨는데 이 가장 먼 미래라는게 상대적으로 먼 미래를 의미하는건가요?
>> 절대적으로 먼 미래입니다.
예를들어 콘센트에 2번, 3번이 들어가 있을때
앞으로 나올 2번과 3번이 둘다 있는경우 이 두가지 중 더 멀리있는 거랑 swap 하는 건가요?
>> 2 3 2 3 2 3 이고 콘센트가 2개 공간이 있다고 하면 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부터 확인하게 되는게 아닌가요? 그럼 한칸을 빼먹는거 같은데 이 부분이 좀 헷갈립니다.
>>
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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
0
이명운
질문자2023.08.29
아 두번째 질문은 이해가 갔습니다! 근데 아직 첫번째 질문은 조금 헷갈리는데, 절대적으로 먼 미래이면 가장 뒤에서 부터 탐색을 해야하지 않나요?
예를 들어 입력이
2 8
2 3 1 4 2 5 3 2
라면 처음 콘센트에 2와 3이 들어가고 그다음 가득 차게되어 swap을 해야하는데 가장 2와 3중 더 뒤에있는 값이 2 이므로(7번째 인덱스) 콘센트 에 들어있는 2를 스왑하는건가요?
코드를 보면 2(4번째 인덱스)와 3(6번째 인덱스)를 비교하여 더 멀리있는 3을 스왑하는것 같아서요
큰돌
지식공유자2023.08.29
안녕하세요 명운님 ㅎㅎ
절대적으로 먼 미래이면 가장 뒤에서 부터 탐색을 해야하지 않나요?
>>
음 먼 미래라는 것은 발견되고 미래에 다시 발견되는 것을 의미하는 것이 아닙니다. 지금 이 시점에서 보았을 때 가장 먼 미래에서 참조되는 것을 골라야 하기 때문에 이 시점에서 오른쪽으로 즉, idx가 증가하는 방향으로 탐색해야 합니다.
제가 답변 드리면서 명운님 질문을 이해했는데요.
상대적이라고 볼 수 있을 거 같습니다.
지금 이 시점에서 보았을 때 처음으로 등장한 것 기준 가장 먼 미래에 참조되는 것
이라는 워딩이 더 정확할 거 같습니다.
라면 처음 콘센트에 2와 3이 들어가고 그다음 가득 차게되어 swap을 해야하는데 가장 2와 3중 더 뒤에있는 값이 2 이므로(7번째 인덱스) 콘센트 에 들어있는 2를 스왑하는건가요?
>>
아닙니다. 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;
}
감사합니다.
답변 3