임시) 탐색

깊이 우선 탐색

 

가장 많이 사용, 매우 중요

• 인접 리스트, 방문 배열을 만들고 시작
• 스택을 쓸지, 재귀를 쓸지 알아서, 보통 재귀를 쓰긴 함

스택과 재귀의 유사성

1. 호출 스택(Call Stack) 사용:
   • 재귀 함수: 재귀 함수가 호출될 때마다 현재 함수의 실행 상태(매개변수, 로컬 변수 등)가 호출 스택에 저장됩니다. 함수가 종료되면, 스택에서 이전 상태로 되돌아갑니다.
   • 스택: 명시적으로 데이터를 쌓고 제거하는 데이터 구조로, 후입선출(LIFO) 원칙을 따릅니다.
2. 후입선출(LIFO) 원칙:
   • 재귀 함수: 가장 마지막에 호출된 함수가 가장 먼저 종료됩니다. 이는 스택의 후입선출 원칙과 동일합니다.
   • 스택: 가장 마지막에 추가된 데이터가 가장 먼저 제거됩니다.
3. 함수 호출 관리:
   • 재귀 함수: 각 재귀 호출은 호출 스택의 새로운 프레임으로 추가됩니다. 함수가 반환되면, 해당 프레임이 제거됩니다.
   • 스택: 명시적으로 함수 호출을 스택에 저장하고, 함수가 종료되면 스택에서 제거할 수 있습니다.

재귀 함수 예시

public class RecursionExample {
    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println(result);// 출력: 120
    }

    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}

스택을 사용한 예시

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println(result);// 출력: 120
    }

    public static int factorial(int n) {
        Stack<Integer> stack = new Stack<>();
        int result = 1;

        while (n > 1) {
            stack.push(n);
            n--;
        }

        while (!stack.isEmpty()) {
            result *= stack.pop();
        }

        return result;
    }
}

23번, 연결 요소의 개수 구하기

 

• 연결요소 → 에지로 연결된 노드의 집합
• dfs가 한 번 완료될 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단할 수 있다 → 즉 dfs가 몇 번 실행됐는지로 알 수 있다
• 자바에서 static은 뭘 뜻하고 어떤 역할을 하며, 주로 어떨 때 사용되지?
• 요약
  • Static 키워드는 클래스 레벨에서 변수를 선언하거나 메서드를 정의할 때 사용되며, 인스턴스 없이 접근 가능합니다.
  • Static 변수는 클래스의 모든 인스턴스가 공유하는 변수입니다.
  • Static 메서드는 클래스의 인스턴스 없이 호출할 수 있는 메서드입니다.
• Static의 의미와 역할
  1. 클래스 레벨에서의 공유:
     • static 변수는 클래스의 모든 인스턴스가 공유하는 변수입니다.
     • 클래스의 모든 인스턴스는 같은 static 변수에 접근하고, 이를 통해 값을 읽고 쓸 수 있습니다.
  2. 메모리 절약:
     • static 변수는 클래스 로딩 시점에 메모리에 할당되고, 프로그램 종료 시까지 유지됩니다.
     • 동일한 값을 가지는 변수가 여러 인스턴스에 걸쳐 반복되는 것을 방지합니다.
  3. 유틸리티 메서드:
     • static 메서드는 인스턴스화 없이 호출할 수 있는 메서드입니다.
     • 흔히 유틸리티 클래스에서 자주 사용됩니다. 예를 들어, java.lang.Math 클래스의 메서드들(Math.abs(), Math.max() 등)은 모두 static 메서드입니다.
• Static 변수
  • 클래스의 모든 인스턴스가 공유하는 변수입니다.
  • 클래스 로딩 시점에 메모리에 할당됩니다.

public class Counter {
    public static int count = 0;

    public Counter() {
        count++;
    }
}

public class Main {
    public static void main(String[] args) {
        Counter c1 = new Counter();
        Counter c2 = new Counter();
        Counter c3 = new Counter();
        
        System.out.println(Counter.count); // 출력: 3
    }
}

• Static 메서드
  • 클래스의 인스턴스 없이 호출할 수 있는 메서드입니다.
  • static 메서드에서는 인스턴스 변수나 인스턴스 메서드에 직접 접근할 수 없습니다.

public class MathUtils {
    public static int add(int a, int b) {
        return a + b;
    }
}

public class Main {
    public static void main(String[] args) {
        int sum = MathUtils.add(5, 3);
        System.out.println(sum); // 출력: 8
    }
}

• Static의 사용 사례
  1. 상수 정의:
     • static final 키워드와 함께 사용하여 클래스 전체에서 공유되는 상수를 정의할 때 사용합니다.
     • 예를 들어, public static final double PI = 3.14159;.
  2. 유틸리티 클래스:
     • 자주 사용되는 메서드를 정적 메서드로 정의하여 인스턴스화 없이 호출할 수 있도록 합니다.
     • 예: java.lang.Math, java.util.Collections.
  3. 싱글톤 패턴:
     • 클래스의 유일한 인스턴스를 관리할 때 정적 변수와 정적 메서드를 사용합니다.
• ArrayList<Integer>라는 자료 구조가 자바에 있고
  • new ArrayList<Integer>(); 이런 식으로 생성해주는구나
  • A[s].add(e) // add라는 함수가 있구나

24번, 신기한 소수 찾기

• 이 문제는 재귀 함수에 자릿수 개념을 붙여 구현
• 소수는 약수가 1과 자기 자신인 수
• 소수 판별은 보통 에라토스테네스의 체를 사용, 여기서는 단순한 소수 판별 함수를 사용해도 시간 안에 문제 풀 수 있음
• n=4일 때의 흐름
  1. 초기 설정:
     • 입력 N=4
     • 일의 자리 소수 2, 3, 5, 7을 시작점으로 DFS를 호출합니다.
  2. DFS 호출:
     • 각 일의 자리 소수에 대해 DFS 호출이 시작됩니다.
     • 예를 들어, DFS(2, 1) 호출이 시작됩니다.
• 예시를 통해 n=4일 때의 동작 과정을 자세히 설명하겠습니다.
• DFS(2, 1) 호출
  1. DFS(2, 1) 내부 로직:
     • 현재 number = 2, jarisu = 1 (현재 자리수)
     • jarisu가 N과 같지 않으므로 종료 조건에 도달하지 않습니다.
     • for문을 통해 다음 자리수를 탐색합니다.
  2. for 루프 (i=1 to 9):
     • i=1: number * 10 + i = 21, 21은 소수가 아니므로 패스.
     • i=3: number * 10 + i = 23, 23은 소수이므로 DFS(23, 2) 호출.
• DFS(23, 2) 호출
  1. DFS(23, 2) 내부 로직:
     • 현재 number = 23, jarisu = 2
     • jarisu가 N과 같지 않으므로 종료 조건에 도달하지 않습니다.
     • for문을 통해 다음 자리수를 탐색합니다.
  2. for 루프 (i=1 to 9):
     • i=1: number * 10 + i = 231, 231은 소수가 아니므로 패스.
     • i=3: number * 10 + i = 233, 233은 소수이므로 DFS(233, 3) 호출.
• DFS(233, 3) 호출
  1. DFS(233, 3) 내부 로직:
     • 현재 number = 233, jarisu = 3
     • jarisu가 N과 같지 않으므로 종료 조건에 도달하지 않습니다.
     • for문을 통해 다음 자리수를 탐색합니다.
  2. for 루프 (i=1 to 9):
     • i=1: number * 10 + i = 2331, 2331은 소수가 아니므로 패스.
     • i=3: number * 10 + i = 2333, 2333은 소수이므로 DFS(2333, 4) 호출.
• DFS(2333, 4) 호출
  1. DFS(2333, 4) 내부 로직:
     • 현재 number = 2333, jarisu = 4
     • jarisu가 N과 같으므로 종료 조건에 도달합니다.
     • isPrime(number) 호출하여 2333이 소수인지 확인합니다.
     • 2333은 소수이므로 출력합니다: System.out.println(2333).
• 요약
  • DFS(2, 1)은 2에서 시작하여 23, 233, 2333을 탐색합니다.
  • 각 자리수마다 소수인지 확인하고, 소수라면 다음 자리수를 탐색합니다.
  • n=4일 때, 예를 들어 2333은 모든 자리수가 소수이므로 최종 출력됩니다.
  • 이 과정은 다른 일의 자리 소수인 3, 5, 7에 대해서도 동일하게 수행됩니다. 각 시작점에서 가능한 모든 신기한 소수를 탐색하게 됩니다.
• isPrime 함수의 흐름 설명

static boolean isPrime(int num) {
    for (int i = 2; i <= num / 2; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

1. 함수 설명:
   • 함수 isPrime는 주어진 숫자가 소수인지 판별합니다.
   • 소수란 1과 자기 자신 외에 다른 약수가 없는 숫자입니다.
2. 흐름 설명 (num=531일 때):
   • 입력: num = 531
   • for 루프: i가 2부터 num/2까지 순차적으로 증가하면서 num이 i로 나누어지는지 확인합니다.
   • 만약 531 % i == 0이 되는 i가 있다면, 531은 소수가 아닙니다.

• num=531일 때의 흐름:
  • num = 531
  • for (int i = 2; i <= 265; i++) { ... } (531 / 2 = 265.5이므로 정수 부분만 취해서 265까지 반복)
    • i=2: 531 % 2 != 0 (짝수 아님)
    • i=3: 531 % 3 == 0 (531은 3으로 나누어짐, 소수가 아님)
  • 따라서, 531은 소수가 아니므로 false를 반환하고 함수가 종료됩니다.
• for문에서 i <= num / 2를 한 이유
  1. 약수의 대칭성:
     • 어떤 수 num의 약수는 대칭적으로 존재합니다. 예를 들어, num의 약수 쌍 (a, b)가 있다면 a * b = num입니다.
     • 작은 값부터 순차적으로 확인할 때, 만약 i > num / 2라면 i와 곱해서 num이 되는 값 j는 j < num / 2입니다. 따라서 i <= num / 2 범위에서 모든 약수 쌍을 확인할 수 있습니다.
  2. 효율성:
     • 모든 숫자를 num까지 확인하면 불필요한 계산이 증가합니다.
     • i <= num / 2까지만 확인해도 충분히 소수 여부를 판단할 수 있습니다.
• i <= num / 2 조건은 효율성을 높이기 위해 사용되었습니다. 어떤 수 num이 소수인지 확인할 때 i를 num/2까지만 확인해도 충분한 이유는 다음과 같습니다:
• 개선된 isPrime 함수
• i <= num / 2 대신 더 효율적인 방법으로 i <= Math.sqrt(num)를 사용할 수 있습니다. 이는 num의 제곱근까지만 확인하면 충분하기 때문입니다. 왜냐하면 약수 쌍 중 하나가 항상 num의 제곱근 이하에 있기 때문입니다.

static boolean isPrime(int num) {
    if (num <= 1) return false; // 1 이하의 수는 소수가 아님
    if (num == 2) return true; // 2는 소수
    if (num % 2 == 0) return false; // 짝수는 소수가 아님 (2 제외)

    for (int i = 3; i <= Math.sqrt(num); i += 2) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

• 개선된 이유:
  • Math.sqrt(num)까지만 반복하면 되므로 더 적은 반복 횟수로 소수 판별이 가능합니다.
  • 짝수를 미리 걸러내어 홀수만 검사하므로 효율적입니다.

25번, 친구 관계 파악하기

• 주어진 모든 노드에 dfs를 수행하고, 재귀의 깊이가 5이상(5개의 노드가 재귀 형태로 연결)이면 1, 아니면 0을 출력
  • 재귀 호출마다 깊이를 더함. 깊이가 5가 되면 1을 출력하고 프로그램 종료
• dfs의 복잡도는 v+e이므로 최대 4000, 모든 노드를 진행했을 때 4000*2000=8,000,000이므로 dfs를 사용해도 제한 시간 내 풀 수 있음
  1. arrive 변수의 용도
• arrive 변수는 주어진 그래프에서 깊이 5의 경로가 있는지를 확인하는 데 사용됩니다. 깊이 우선 탐색(DFS) 중 하나의 깊이가 5인 경로가 발견되면 arrive를 true로 설정하고 더 이상의 탐색을 중단할 수 있습니다.
  • 탐색 종료 플래그: arrive 변수가 true로 설정되면 DFS는 더 이상 탐색을 수행하지 않습니다. 이는 불필요한 탐색을 방지하고 효율성을 높이는 데 사용됩니다.
  • 결과 반환: 메인 함수에서 arrive 변수를 확인하여 깊이 5의 경로가 있는지 여부를 출력합니다.
• 용도:
• 왜 필요한가?:
  • 효율성: 하나의 깊이 5의 경로를 발견하면, 탐색을 중단하고 나머지 경로를 탐색할 필요가 없습니다. arrive 변수를 사용하면 불필요한 탐색을 피할 수 있습니다.
  • 명확성: arrive 변수를 사용하여 탐색이 종료된 이유를 명확하게 할 수 있습니다. 이는 코드의 가독성을 높이고 유지보수를 쉽게 합니다.
  • 만약 arrive 변수를 사용하지 않으면, DFS를 통해 모든 경로를 탐색해야 하며, 불필요한 계산이 증가할 수 있습니다. 탐색이 끝나더라도 확인된 깊이 5의 경로를 통해 프로그램을 종료해야 합니다.
  1. visited[now] = false;를 하는 이유
• visited[now] = false;는 DFS 탐색이 완료된 후, 해당 노드를 방문하지 않은 상태로 되돌리는 작업입니다. 이는 백트래킹(backtracking)을 구현하기 위해 필요합니다.
• 왜 필요한가?:
  • 백트래킹: DFS는 재귀적으로 호출되며, 특정 경로를 탐색한 후에는 다른 경로를 탐색하기 위해 이전 상태로 돌아가야 합니다. 이를 백트래킹이라 합니다. visited[now] = false;는 현재 노드를 방문하지 않은 상태로 되돌려 다른 경로를 탐색할 수 있도록 합니다.
  • 다른 경로 탐색: 그래프 탐색 시, 모든 가능한 경로를 확인해야 합니다. 현재 노드를 방문하지 않은 상태로 되돌리면, 다른 경로를 탐색할 때 이 노드를 다시 방문할 수 있습니다.
• 즉 내가 헷갈린 이유는, 이론과 기본 개념을 설명할 땐 기능을 그래프 완전 탐색에 초점을 두고 설명함
  • 따라서 한 번 방문한 노드는 다시 할 필요 없잖아. 완전 탐색이 목적이니까
  • 반면 이 문제의 경우 완전 탐색이 아니라, 깊이가 5인 경로가 있는지를 판단하는 것이 목적이기에, 이 부분을 개조한 거지. 목적에 맞게 튜닝했다 정도.

이제 visited[now] = false;가 있는 경우와 없는 경우의 차이를 예를 통해 설명해 보겠습니다.

예시: 작은 그래프 탐색

코드 복사
0 - 1
|   |
2 - 3

• DFS(0, 1)을 호출하여 시작합니다.
• visited[0] = true로 설정됩니다.
• DFS(1, 2)를 호출하고 visited[1] = true로 설정됩니다.
• DFS(3, 3)을 호출하고 visited[3] = true로 설정됩니다.
• DFS(2, 4)을 호출하고 visited[2] = true로 설정됩니다.
• 깊이가 5에 도달하지 않았으므로 백트래킹이 필요합니다.
• visited[2] = false로 되돌리고, 이전 호출로 돌아가 다른 경로를 탐색합니다.

이 과정에서 visited[now] = false가 없다면, 이미 방문한 노드를 다시 방문할 수 없게 되어 다른 경로 탐색이 불가능해집니다.

너비 우선 탐색

 

• 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장함
  • 즉 어떤 노드까지 가는 최단 경로를 찾고자 했을 때, 탐색 시작 노드와 가까운 노드 층을 우선해서 함.
  • 그러니 세 번째로 가까운 노드들을 탐색할 때 찾고자 하는 노드가 발견되면, 이 노드까지 얼마나 걸렸는지를 판단할 수 있다. 즉 보장한다.는 뜻임
• dfs와 비교해보면
  • 인접리스트, 방문 배열을 사용하지만
  • 차이점은 탐색을 위해 스택이 아닌 큐를 사용한다는 점

26번, DFS와 BFS 프로그램

• 방문할 수 있는 노드가 여러 개일 경우에는 노드 번호가 작은 것을 먼저 방문
  • 인접 노드를 오름차순으로 정렬하면 됨

for (int i = 1; i <= N; i++) {
Collections.sort(A[i]);
}

• 여기선 Arrays.sort가 아니라 Collections.sort를 썼네. 이유가 뭘까?
  • 이유 설명
    • 해당 코드에서 Collections.sort를 사용한 이유는 A[i]가 ArrayList<Integer> 형식이기 때문입니다.
    • ArrayList는 List 인터페이스를 구현한 클래스이므로 Collections.sort를 사용하는 것이 적절합니다.
  • 데이터 구조의 차이: Arrays.sort는 배열을, Collections.sort는 List를 정렬하는 메서드입니다.
  • 적절한 선택: 코드에서 A[i]는 ArrayList<Integer> 형식이므로, Collections.sort를 사용하여 정렬하는 것이 적절합니다.
  • 동적 크기: ArrayList는 동적으로 크기가 변할 수 있어, 그래프의 인접 리스트 표현에 적합합니다.
  1. Arrays.sort:
     • Arrays.sort는 배열을 정렬하는 메서드입니다.
     • 배열(Array)은 고정된 크기를 가지며, 초기화할 때 크기를 지정해야 합니다.
  2. Collections.sort:
     • Collections.sort는 List 인터페이스를 구현한 컬렉션을 정렬하는 메서드입니다.
     • List 인터페이스를 구현한 컬렉션은 가변적이며, 동적으로 크기가 변경될 수 있습니다. 대표적으로 ArrayList, LinkedList 등이 있습니다.
• 간단히 System.out.print(node + " ");로 했네. bufferedwriter 사용이 귀찮아서 그런가

###코드###
1. dfs 함수 1번
static void DFS(int v) {
    if (visited[v]) {
      return;
    }
    visited[v] = true;
    for (int i : A[v]) {
      if (visited[i] == false) { // 연결 정점 중 방문하지 않았던 정점만 탐색함
        DFS(i);
      }
    }

2. dfs 함수 2번
 public static void DFS(int node) {  // DFS구현
    System.out.print(node + " ");
    visited[node] = true;
    for (int i : A[node]) {
      if (!visited[i]) {
        DFS(i);
      }
    }
  }

###질문###
1. 2번 dfs 함수에선 왜 아래 부분이 없는가. 이 부분은 기본적인 dfs 함수 구현할 때 보통 들어가는 것 아닌가? 이게 생략 가능하다면 어떤 경우인가?
    if (visited[v]) {
      return;
    }

• 1번 DFS 함수의 구조
  • 방문 확인 후 반환: 함수 시작 시 방문 여부를 확인하고, 이미 방문된 노드라면 즉시 반환합니다.
  • 이중 방문 방지: 이 구조는 중복된 방문을 막는 것을 보장합니다.
• 2번 DFS 함수의 구조
  • 방문 확인 없이 출력: 노드 방문 시 바로 방문 처리를 합니다.
  • 반복문 내부에서 방문 확인: 노드의 인접 노드를 탐색할 때만 방문 여부를 확인합니다.
• 요약
  • 방문 확인 생략 가능 여부: 방문 여부를 반복문 내부에서만 확인하여 중복 방문을 방지할 수 있는 경우, 함수 시작 시 방문 확인 코드를 생략할 수 있습니다.
  • 구현 선택: 두 방법 중 어떤 것을 사용할지는 구현자의 선택이며, 코드의 간결성 또는 안전성을 고려하여 결정할 수 있습니다.
• 두 함수 비교
  • 1번 DFS 함수는 중복된 방문을 확실하게 방지합니다. 이는 모든 호출에서 방문 여부를 확인하기 때문에 안전하지만, 약간의 오버헤드가 있을 수 있습니다.
  • 2번 DFS 함수는 더 간결하며, 방문 확인을 반복문 내부로 제한하여 중복 방문을 방지합니다. 이는 초기 호출에서 방문 여부를 별도로 확인할 필요가 없는 경우 적합합니다.
• 방문 확인 코드 생략 가능성
  • 방문 확인 코드 (if (visited[v]) { return; })가 생략 가능한 경우는 다음과 같습니다:
  1. 초기 호출에서만 방문 여부를 확인할 필요가 없는 경우:
     • 함수가 항상 처음 호출될 때 방문되지 않은 노드만 호출된다고 보장된다면 생략할 수 있습니다.
  2. 방문 확인을 다른 위치에서 이미 처리한 경우:
     • DFS 함수의 반복문 내에서 방문 여부를 확인하는 경우, 함수 시작 시 중복된 확인을 피하기 위해 생략할 수 있습니다.

27번, 미로 탐색하기

 

• 최단 경로 문제인가? bfs로 완전 탐색 진행하며 몇 번째 깊이에서 원하는 값 찾을 수 있는지 구하는 것과 동일
• dx, dy(상하좌우를 탐색하기 위한 define값 정의 변수)
  • 문제에서 주로 배열에서 상하좌우로 갈 수 있다. 혹은 근처 8방향으로 갈 수 있다 이럴 때 많이 씀
  • 이 때 이 define을 통해 탐색을 쉽게 구현할 수 있음. 많이 씀
• A[i][j] = Integer.parseInt(line.substring(j, j + 1));
  • String 변수에 substring()이란 메소드가 있구나
• Queue<int[]> queue = new LinkedList<>();
  • 왜 int[]냐? 데이터가 두 개 들어오니까
• queue.offer(new int[] { i, j });
  • offer가 뭔지는 내가 전에 교재에 기록한 거 참고 ⇒ add와 offer, remove와 poll의 차이
  • new int[] { i, j }; 이렇게 배열을 생성할 수 있구나
• int now[] = queue.poll();
  • queue의 자료형이 int[]라서 가능한 거구나

for (int k = 0; k < 4; k++) {
int x = now[0] + dx[k];
int y = now[1] + dy[k];
}

• now[0]은 x좌표를, now[1]은 y좌표를 뜻하는 것 같음
• 이 부분 애매하면 영상 해설 보기
• if (x >= 0 && y >= 0 && x < N && y < M)
  • 이 부분 뜻은 좌표 탐색할 때, N X M 배열의 범위를 넘어가면 안 된다는 뜻

 

28번, 트리의 지름 구하기

• 임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다
  • ⇒ 챗 지피티는 아래처럼 말하지만, 난 이해 잘 안 됨. 그럴 수 있겠다 싶지만 완전히 설명은 안 된 느낌임. 그냥 넘어가. 지금 수준에서 이해 안 되는 건 넘어가는 거잖아. 너무 시간 썼네.
  • 이유:
    • 최장 경로의 속성: 트리의 지름은 트리 내에서 가장 긴 경로입니다. 이 경로는 항상 트리의 양 끝 노드들 사이의 경로입니다.
    • 임의의 노드에서 가장 먼 노드: 임의의 노드에서 가장 먼 노드는 트리의 지름에 해당하는 두 노드 중 하나입니다. 왜냐하면, 가장 먼 노드는 트리의 한쪽 끝에 있기 때문입니다.
    • 두 번째 BFS: 첫 번째 BFS에서 얻은 가장 먼 노드에서 다시 BFS를 실행하면, 트리의 지름에 해당하는 최장 경로를 얻을 수 있습니다. 이는 첫 번째 BFS에서 얻은 노드가 실제로 지름의 한쪽 끝에 있기 때문입니다.
  • 이 아이디어는 트리의 특성(모든 노드가 연결된 하나의 경로를 갖는 구조)과 BFS의 특성(최단 경로를 찾는 알고리즘)을 활용한 것입니다.

이진 탐색

• 간단한 구현에 비해 괜찮은 성능을 나타내어 코테에 종종 출제됨
• 원하는 특정 데이터 탐색할 때 사용하는 가장 일반적인 알고리즘 -> 구현 및 원리가 비교적 간단하여 많은 코테에서 부분 문제로 요구하는 영역
• logN번의 연산으로 찾을 수 있지만, 데이터가 정렬되어 있어야 함

 

• 이진 탐색 원리도 투 포인터와 연관되어 있는 듯하다. 
  • 가만 보니 느낀 건데 정렬을 할 때도 이진 탐색을 할 때도 투 포인터가 자주 쓰이는 걸 알 수 있다.

 

29번, 원하는 정수 찾기 

강의 영상 있지만 안 보고 교재만 봐도 충분히 쉽고

이번 문제 강의는 너무 교재 읽기식이라 시간 바쁜 상태에서 한 것 같아 굳이

 

30번, 블루레이 만들기

교재 읽으면 이해 됨

 

31번, 배열에서 k번째 수 찾기

이 문젠 개념과 아이디어가 이해 안 됨

코드 자체는 간단한데, 개념이 이해가 안 되서

이건 보류하고 넘어가기 

내가 수준 올라오고 그럴 때 다시 이해하려고 해보기 

지금 완전히 이해하려면 시간 너무 많이 걸릴 것 같음

 

• 이진 탐색 시장 인덱스를 1, 종룔 인덱스를 k로 정함
  • 교재 설명) 왜? 2차원 배열은 n행이 n의 배수로 구성되어 있으므로 2차원 배열에서의 k번째 수는 k를 넘지 않는다. 즉 2차원 배열의 1~k번째 안에 정답이 있다