알고리즘 ) 과제( 26.3.20)

 

 

 

hw1

 

 

 

Requested array size exceeds VM limit

int[] totalArr=new int[Integer.MAX_VALUE-1];

 

 

 

 

배열의 크기가 얼마가 될지 모를때

리스트는알아서 해주고, size로 갯수얼마인지 알아낼수있으니깐 

int[] totalArr=new int[arrList.size()];

 

 

 

리스트로 만든다음 배열로 변환방법

 

int[] array = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
    array[i] = list.get(i); // 자동으로 Integer가 int로 바뀝니다(Unboxing)
}

• 장점: 에러(IndexOutOfBounds 등)가 났을 때 어느 줄인지 바로 알 수 있고, 가장 빠릅니다.
• 단점: 코드가 3~4줄로 길어집니다.

 

 

 

1. 정렬 알고리즘(Shell Sort)의 논리 오류:
   • 현재 코드: chosen2RandomIndexAndTotal[j] < chosen2RandomIndexAndTotal[j-h] 조건에서 교환은 j와 j-1을 하고 있습니다. 쉘 정렬은 j와 j-h를 비교하고 교환해야 합니다. 지금 코드는 h가 1이 되는 순간에만 제대로 작동하는 불완전한 삽입 정렬 형태입니다.
2. 중복 제거의 효율성:
   • arrList.indexOf(...) != i를 쓰면 리스트를 처음부터 끝까지 매번 뒤져야 하므로 속도가 매우 느려집니다

 

 

 

방법 1: "이미 봤던 숫자인지 체크하는 체크리스트" 활용 (강력 추천)

2try에서 numLimit = 101로 배열을 만드셨던 것과 같은 원리입니다.

• 힌트: 두 수의 합(i + j)이 가질 수 있는 최대값은 얼마일까요? (0~100 사이의 두 수를 더하니까요.)
• 논리: 그 최대값 크기만큼의 boolean[] 배열을 하나 만듭니다. (예: boolean[] isExist = new boolean[201];)
• 적용: 두 수를 더한 결과가 15라면, 리스트에 넣기 전에 isExist[15]가 true인지 확인합니다.
  • false라면? 처음 보는 숫지이니 리스트에 add하고 isExist[15] = true로 바꿉니다.
  • true라면? 이미 리스트에 들어있는 숫자이니 무시하고 넘어갑니다.
• 효과: indexOf는 리스트를 처음부터 다 뒤져야 하지만(), 배열 인덱스 접근은 한 번에 끝납니다

 

 

 

• 문제 A (간격 h): h = 13으로 고정되어 있습니다. 만약 더해서 나온 결과 배열의 크기가 10개라면, j >= h 조건이 한 번도 참이 되지 않아 정렬이 아예 안 됩니다. (이거 while문으로 감싸야함)
• 문제 B (교환 대상): 쉘 정렬은 j와 j - h를 비교하고 교환해야 하는데, 현재 코드에서는 j와 j - 1을 교환하고 있습니다.

(-1 부분 모두 h로 바꿧는지 )

 

 

중복된 숫자가 입력될 때의 처리 (i == j)

문제 설명에 "서로 다른 인덱스에 있는 두 개의 수"라고 되어 있습니다. 만약 입력이 [1, 1, 2]라면, 인덱스 0번의 1과 인덱스 1번의 1을 더해 2라는 합이 나올 수 있어야 합니다.

• 현재 코드의 문제: if(i == j) continue; 때문에 같은 숫자가 두 개 있어도 i + i 연산을 아예 건너뜁니다.

 

 

 

 

 

뭔소리야 현재는 그 배열은 0인지 아닌지만 판단하기위함이고, 지금으  인덱스가 서로 같지않으면 수행하라고 

<잠깐만 중복인가 그러면 

j가 i부터 시작해야 

 

 

i와 j는 "인덱스"가 아니라 "숫자 그 자체(값)"**이기 때문에 생기는 문제입니다.

 

"내가 지금 숫자 i를 보고 있는데, 만약 원본에 이 숫자가 두 개 이상 있었다면? 그럼 i + i도 계산해서 리스트에 넣어줘야지!"

 

 

j = i + 1 일 때 생기는 일 (현재 코드)

j = i + 1이라는 뜻은 **"서로 다른 숫자끼리만 더하겠다"**는 뜻입니다.

• i=1, j=2 (1+2) ✅
• i=1, j=3 (1+3) ✅
• 하지만 i=1, j=1 (1+1)은 절대로 일어날 수 없습니다. (j는 항상 i보다 커야 하니까요)

2. 그런데 문제는 뭐라고 했나요?

"서로 다른 인덱스에 있는 두 수를 더해라."

이 말은 값이 같더라도 위치가 다르면 더할 수 있다는 뜻입니다.

 

 

 

 

 

 

이걸 어케 생각하냐고 ㅋㅋ

// [핵심] i와 j가 같은 숫자라면? 원본에 그 숫자가 2개 이상 있을 때만 더하기!
        if (i == j && countedEachElement[i] < 2) {
            continue;
        }

 

 

 

 

 

 

• 문제점: h를 줄여나가는 방식입니다.
  • 지금 코드: h-- (1씩 감소)
  • 이유: h를 1씩 줄이면 쉘 정렬의 핵심인 '간격(Gap) 효과'가 사라지고, 거의 매번 '삽입 정렬'만 반복하게 됩니다.
  • 수정: h를 처음에 h = h * 3 + 1로 계산하셨다면, 줄일 때는 다시 역순으로 h = (h - 1) / 3 또는 **h /= 3**으로 줄여야 쉘 정렬의 성능이 나옵니다.
• 시작 인덱스: for (int i = 1; ...) 보다는 **for (int i = h; ...)**로 시작하는 것이 정석입니다. (i가 h보다 작으면 j >= h 조건 때문에 어차피 루프가 돌지 않기 때문입니다.)

 

---

hw2

 

previous없이 어떻게 내부 반복문 만들지