자바 코딩 테스트 정리 (1)

* 인프런 강의를 보면서 정리 (내용 계속 추가 될 예정)

 

 

<시간 복잡도> 

 
일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다 
 
시간 복잡도 유형

• 빅 오메가 : 최선일 때 연산 횟수를 나타낸 표기법 
• 빅 세타: 보통일 때 연산 횟수를 나타낸 표기법 
• 빅 오 : 최악일 대 연산 횟수를 나타낸 표기법  -> 코딩 테스트에서 선택하는 표기법 

연산 횟수 계산 방법

• 연산 횟수 = 알고리즘 시간 복잡도 * 데이터의 크기 

 
시간 복잡도 도출 기준

• 상수는 시간 복잡도 계산에서 제외한다
• 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다 

 
시간 초과과 되었을 땐 내 로직이 효율적인 지 다시 점검해야한다
 
 
(1) 알맞은 알고리즘 선택 기준
(2) 비효율적인 로직 찾아서 효율적으로 바꾸기  
 
 

 

<디버깅> 

 

프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정을 디버깅이라고 한다 
문법 오류는 컴파일러가 자동으로 찾아주지만 논리오류는 사용자의 의도와 다르게 동작하며 다양한 형태로 발생한다.
 
 
디버깅 하는 법 
코드에서 디버깅하고자 하는 줄에 중단점을 설정하고 IDE의 디버깅 기능을 실행해 진행한다 
 
(1)  코드에서 디버깅하고자 하는 줄에 중단점을 설정한다. 이때 중단점은 여러 개 설정할 수 있다
(2)  IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나 다음 중단점까지 실행할 수 있으며, 이 과정에서 추적할 변숫값도 지정할 수 있다. 이 방법으로 변숫값이 자신이 의도한 대로 바뀌는지 파악한다.
(3)  변숫값 이외에도 원하는 수식을 입력해 논리 오류를 파악할 수도 있다. 
 
 
step in to -> 코드 안으로 들어가면서 한줄씩 진행
step over -> 한줄씩 진행 

 

 

 

<입출력>

 

 import java.io.*;
  import java.util.*;
  
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String input = br.readline(); // 문자열 입력 받기 
  String[] input = br.readline().split(" "); // 공백으로 구분된 문자 입력받기 
  //문자열로 받고 split메소드를 이용해서 공백을 기준으로 잘라서 활용.
  
  StringTokenizer st = new StringTokenizer(br.readLine());
  String A = st.nextToken();

• Scanner이나 System.in.read를 사용하는 것이 일반적이나, 코딩테스트용으로 빠르게 입력받기 위해서는 BufferedReader을 사용한다.
• StringTokenizer은 공백이 있는 경우 문자열이 공백처리를 땡겨 채우도록 하여 BufferedReader보다 더 빠르다고 한다.
• BufferedReader, InputStreamReader은 java.io에 속하고 StringTokenizer은 java.util에 속한다.

 
 
 
정수 입력 받을 때

BufferedReader br= new BufferReadered(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine()); // 문자열을 정수로 전환 

 

• readLine은 BufferedReader 클래스에서 제공하는 메서드로, 입력 스트림으로부터 한 줄의 텍스트를 읽어오는 기능을 한다.
• BufferedReader 의 경우 문자열을 받는 대표적인 방법은 readLine() 과 read() 이다.
• 둘의 차이는 readLine() 은 한 행을 읽어오고, read() 는 한 문자만 읽어온다.
• 그래서 특별한 경우가 없는 한 대부분 readLine() 을 쓴다.

 
 
 
 
StringTokenizer 사용법

• 자바에서는 String을 token단위로 끊어주는 StringTokenizer 클래스를 제공한다.
• 예를 들어 “this is my string” 이라는 스트링을 this, is, my, string 4개의 스트링으로 끊어주는 기능을 제공한다.
• 그리고 공백말고도 다른 구획문자(delimiter)를 사용할수도 있다. 예를 들어 this%is%my%string을 delimiter에 %를 넣어 StringTokenizer를 사용하면 마찬가지로 this, is, my, string으로 읽어준다.
• thismy%string^일 때 구획 문자를 “$%^”라고 설정해주면 this, is, my, string 으로 끊어준다.

 
객체 생성 할 때 StringTokenizer( "문자열" , 구분자 ); 을 해주면 된다.
구분된 변수를 꺼낼 때는 차례대로 nextToken(); 을 해주면 문자열을 반환해준다.
이때 반환시킨 문자열은 반환됨과 동시에 해당 객체에서 사라지게 된다.
st.nextToken() 은 문자열을 반환하니 Double.parseDouble()로 double 형으로 변환
 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in);
StringTokenizer st = new StringTokenizer(br.readLine());

// AB CDD EFFF GH 입력

st.nextToken() // AB
st.nextToken() // CDD
st.nextToken() // EFFF
st.nextToken() // GH

    String str = "this%%is%%my%%string"; 
    StringTokenizer st = new StringTokenizer(str,"%%"); 

    while(st.hasMoreTokens()) { 
        System.out.println(st.nextToken()); 
    }

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main {
    public static void main(String[] args) {
        // try-with-resources를 사용하여 BufferedWriter 생성
        try (BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            bw.write("첫 번째 줄");
            bw.newLine();  // 줄 바꿈
            bw.write("두 번째 줄");
            bw.newLine();  // 줄 바꿈
            bw.flush();    // 버퍼를 강제로 플러시 (필요한 경우)
        } catch (IOException e) {
            System.out.println("출력 오류 발생: " + e.getMessage());
        }
        // try-with-resources 블록을 벗어나면 자동으로 close()가 호출됩니다.
    }
}

 
BufferedWriter 는 출력 메서드를 갖고있는 클래스로
write함수를 사용해서 버퍼에 입력 하고 newLine으로 줄바꿈을 하며 flush로 버퍼에 있는 내용을 출력한다.

• flush(): 데이터를 즉시 출력해야 할 때 사용. 모든 상황에서 필요한 것은 아니지만, 필요한 경우 명시적으로 호출.
• close(): 스트림 사용이 끝났을 때 항상 호출해야 하며, 자원을 해제하기 위해 필수적. try-with-resources 문을 사용하면 자동으로 호출됨.

 
 

---

 

<자료구조> 

 

1. 배열과 리스트 

 
배열과 리스트는 비슷한 점도 많지만 다른 점도 많다. 두 자료구조의 특징을 정확하게 이해하고 문제를 요구하는 조건에 따라 적절하게 선택해 사용하는 것이 중요하다 
 
 
🔹배열

• 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조
• 인덱스를 통해 참조할 수 있다 

 
🔹 배열의 특징
 
(1) 인덱스를 사용하여 값에 바로 접근할 수있다.
(2) 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다. 
(3) 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
(4) 구조가 간단하므로 코딩 테스트에서 많이 사용한다. 
 
 
데이터의 접근하는 경우가 많을 때나 크기가 고정되어있을 때 배열 사용 
 
🔹 리스트 
리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조
 
 
🔹 리스트의 특징 
 
(1) 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. 다시 말에 값에 접근하는 속도가 느리다. 
(2) 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다. 
(3) 선언할 때 크기의 별도로 지정하지 않아도 된다. 다시 말해 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 수윈 데이터를 다룰 때 적절하다. 
(4) 포인터를 지정할 공간이 필요하므로 배열보다 구조가 복잡하다. 
 
 
 
자바에선 ArrayList, LinkedList를 기본적으로 제공해준다. 
데이터의 삽입 삭제가 많고 배열이 복잡할 때 사용 
 
 
 
 

📌 2. 구간 합  (핵심 개념) 

 
구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 
코딩 테스트에서 사용 빈도가 높다
 

 
구간 합의 핵심 이론 

 

S[i]=A[0]+A[1]+ ... + A[i-1]+A[i] //A[0]부터 A[i] 까지의 합
S[i]=S[i-1]+A[i]
S[j]-s[i-1] // i에서 j까지의 구간합