제1-1장: 변수, 배열, 반복문 (5/7)

📌 매일 하는것이 제일 중요하다!

• Inflearn - Java로 배우는 자료구조
• 깃허브 저장소

---

- 1~100000사이의 모든 소수를 찾기

하나의 소수(Prime number)를 찾는 것은 컴퓨터 공학에서 아주 중요하다.

가장 기본적인 방법은 단순히 이런걸 생각했었다.

int n = 30;
for(int i = 2; i <= n; i++{//2부터 n까지 수를 검사
    if(n % i == 0) {//n이외의 수에서 나누어진다면
        break;//멈춤
    }

}

하지만 그것보다 소수는 1과 자신으로 나누어진 수 라는 특징을 이용해서 그렇다면 2로 나누어 지기만 해도 소수가 아니게 되므로

for (int i = 2; i <= n / 2; i++)

n을 2로 나누어 주어서 코드의 실행 시간을 줄일 수 있게된다.

여기서 더 나아가 2로 나누어 지므로 루트2도 가능한데 표현할 수 없으고 i=2로 시작하는 식을 이용해

for (int i = 2; i * i <= n; i++)

추가로 boolean타입을 이용해 나머지가 0일 때 false형식인 flag를 만들어 for이 실행 때 멈추게 할 수 었있다.

boolean isPrime = true; // 소수 판별기
for (int i = 2; i * i <= n && isPrime; i++)// i가 루트n보다 작다 == i*i <= n 이다(헐?)
    if (n % i == 0) { // 소수가 아니라는 증거
    isPrime = false;
} // 소수가 아님에도 계속 for를 하는것은 자원낭비

---

- 중복된 정수 쌍의 개수를 카운트하기

솔직히 이건 글로 이어서 설명하기 힘들것 같아 코트에 주석을 달아 흐름대로 설명해 놓았다

// # 사용자로부터 먼저 정수의 개수 n을 입력받는다
// 이어서 n개의 정수를 입력받아 순서대로 배열에 저장한다.
// 그런 다음 중복된 정수 쌍의 개수를 카운트하여 출력하라.
// 예를 들어 n=6이고 입력된 정수들이 2,4,2,4,5,2이면 정수쌍은
// (2,2), (2,2), (2,2), (4,4)로 모두 4쌍이다

// 제일 간단한 방법
// 모든 쌍을 검사하기

Scanner kb = new Scanner(System.in);
int n = kb.nextInt();// 정수 입력받기
int[] data = new int[n];// 입력받은 정수의 크기만큼 data 정수 배열 생성

for (int i = 0; i < n; i++)// 0부터 n-1번 반복
data[i] = kb.nextInt();// data배열에 숫자를 입력
kb.close();// 자원낭비 줄이기

// 모든쌍을 검색할 때는 항상 두개의 중첩된 for문 -> "패턴"
int count = 0; // 중첩카운트
for (int i = 0; i < n; i++) { // 0부터 n-1번 반복
    for (int j = i + 1; j < n; j++) { // j는 항상 i+1의 수부터 시작 -> i와 같은 위치로 중첩될 일을 방지
    if (i != j && data[i] == data[j])//즁복조건
    // (중요) i != j -> i와 j과 같다면 비교가 안되고 있다는 상황
    //data[i] == data[j] -> data[j]는 언제나 data[i+1]
    count++; //카운트 해주기
    }
}

---

Review

• 갑자기 루트를 써서 당황했었다. 하지만 이게 자연스럽게 나오신다니 나도 언제 저렇게 될 지 걱정이 생겼다.
• for문에는 습관처럼 반복되는 숫자들만 작성했는데 조건을 추가해 for문에서 바로 멈추는게 하는것은 새로운 관점으로 보게되는 좋은 코드라고 느꼇다
• 처음부터 다 이해하려 하지 이해한만큼 알고 넘어간 후 안되면 다시 보자
  • 다 이해하려다 소화불량으로 죽을지도 몰라...