본문 바로가기
과목
  • 1 Java 기초
    1.1

    클래스, main & output

    이 사이트는 Java 8 언어 규칙에 따라 자바를 컴파일합니다. 이러한 독립적인 예제는 entry method인 main를 클래스 내에 배치합니다. 헬퍼 클래스와 메서드 전용 답변은 자체 main가 필요하지 않습니다. System.out.println(...)은 줄을 출력하며, System.out.print(...)은 줄바꿈 없이 출력합니다.

    public class Main {
        public static void main(String[] args) {
            System.out.println("Hello, world!");
            System.out.println("I am learning Java.");
        }
    }
    
    • Java는 컴파일됩니다: 컴파일러가 전체 프로그램을 검사한 후 실행합니다.
    • 선언, 할당, 메서드 호출 및 return 문장은 세미콜론 ;으로 끝납니다. if, for 또는 while 블록은 braces를 사용하며, 닫는 braces가 나타나더라도 세미콜론을 추가하지 마십시오.
    이 독립 Java 8 예제는 클래스 내부에 main을 정의합니다
    이 독립적인 Java 8 예제는 main을 클래스 내에서 정의함
    1.2

    변수 & 원시 데이터 타입

    변수는type을 명시해야 합니다. 일반적인 원시 type: int (정수), double (부동소수점), boolean (true/false), char (한 UTF-16 코드 단위; 일부 문자는 두 개 필요).

    public class Main {
        public static void main(String[] args) {
            int age = 17;
            double price = 9.99;
            boolean passed = true;
            System.out.println(age + " " + price + " " + passed);
        }
    }
    
    1.3

    주석 & 스타일

    주석은 //(한 줄) 또는 /* ... */(블록)입니다. braces { } 안의 코드는suitably.give indentation(적절히 두께를 두십시오). 클래스명은 대문자로 시작하고, 변수와 메서드는 camelCase(첫 글자는 소문자)를 사용합니다.

    public class Main {
        public static void main(String[] args) {
            // greet the user
            String firstName = "Mei";
            System.out.println("Hi, " + firstName);
        }
    }
    

    Common mistakes

    • 선언, 할당, 메서드 호출 및 return 문장은 ;으로 끝납니다;제어 흐름 블록은 추가 세미콜론이 필요 없습니다.
    • 표준 Java 8 진입점 public static void main(String[] args)을 사용하십시오; 매개변수 이름은 다를 수 있으며, String... args도 유효합니다.
    • println는 새로운 줄을 추가합니다; print은 추가하지 않습니다.
  • 2 연산자 및 식
    2.1

    산술 연산 및 할당

    Java 산술 연산에서는 + - * /와 %(나머지)를 사용합니다. 두 int의 경우, /은 정수 나눗셈으로 소수점을 버립니다. +=, -=, ++는 단축문입니다.

    public class Main {
        public static void main(String[] args) {
            int a = 7, b = 2;
            System.out.println(a / b);    // 3 (integer division)
            System.out.println(a % b);    // 1
            double x = 7.0 / 2;           // 3.5 (one side is double)
            System.out.println(x);
        }
    }
    
    int/int는 반올림됩니다; 정확한 결과를 위해 double을 포함해야 합니다
    int/int는 반올림됩니다; 정확한 결과를 위해 double을 포함해야 합니다
    2.2

    객체 사용: String, Math, 래퍼

    일부 값은 메소드를 가진 객체입니다. String에는 .length(), .substring(), .toUpperCase()이 있습니다. Math에는 Math.max, Math.sqrt, Math.pow이 있습니다. 래퍼 클래스(Integer, Double)는 기본 타입을 감싸며, 예로 Integer.parseInt("42")가 있습니다.

    public class Main {
        public static void main(String[] args) {
            String s = "Hello";
            System.out.println(s.length());                  // 5
            System.out.println(s.toUpperCase());             // HELLO
            System.out.println(Math.max(3, 9));              // 9
            System.out.println(Integer.parseInt("42") + 1);  // 43
        }
    }
    

    Math.random()은 double에서 시작하여(포함) 0.0까지(불포함)의 무작위 1.0를 반환합니다. 이를 스케일링하고 형변환하여 정수를 얻으세요 — 이것이 AP의 관례입니다:

    public class Main {
        public static void main(String[] args) {
            // a random whole number from 1 to 6 (a dice roll)
            int roll = (int) (Math.random() * 6) + 1;
            System.out.println(roll >= 1 && roll <= 6);   // true
        }
    }
    
    • Integer.MAX_VALUE (2147483647)과 Integer.MIN_VALUE은 int의 한계이며, 이를 넘으면 wrapping됩니다(오버플로우).
    • 어떤 객체도 가리키지 않는 객체 변수는 null을 포함하며, 이에 대해 메서드를 호출하면 NullPointerException이 발생합니다.
    2.3

    형변환 및 타입 변환

    형변환(cast)은 값의 타입을 변경합니다. (int)는 소수점을 버리며, 정확한 결과가 필요할 때 정수 나눗셈을 피하기 위해 (double)을 사용합니다.

    public class Main {
        public static void main(String[] args) {
            double pi = 3.99;
            System.out.println((int) pi);            // 3
            int total = 7, n = 2;
            System.out.println((double) total / n);  // 3.5
        }
    }
    

    Common mistakes

    • 정수 나눗셈: 5 / 2은 2이며, 2.5이 아닙니다. 먼저 형변환: (double) 5 / 2.
    • Strings(그리고 다른 객체)를 비교할 때는 .equals()를 사용하고, ==을 사용하지 마십시오.
    • 두 객체에 대한 ==는 동일한 객체인지를 테스트하며, 외관이 같은지는 테스트하지 않습니다.
  • 3 부울리안 및 선택
    3.1

    if / else

    if는 조건이 참일 때 블록을 실행하며, else if과 else은 더 많은 경우를 추가합니다. 조건은 ( )에, 블록은 { }에 넣습니다.

    public class Main {
        public static void main(String[] args) {
            int score = 72;
            if (score >= 80) {
                System.out.println("A");
            } else if (score >= 60) {
                System.out.println("B");
            } else {
                System.out.println("fail");
            }
        }
    }
    
    if는 참인 분기를 선택; else는 거짓 분기를 선택
    if는 참인 분기를 선택; else는 거짓 분기를 선택합니다
    3.2

    논리 연산자 및 비교

    ==, !=, <, >, <=, >=로 비교하여 boolean를 얻습니다. 논리 연산자인 &&(and), ||(or), !(not)로 결합하십시오. String의 경우, .equals(...)을 사용하고 반드시 ==을 사용하지 마십시오.

    public class Main {
        public static void main(String[] args) {
            int age = 16;
            boolean member = true;
            System.out.println(age >= 18 && member);   // false
            String a = "hi";
            System.out.println(a.equals("hi"));        // true
        }
    }
    
    3.3

    스위치

    switch는 여러 고정된 값 중 하나를 선택합니다. 각 case은 break으로 끝납니다; default은 기본값(fallback)입니다.

    public class Main {
        public static void main(String[] args) {
            int day = 3;
            switch (day) {
                case 1: System.out.println("Mon"); break;
                case 3: System.out.println("Wed"); break;
                default: System.out.println("other");
            }
        }
    }
    

    Common mistakes

    • 조건은 반드시 boolean여야 하며, if (x = 5)은 컴파일되지 않습니다(==을 사용하십시오).
    • 각 switch case에는 break;이 있어야 하며, 그렇지 않으면 제어가 다음 case로Fall through됩니다.
    • &&과 ||은 논리 연산자입니다. &과 |은 비트 연산자입니다.
  • 4 루프
    4.1

    while 루프

    while 루프는 조건이 참인 동안 반복됩니다. 내부에서 값을 변경하지 않으면 무한 루프가 됩니다.

    public class Main {
        public static void main(String[] args) {
            int n = 1;
            while (n <= 3) {
                System.out.println(n);
                n++;
            }
        }
    }
    
    while문은 바디(body)의 각 반복 실행 전 조건을 먼저 확인합니다
    while문은 바디(body)의 각 반복 실행 전 조건을 먼저 확인합니다
    4.2

    for 루프

    for 루프는 시작값, 조건, 단계값을 한 줄에 묶습니다. 반복 횟수가 명확할 때 가장 적합합니다.

    public class Main {
        public static void main(String[] args) {
            for (int i = 0; i < 5; i++) {
                System.out.print(i + " ");
            }
            System.out.println();   // 0 1 2 3 4
        }
    }
    
    4.3

    누적 (Accumulation)

    누적 패턴: 루프 전에 변수를 초기화한 뒤, 매 반복마다 값을 업데이트합니다.

    public class Main {
        public static void main(String[] args) {
            int total = 0;
            for (int i = 1; i <= 5; i++) {
                total += i;
            }
            System.out.println(total);   // 15
        }
    }
    
    4.4

    중첩 루프

    루프 안에 다른 루프가 있는 것을 중첩 루프라고 합니다. 외부 루프의 각 반복 시 내부 루프가 완전히 실행됩니다.

    public class Main {
        public static void main(String[] args) {
            for (int r = 0; r < 3; r++) {
                for (int c = 0; c < 3; c++) {
                    System.out.print("*");
                }
                System.out.println();
            }
        }
    }
    

    Common mistakes

    • for (int i = 0; i < n; i++)는 n번 실행됩니다(0부터 n - 1까지); <=를 사용하면 한 번 더 추가 실행됩니다.
    • for (...) 또는 while (...) 바로 뒤에 세미콜론을 두면 안 됩니다—빈 루프가 생성되기 때문입니다.
    • 카운터는 for 헤더에서 선언하여 scopes가 루프 종료와 함께 끝나도록 하십시오.
  • 5 문자열
    5.1

    String 메서드

    String는 텍스트입니다. 유용한 메서드: .length(), .charAt(i), .substring(a, b), .indexOf(x), .toUpperCase(), .equals(...). String은 불변이며, 각 메서드는 새로운 String을 반환합니다.

    public class Main {
        public static void main(String[] args) {
            String s = "Python";
            System.out.println(s.length());          // 6
            System.out.println(s.charAt(0));         // P
            System.out.println(s.substring(0, 3));   // Pyt
            System.out.println(s.toUpperCase());     // PYTHON
        }
    }
    

    매일 사용할 메서드들:

    메서드 의미 예시 → 결과
    .length() 문자 수 "Hi".length() → 2
    .charAt(i) 특정 인덱스의 한 문자 "Hi".charAt(0) → H
    .substring(a, b) 일부 추출, b 전까지 (포함 안 함) "Python".substring(0, 3) → Pyt
    .substring(a) a부터 끝까지 "Python".substring(3) → hon
    .indexOf(x) 첫 번째 위치, 없으면 -1 "banana".indexOf("na") → 2
    .equals(s) 같은 텍스트? "hi".equals("hi") → true
    .compareTo(s) 순서: 음수 / 0 / 양수 "apple".compareTo("banana") → 음수

    compareTo은 문자열을 사전 순서로 정렬합니다 — AP 시험에서는 문제 정렬에 이 방법을 사용합니다:

    public class Main {
        public static void main(String[] args) {
            String a = "apple", b = "banana";
            System.out.println(a.compareTo(b) < 0);    // true (apple comes first)
            System.out.println(a.compareTo("apple"));  // 0 (equal)
        }
    }
    
    핵심 String 메소드: length, charAt, substring, equals
    핵심 String 메소드: length, charAt, substring, equals
    5.2

    문자열 생성 및 순회

    +(연결)으로 문자열을 합치세요. 루프와 .charAt(i)를 사용하여 각 문자를 방문하세요.

    public class Main {
        public static void main(String[] args) {
            String word = "banana";
            int count = 0;
            for (int i = 0; i < word.length(); i++) {
                if (word.charAt(i) == 'a') count++;
            }
            System.out.println(count);   // 3
        }
    }
    

    루프에서 긴 문자열을 만들 때, StringBuilder이 훨씬 빠릅니다: 조각들을 append한 후, .toString()를 한 번만 호출하세요.

    public class Main {
        public static void main(String[] args) {
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= 5; i++) {
                sb.append(i).append(" ");
            }
            System.out.println(sb.toString().trim());   // 1 2 3 4 5
        }
    }
    

    Common mistakes

    • 문자열은 불변(immutable)입니다: s.toUpperCase()은 새로운 문자열을 반환하므로 결과를 저장해야 합니다.
    • s.charAt(i)으로 문자를 읽으세요; 길이는 s.length()입니다(()가 있는 메소드).
    • 큰 루프에서 +=으로 문자열을 만드는 것은 느립니다; StringBuilder을 사용하세요.
  • 6 배열(Data arrays)
    6.1

    1-D 배열

    배열은 하나의 타입의 고정된 수의 값을 보관합니다. 인덱스는 0부터 시작하며, 크기는 .length으로 얻습니다.

    public class Main {
        public static void main(String[] args) {
            int[] scores = {88, 71, 95};
            System.out.println(scores[0]);       // 88
            System.out.println(scores.length);   // 3
            scores[1] = 100;
            System.out.println(scores[1]);       // 100
        }
    }
    
    기본 데이터 타입(value)을 유지하고, 배열 변수는 배열 객체에 대한 참조를 가짐
    기본 데이터 타입(value)을 유지하고, 배열 변수는 배열 객체에 대한 참조를 가짐
    6.2

    배열 알고리즘

    루프를 사용하여 배열을 순회하여 최대값, 총합, 개수를 찾거나 검색할 수 있습니다. for-each 루프(for (int x : a))는 각 값을 순서대로 읽습니다.

    public class Main {
        public static void main(String[] args) {
            int[] a = {3, 9, 2, 7};
            int max = a[0], total = 0;
            for (int x : a) {
                if (x > max) max = x;
                total += x;
            }
            System.out.println(max + " " + total);   // 9 21
        }
    }
    
    6.3

    2-D 배열

    2차원 배열은 행과 열의 격자입니다: grid[row][col].

    public class Main {
        public static void main(String[] args) {
            int[][] grid = {{1, 2, 3}, {4, 5, 6}};
            System.out.println(grid[1][2]);   // 6
            for (int[] row : grid) {
                for (int v : row) System.out.print(v + " ");
            }
            System.out.println();             // 1 2 3 4 5 6
        }
    }
    

    Common mistakes

    • 배열의 크기는 a.length이며(대괄호나 () 없음), 생성 시 고정됩니다.
    • 유효한 인덱스는 0부터 a.length - 1까지이며, a[a.length]는 ArrayIndexOutOfBoundsException을 발생시킵니다.
    • 새로운 int[5]은 빈 공간이 아닌 영제로 채워집니다.
  • 7 ArrayList
    7.1

    ArrayList 기본

    ArrayList은 확장 가능한 목록으로, 항목을 추가하거나 제거할 때 커지고 작아집니다. 객체를 저장하므로 Integer 같은(wrapper type)을 사용해야 합니다(int가 아님). <Integer>는 제네릭 타입입니다. 주요 메서드: .add(x), .get(i), .set(i, x), .size(), .remove(i).

    import java.util.ArrayList;
    
    public class Main {
        public static void main(String[] args) {
            ArrayList<Integer> nums = new ArrayList<Integer>();
            nums.add(10);
            nums.add(20);
            nums.add(30);
            System.out.println(nums.size());   // 3
            System.out.println(nums.get(1));   // 20
            nums.set(0, 99);
            System.out.println(nums);          // [99, 20, 30]
        }
    }
    
    ArrayList: 확장 가능한 목록에서의 add, get, size
    ArrayList: 확장 가능한 목록에서의 add, get, size
    7.2

    ArrayList 알고리즘 및 remove 버그

    .remove(i)는 이후 모든 요소를 한 자리 왼쪽으로 밀어냅니다. i로 세어 가며 제거하면 다음 요소를 건너뜁니다. 수정 방법: 역순으로 루프를 돌리거나, 제거 후 i를 증가시키지 마십시오.

    import java.util.ArrayList;
    
    public class Main {
        public static void main(String[] args) {
            ArrayList<Integer> nums = new ArrayList<Integer>();
            for (int n : new int[]{4, 7, 4, 9, 4}) nums.add(n);
            // Remove every 4 — loop backwards so removals don't skip items.
            for (int i = nums.size() - 1; i >= 0; i--) {
                if (nums.get(i) == 4) nums.remove(i);
            }
            System.out.println(nums);   // [7, 9]
        }
    }
    

    Common mistakes

    • ArrayList는 .size(), .get(i), .add(...)을 사용하며, 배열에서 사용하는 []가 아닙니다.
    • 인덱스로 전진하는 루프 중 항목을 제거하면 다음 항목을 건너뜁니다(remove 버그). 역순으로 루프를 도는지, 이터레이터를 사용하십시오.
    • 원시형(primitives) 대신 객체를 저장합니다: ArrayList<Integer>을 사용하고, Java가 int 값을 자동 박싱(auto-boxing)합니다.
  • 8 클래스 작성
    8.1

    필드, 컨스트럭터 및 메서드

    클래스는 객체의 청사진입니다. 필드는 데이터를 저장하고, 컨스트럭터는 새 객체를 설정하며, 메서드는 동작입니다. this.name는 "이 객체의 name"를 의미합니다. new를 사용하여 객체를 생성합니다.

    public class Main {
        public static void main(String[] args) {
            Dog d = new Dog("Rex", 3);
            System.out.println(d.describe());   // Rex is 3 years old
            d.haveBirthday();
            System.out.println(d.describe());   // Rex is 4 years old
        }
    }
    
    class Dog {
        private String name;
        private int age;
    
        public Dog(String name, int age) {   // constructor
            this.name = name;
            this.age = age;
        }
    
        public String describe() {
            return name + " is " + age + " years old";
        }
    
        public void haveBirthday() {
            age++;
        }
    }
    

    static 멤버는 특정 객체가 아닌 클래스 자체에 속합니다. 클래스명 위에 정적 메서드를 호출합니다—Math.max와 같이—and 정적 필드는 모든 객체와 공유됩니다:

    public class Main {
        public static void main(String[] args) {
            System.out.println(Counter.made());   // 0
            new Counter();
            new Counter();
            System.out.println(Counter.made());   // 2
        }
    }
    
    class Counter {
        private static int count = 0;      // shared by ALL Counter objects
    
        public Counter() { count++; }
    
        public static int made() {         // called on the class: Counter.made()
            return count;
        }
    }
    
    필드는 상태(state)를 저장; 컨스트럭터는 구축; 메서드는 작동
    필드는 상태를 저장; 컨스트럭터는 구축; 메서드는 작동
    8.2

    캡슐화

    encapsulation은 객체 상태에 대한 접근을 제어합니다. 필드에 private 표시하여 비관련 클래스로부터 직접 접근을 차단합니다; 액세서리(게터)는 상태를 읽고 뮤테이터는 변경합니다. 세터는 뮤테이터의 한 종류입니다. private은 값을 검증하지 않습니다: 컨스트럭터와 뮤테이팅 메서드는 자체 확인이나 명시된 전제 조건이 필요합니다. 이 예제는 음수가 아닌 start과 int 내에 맞도록 더하는 것을 가정하며, its deposit 메서드는 양수가 아닌 금액을 거절합니다.

    public class Main {
        public static void main(String[] args) {
            Account a = new Account(100);
            a.deposit(50);
            a.deposit(-999);                       // rejected by the guard
            System.out.println(a.getBalance());    // 150
        }
    }
    
    class Account {
        private int balance;                       // hidden from outside
    
        public Account(int start) {
            balance = start;
        }
    
        public void deposit(int amount) {
            if (amount > 0) balance += amount;     // this guard checks the deposit amount
        }
    
        public int getBalance() {                  // accessor (getter)
            return balance;
        }
    }
    

    Common mistakes

    • 컨스트럭터는 클래스명과 반환 유형이 없습니다(void도 포함).
    • 동일한 이름의 매개변수와 구별하려면 this.field를 사용합니다.
    • 필드를 private로 만들고 getter/setter 메서드를 통해 접근하십시오(엔캡슐).
  • 9 상속 및 다형성
    9.1

    상속(Inheritance)

    상속은 서브클래스가 초기(superclass)의 기능을 재사용할 수 있게 합니다. class Cat extends Animal를 작성하면 Cat이 Animal의 필드와 메서드를 무료로 얻습니다. super(...)를 사용하여 부모 컨스트럭터를 호출합니다.

    public class Main {
        public static void main(String[] args) {
            Cat c = new Cat("Milo");
            c.eat();      // Milo is eating  (inherited from Animal)
            c.speak();    // Meow            (Cat's own method)
        }
    }
    
    class Animal {
        protected String name;
        public Animal(String name) { this.name = name; }
        public void eat() { System.out.println(name + " is eating"); }
    }
    
    class Cat extends Animal {
        public Cat(String name) { super(name); }     // call Animal's constructor
        public void speak() { System.out.println("Meow"); }
    }
    
    Cat과 Dog가 Animal을 확장: 구성원을 상속하고 자체적인 것들을 추가
    Cat과 Dog가 Animal을 확장: 구성원을 상속하고 자체적인 것들을 추가
    9.2

    다형성(Polymorphism) 및 toString

    서브클래스는 메서드를 오버라이딩하여 부모의 버전을 대체할 수 있습니다. 다형성은 Shape 변수가 어떤 하위 타입(h subtype)을든 가질 수 있음을 의미하며, Java가 실행 시간(run time)에 올바른 toString을 선택합니다. System.out.println(obj)는 자동으로 obj.toString()를 호출합니다.

    public class Main {
        public static void main(String[] args) {
            Shape[] shapes = { new Circle(2), new Square(3) };
            for (Shape s : shapes) {
                System.out.println(s);          // each calls its own toString
            }
        }
    }
    
    class Shape {
        public String toString() { return "a shape"; }
    }
    
    class Circle extends Shape {
        private int r;
        public Circle(int r) { this.r = r; }
        public String toString() { return "Circle r=" + r; }     // override
    }
    
    class Square extends Shape {
        private int side;
        public Square(int side) { this.side = side; }
        public String toString() { return "Square side=" + side; }   // override
    }
    

    Common mistakes

    • 오버라이딩 메서드는 서명(signature)과 정확히 일치해야 하며, @Override를 추가하여 컴파일러가 실수를 감지하도록 합니다.
    • super(...)은 서브클래스 컨스트럭터의 첫 번째 줄이어야 합니다.
    • 서브클래스 객체는 IS-A 초기 객체이지만, 그 반대는 아닙니다.
  • 10 재귀
    10.1

    재귀

    재귀(recursion)는 메서드가 자신을 호출하는 것입니다. 모든 재귀에는 기준 사례(base case, 멈출 때)와 이를 향해 나아가는 재귀 호출이 필요합니다. 기준 사례가 없으면 영원히 멈추지 않고 스택 오버플로우로 충돌합니다.

    factorial(3)의 콜 스택: 각 호출이 대기했다가 역순으로 반환
    factorial(3)의 콜 스택: 각 호출이 대기했다가 역순으로 반환
    public class Main {
        public static void main(String[] args) {
            System.out.println(factorial(5));   // 120
        }
    
        public static int factorial(int n) {
            if (n <= 1) return 1;            // base case
            return n * factorial(n - 1);     // recursive call: n * (n-1)!
        }
    }
    

    Trace it: factorial(5) waits for factorial(4), which waits for factorial(3)… down to factorial(1) returning 1. Then the answers multiply back up: 1 → 2 → 6 → 24 → 120.

    재귀는 문자열(strings)에서도 작동—매번 한 문자를 떼어내세요:

    public class Main {
        public static void main(String[] args) {
            System.out.println(reverse("PYTHON"));   // NOHTYP
        }
    
        static String reverse(String s) {
            if (s.length() <= 1) return s;               // base case
            return reverse(s.substring(1)) + s.charAt(0);
        }
    }
    

    **병합 정렬(merge sort)**은 AP 시험의 재귀 정렬 주제입니다: 배열을 반으로 나누고, 각각을 재귀적으로 정렬한 후 두 정렬된 반을 병합(merge)합니다. O(n log n)에 실행되어 대용량 배열의 O(n²) 정렬보다 훨씬 빠릅니다.

    import java.util.Arrays;
    
    public class Main {
        public static void main(String[] args) {
            int[] a = {5, 2, 9, 1, 7, 3};
            mergeSort(a, 0, a.length - 1);
            System.out.println(Arrays.toString(a));   // [1, 2, 3, 5, 7, 9]
        }
    
        static void mergeSort(int[] a, int lo, int hi) {
            if (lo >= hi) return;                 // base case: one element
            int mid = (lo + hi) / 2;
            mergeSort(a, lo, mid);                // sort the left half
            mergeSort(a, mid + 1, hi);            // sort the right half
            merge(a, lo, mid, hi);                // merge the two halves
        }
    
        static void merge(int[] a, int lo, int mid, int hi) {
            int[] tmp = new int[hi - lo + 1];
            int i = lo, j = mid + 1, k = 0;
            while (i <= mid && j <= hi) {
                if (a[i] <= a[j]) tmp[k++] = a[i++];
                else              tmp[k++] = a[j++];
            }
            while (i <= mid) tmp[k++] = a[i++];
            while (j <= hi)  tmp[k++] = a[j++];
            for (k = 0; k < tmp.length; k++) a[lo + k] = tmp[k];
        }
    }
    

    Common mistakes

    • 재귀에는 기본 경우가 필요합니다. 그렇지 않으면 StackOverflowError가 발생합니다.
    • 각 재귀 호출은 반드시 기준 사례에 더 가까이 이동해야 합니다.
    • 재귀가 올바른 값을 반환하는지 확인하려면 작은 예제를 손으로 추적(trace)하십시오.
    • 병합 정렬에서 병합 단계가 실제 작업을 수행하고, 재귀는 배열만 나눕니다.
  • 11 검색 및 정렬
    11.1

    선형 탐색 및 이진 탐색

    선형 검색(linear search)은 모든 요소를 확인합니다—모든 배열에서 작동합니다. 이진 검색(binary search)은 훨씬 빠르지만 정렬된 배열이 필요합니다: 중간을 보고 매 단계마다 절반을 폐기합니다. 둘 다 인덱스를 반환하거나, 찾지 못하면 -1를 반환합니다.

    public class Main {
        public static void main(String[] args) {
            int[] a = {2, 5, 8, 12, 16, 23};      // sorted, so binary search works
            System.out.println(linear(a, 12));    // 3
            System.out.println(binary(a, 12));    // 3
            System.out.println(binary(a, 9));     // -1 (not found)
        }
    
        static int linear(int[] a, int target) {
            for (int i = 0; i < a.length; i++)
                if (a[i] == target) return i;
            return -1;
        }
    
        static int binary(int[] a, int target) {
            int lo = 0, hi = a.length - 1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (a[mid] == target) return mid;
                else if (a[mid] < target) lo = mid + 1;
                else hi = mid - 1;
            }
            return -1;
        }
    }
    
    이진 검색은 매 단계마다 범위를 반으로 나누므로, 정렬된 배열은 O(log n)에 검색됨
    이진 검색은 매 단계마다 범위를 반으로 나누므로, 정렬된 배열은 O(log n)에 검색됨
    11.2

    선택 및 삽입 정렬

    선택 정렬(selection sort)은 남은 값 중 가장 작은 값을 반복해서 찾아 맨 앞으로 스왑합니다. 삽입 정렬(insertion sort)은 각 값을 가져와 이미 정렬된 값들 사이에서 제자리로 밀어 넣습니다.

    import java.util.Arrays;
    
    public class Main {
        public static void main(String[] args) {
            int[] a = {5, 2, 9, 1, 7};
            for (int i = 0; i < a.length - 1; i++) {
                int min = i;
                for (int j = i + 1; j < a.length; j++)
                    if (a[j] < a[min]) min = j;
                int t = a[min]; a[min] = a[i]; a[i] = t;   // swap into place
            }
            System.out.println(Arrays.toString(a));   // [1, 2, 5, 7, 9]
        }
    }
    
    import java.util.Arrays;
    
    public class Main {
        public static void main(String[] args) {
            int[] a = {5, 2, 9, 1, 7};
            for (int i = 1; i < a.length; i++) {
                int key = a[i], j = i - 1;
                while (j >= 0 && a[j] > key) {    // shift bigger values right
                    a[j + 1] = a[j];
                    j--;
                }
                a[j + 1] = key;                  // drop key into the gap
            }
            System.out.println(Arrays.toString(a));   // [1, 2, 5, 7, 9]
        }
    }
    

    속도 비교 방법:

    알고리즘 시간
    선형 검색 O(n)
    이진 검색 O(log n), 정렬된 배열 전용
    선택 / 삽입 정렬 O(n²)
    병합 정렬 (주제 10) O(log n)

    Common mistakes

    • 이진 검색은 정렬된 배열에서만 작동합니다.
    • 선형 검색은 O(n); 이진 검색은 O(log n)이나 먼저 정렬이 필요합니다.
    • 선택 및 삽입 정렬은 O(n²)—배우기 쉬우나 대용량 데이터에서는 느립니다.
  • 12 파일 및 FRQ
    12.1

    Scanner로 텍스트 파일 처리

    Scanner는 텍스트를 한 줄씩 읽습니다. 실제 파일에서는 new Scanner(new File("scores.txt"))을 작성하지만, 여기서는 예제가 어디서나 작동하도록 String으로 감쌈니다. 한 줄을 부분으로 나누려면 .split(" ")을 사용하고 텍스트에서 숫자를 해석하려면 Integer.parseInt(...)을 사용하십시오.

    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            // Real file:  Scanner in = new Scanner(new File("scores.txt"));
            String data = "Alice 80\nBob 95\nCara 72";
            Scanner in = new Scanner(data);
            int total = 0, count = 0;
            while (in.hasNextLine()) {
                String line = in.nextLine();
                String[] parts = line.split(" ");      // break the line on the space
                total += Integer.parseInt(parts[1]);
                count++;
            }
            System.out.println("average = " + (total / count));   // average = 82
        }
    }
    
    Scanner는 hasNextLine이 true인 동안 줄을 읽음
    Scanner는 hasNextLine이 true인 동안 줄을 읽음
    12.2

    AP FRQ 질문 유형

    AP CS A 시험은 4개의 서술형 문제가 있으며, 각 문제는 고정된 형태를 가집니다:

    • Q1 — 메소드 및 제어: 주어진 규격에 따라 메소드를 작성; 루프, if, String/Math.
    • Q2 — 클래스 설계: 설명에서 전체 클래스(필드, 생성자, 메소드)를 작성합니다.
    • Q3 — 배열 / ArrayList: 1-D 배열이나 ArrayList을 처리(검색, 카운팅, 새 목록 생성).
    • Q4 — 2-D 배열: 행과 열을 통해 격자를 순회합니다.

    이 기술은 항상 동일합니다: 규격을 읽고, 설명대로 정확히 메소드를 작성하고, 올바른 타입을 반환합니다.

    public class Main {
        public static void main(String[] args) {
            // Q1 style: implement a method to a spec, then it is tested.
            System.out.println(countEven(new int[]{4, 7, 10, 3, 6}));   // 3
        }
    
        /** Returns how many values in arr are even. */
        public static int countEven(int[] arr) {
            int count = 0;
            for (int x : arr)
                if (x % 2 == 0) count++;
            return count;
        }
    }
    

    Common mistakes

    • nextInt()는 줄바꿈 문자를 그대로 두므로, 이어서 읽히는 nextLine()는 빈 줄이 됩니다. 먼저 이를 읽어야 합니다.
    • 파일 끝을 넘지 않도록 hasNext()를 확인한 후 읽으십시오.
    • FRQ에서 메소드 헤더를 주의 깊게 읽으세요: 반환 타입과 매개변수를 정확히 맞추십시오.

로그인 또는 계정 만들기

IGCSE, A-Level & AP