[KB IT’s Your Life 7기] 코딩 테스트 자료 구조 후기(aka 알고리즘 특강)

 

안녕하세요.

 

오늘은 밀리고 밀려버린 5월 2주차 기술블로그를 작성하고자 합니다.

 

 

ㅇㅇ

Today I Learned

 

 

5월 11일 부터 5월 20일까지는 알고리즘 특강을 진행했는데요 

강사님은 인프런 강사님으로도 유명하신

개발남노씨 강사님이셨습니다!

개발남노씨 강사님의 인프런 홈 화면

 

강사님은 인프런을 비롯하여 유튜브, 오픈카톡 등 다양한 채널을 통해서 학생들과 소통 및 강의를 진행하고 계신 분인데요.

 

사실 KB IT's your life를 지원할 때 개발남노씨 강사님의 강의가 있다는 것도 제가 지원하게 된 계기 중 하나랍니다!

 

https://www.youtube.com/@nossidev

개발남노씨

 

 

 

수업 교재 및 수업 방식

 

 

 

메인 수업은 기존과 동일하게 줌을 통해서 진행이 되었습니다! 

또한 강사님께서 이론교재 및 수업시간에 진행한 문제에  대한 해설집을

노션으로 정리해주셔서 모르는 것이 있을 때 언제든 찾아 볼 수 있었습니다!

 

 

 

또한 이런식으로 수업시간 중간, 앞뒤로 나온 질문들을 정리해서 함께 공유하는 시간이 되게 유익했습니다!

 

 

 

 

오후에는 오전에 직접 배운 코드를 활용하여 직접 프로그래머스를 통해 코딩을 하는 시간을 가지는데요.

학생별로 개인페이지를 준비해주셔서 이 페이지를 통해 정리할 수 있도록하는 센스가 대박슨... 

 

더 대박인 것은 이런식으로 하나의 문제를 여러번 풀면서 원리를 이해하고 익숙해질 수 있는 가이드라인도 만들어 주셨습니다!

완전 대만족

 

 

 

 

아무튼 오늘은 1일차부터 5일차까지 수업 중 1일차 수업에 대한 간단한 리뷰를 진행해보도록 하겠습니다!

 

1일차: 코딩테스트 개론

 

1일차는 크게 5가지의 개념을 위주로 수업이 진행되었습니다.

 

- 코딩테스트 개론

- 테스트 케이스 용어 정리

- 기초 자바 문법

- 자료구조 및 알고리즘 개념

- 시간 복잡도

- 완전탐색 (기초)

- 리스트

- 정렬

- Linked List

- Queue

- Stack

 

대부분이 코테를 보기 위한 중요한 개념들이어서 하나하나씩은 추후에 정처기 포스팅을 올리면서 정리하도록하고

오늘은 대표적인 몇가지만 알아보도록 하겠습니다.

 

테스트 케이스 용어 정리

 

테스트 케이스 (Test Case)	입력값(Input)과 기대 출력값(Output)의 쌍. 내 코드가 이 케이스를 모두 통과해야 정답
예제 입출력	문제에서 공개적으로 제공하는 테스트 케이스
히든 케이스 (Hidden Case)	채점 시 사용되지만 공개되지 않는 테스트 케이스
엣지 케이스 (Edge Case)	최솟값, 최댓값, 빈 입력 등 경계 조건에 해당하는 케이스
AC (Accepted)	모든 테스트 케이스를 통과하여 정답 처리된 상태
WA (Wrong Answer)	출력 결과가 기대값과 다른 경우
TLE (Time Limit Exceeded)	제한 시간 내에 실행이 완료되지 않은 경우
MLE (Memory Limit Exceeded)	메모리 사용량이 제한을 초과한 경우
RE (Runtime Error)	실행 중 오류 발생 (배열 범위 초과, NPE 등)
CE (Compile Error)	코드가 컴파일되지 않은 경우

 

 

 

 

 

시간 복잡도

 

시간복잡도란?

 

입력 크기 n에 따라 알고리즘이 수행하는 연산 횟수의 증가율을 표현한 것입니다.

코딩테스트에서는 보통 1초에 약 1억(10^8) 번 연산이 가능하다고 봅니다.

그래서 강사님은 10^5이란 숫자를 강조하시며, 범위가 10^5 라면 n^2의 복잡도로 풀면 안된다는 꿀팁을 전수해주셨습니다!

 

또한 빅오 표기법 (Big-O Notation) 이라고 하여 아래와 같은 표기법을 주로 사용합니다.

 

표기법이름예시

O(1)	상수 시간	배열 인덱스 접근, 해시맵 검색
O(log n)	로그 시간	이진 탐색
O(n)	선형 시간	배열 순회
O(n log n)	선형 로그 시간	병합 정렬, 힙 정렬
O(n²)	이차 시간	이중 반복문, 버블 정렬
O(2ⁿ)	지수 시간	재귀 완전탐색
O(n!)	팩토리얼 시간	순열 완전탐색

 

 

 

완전탐색 (기초부분)

완전탐색이란?

가능한 모든 경우의 수를 탐색하여 정답을 찾는 방법입니다.
시간 복잡도가 높아 입력이 작을 때만 사용 가능하지만, 구현이 단순하고 실수가 적다는 장점이 있습니다.

 

완전탐색의 종류

단순 반복	for 문으로 모든 경우 나열
재귀 (Recursion)	함수가 자기 자신을 호출하며 탐색
순열 (Permutation)	순서를 고려한 모든 배열 탐색
조합 (Combination)	순서를 고려하지 않은 선택 탐색
부분집합 (Subset)	원소를 포함하거나 제외하는 모든 경우

 

 

단순 반복 예시

// 1부터 n까지 합 구하기
int sum = 0;
for (int i = 1; i <= n; i++) {
    sum += i;
}

재귀 예시

int factorial(int n) {
    if (n <= 1) return 1;       // 기저 조건 (Base Case) ★ 반드시 필요
    return n * factorial(n - 1); // 재귀 호출
}

 

순열 예시 

// [1, 2, 3]의 모든 순열 출력
static int[] arr = {1, 2, 3};
static boolean[] visited = new boolean[3];
static int[] result = new int[3];

static void permutation(int depth) {
    if (depth == arr.length) {
        System.out.println(Arrays.toString(result));
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        if (!visited[i]) {
            visited[i] = true;
            result[depth] = arr[i];
            permutation(depth + 1);
            visited[i] = false; // 백트래킹 — 원상복구
        }
    }
}
// 출력: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

 

부분집합 예시

// {1, 2, 3}의 모든 부분집합 출력
static int[] arr = {1, 2, 3};
static boolean[] selected = new boolean[3];

static void subset(int depth) {
    if (depth == arr.length) {
        for (int i = 0; i < arr.length; i++) {
            if (selected[i]) System.out.print(arr[i] + " ");
        }
        System.out.println();
        return;
    }
    selected[depth] = true;   // 포함
    subset(depth + 1);
    selected[depth] = false;  // 제외
    subset(depth + 1);
}
// 출력: {1,2,3}, {1,2}, {1,3}, {1}, {2,3}, {2}, {3}, {}

 

 

 

 

자료구조 (stack, queue, list)

 

나머지 개념들은 정보처리기사 후기와 2~5일차 후기에서 다시 만나겠습니다!