[묘공단] 코딩 테스트 합격자 되기 챕터 1 ~ 5

묘공단 코딩 스터디에서 책 정리

 

코딩 테스트 합격자 되기 자바편

책 제목 : 코딩 테스트 합격자 되기 자바편

지은이 : 김희성

00. 코딩 테스트를 준비하기 전에

1. 문제를 풀고 꼭 다른 사람의 코드를 읽어 본다.

누군가의 코드를 읽는건 어렵지만 내 생각이 아닌 다른 사람의 풀이를 봐야 생각의 폭이 넓어진다.

 

2. 코딩 테스트가 어려운 이유는 아는것과 모르는 것이 명확하지 않아서이다. 

그 점을 파악하기 위해서는 못푼다고 그만두지않고 기록해야한다. 그러면 왜 그런 코드를 작성했는지 의도가 분명해지고 파악이 쉽게된다.

 

3. 단 시간 공부로는 알고리즘의 수준을 올릴 수 없다.

 

4. 문제를 풀고 꼭 말로 설명할 줄 알아야 정확히 풀었다고 할 수 있다.

 

문제를 풀때 1번째 작업

( 문제 분석 단계 -> 구현 X )

 

문제를 동작 단위로 쪼개서 분석한다.

 

문제의 제약 사항을 정리하고 고려해서 테스트 케이스를 추가한다. -> 어떤 알고리즘을 선택할지 유용

 

입력값을 분석한다. -> 시간 복잡도를 고려한다.

 

데이터 구조에 따라서 유리한 타입을 선택한다. -> 예를 들어 원시형 배열을 사용할지 동적인 컬렉션 배열을 사용할지 선택한다.

 

문제를 풀때 2번째 작업 

( 의사 코드로 설계하는 연습 )

 

원칙 :

1. 프로그래밍 언어로 작성하면 안됨

2. 일반인도 이해 할 수 있는 자연어로 작성해야 함

3. 일정한 형식이 없음 (자유롭게 작성)

 

세부구현이 아닌 동작 중심 구성 -> 점수를 예시 입력을 받는다. 메뉴의 순서를 정한다 등

 

문제 해결 순서로 작성한다. -> 점수 입력, 60점 넘는지 확인, 60점 이상이면 통과, 60점 미만은 실패

 

충분히 테스트한다. -> 구현단계에서는 수정하기 어렵기때문에 충분히 테스트한다.

 

알고리즘의 효율 분석 시 시간 복잡도란?

알고리즘의 성능을 나타내는 지표로 입력 크기에 대한 연산 횟수의 상한을 의미한다.

같이 문제를 푼 여러 방법이 있다면 시간복잡도 ( 연산 횟수 )가 작을 수록 효율적이고 좋다.

 

자주 사용 하는 빅오 표기법

표현 방법은 최고차항을 남기고 계수를 지우면 된다.

예시 ) 2x^2 + 3x + 5 의 표현 방법은 O(x^2)이다.

 

 

일반적인 1초당 컴퓨터 연산 가용범위 ( CPU 스펙 고려 X )

 

주요 학습 내용 정리

1. 문자열

StringBuffer, StringBuilder, String 비교

 

String에 대해서

String 객체는 값을 변경할수 없는 Immutable 객체이다.

즉 기존 String에 + 로 새로운 String을 더하면 새로운 String의 인스턴스가 배정된다.

반복적으로 String에 새로운 String을 추가하거나 삭제하는 경우 불필요한 인스턴스가 생성된다. -> 메모리 낭비

 

문자열 추가, 수정, 삭제시 하나의 인스턴스로만 동작하기 위한 방법 2가지

StringBuffer는 Tread-safe를 통해서 멀티쓰레드에서 무결성을 보장해줄수있다.

StringBuilder 클래스는 Tread-safe 장치가 없어서 동기화 고려할 필요가 없어 속도가 더 빠르다.

 

StringBuilder를 멀티 쓰레드에서 사용 시

public class StringBuilderThreadIssue {
    public static void main(String[] args) throws InterruptedException {
        // StringBuilder 인스턴스 생성
        StringBuilder stringBuilder = new StringBuilder();

        // 스레드 개수 정의
        int numberOfThreads = 10;
        Thread[] threads = new Thread[numberOfThreads];
        int iterations = 100;

        // 여러 스레드를 생성하여 StringBuilder에 문자 추가
        for (int i = 0; i < numberOfThreads; i++) {
            threads[i] = new Thread(() -> {
                for (int j = 0; j < iterations; j++) {
                    stringBuilder.append("a");
                }
            });
            threads[i].start();
        }

        // 모든 스레드가 종료될 때까지 대기
        for (int i = 0; i < numberOfThreads; i++) {
            threads[i].join();
        }

        // 결과 출력
        System.out.println("Expected length: " + (numberOfThreads * iterations));
        System.out.println("Actual length: " + stringBuilder.length());
    }
}

1번째 결과 값

Expected length: 10000
Actual length: 8559

 

2번째 결과 값 

Expected length: 10000
Actual length: 7859

 

3번째 결과 값

Exception in thread "Thread-0" Exception in thread "Thread-1" java.lang.ArrayIndexOutOfBoundsException: arraycopy: last destination index 1289 out of bounds for byte[1150]
예외가 발생했는데 append 내부 동작 과정중 배열을 복사할때 배열길이가 달라서 발생한 오류

 

이런 경우 StringBuilder를 StringBuffer로 변경하면 append 함수에 synchronized를 통해 메서드 단위의 락을 걸어 무결성 보장

2. 배열

ArrayList

특징

0. 원시형 데이터 배열 형태이지만 메서드를 통해서 동적으로 동작하도록 작성하였다.

1. 데이터를 인덱스로 검색시 ( get API ) 빠르다. 원시형 배열이기 때문에 인덱스 검색이 빠르다.

2. 배열에 공간이 남아있다면 데이터 추가시 빠르다. 

예를 들어 배열 5개를 추가하고 하나를 삭제한 다음 다시 하나를 추가한 경우는 빠르다.

배열에 5개를 추가하고 새로 하나 추가하는 경우는 새롭게 원시형 배열을 생성해야서 느림.

ArrayList 클래스의 elemetData

LinkedList

특징

0. 노드라는 클래스를 하위 클래스로 서로간에 연결을 맺고있는 형태이다. ( 원시형 배열 X )

1. 데이터를 인덱스로 검색시 처음 노드부터 쭉 연결된 노드를 찾기때문에 느리다.

2. 노드 수정시 빠른 이유 노드간에 포인터로 연결되어있어서 수정하고자 하는 위치에 포인터만 삽입데이터로 수정해주면 수정되기때문에 빠르다.

LinkedList의 노드클래스 앞뒤 연결 정보

Vector

특징

들어는 봤지만 개발환경에서 사실 한번도 본적이 없는 타입이다.

1. thread-safe라는 점이 특징이다. ArrayList와 LinkedList는 thread-safe를 보장하지않는다.

보통 다른 방법으로 멀티 스레드 환경에서 동기화를 적용하기 때문에 잘 사용되지않는다.