Ch1. 코딩 테스트 개요

1. 코딩테스트 개념과 배경

    - 온라인 저지 사이트(Online Judge)

      : 프로그래밍 대회나 코딩 테스트에서 나올 법한 문제를 시험해보는 온라인 시스템이다.

          1-1. 코딩테스트의 유형

                1) 온라인 코딩 테스트

                    : 온라인 코딩 테스트는 타인과 문제 풀이를 공유하지 않는 선에서 인터넷 검색을 허용하는 경우가 많지만, 

                      명확한 규정을 안내 사항으로 명시하고 있으니, 규칙과 주의 사항을 반드시 확인해야 한다.

                      온라인 IDE를 이용하는 경우 소스코드가 공개 상태로 온라인에 배포되어 부정행위로 간주될 수 있으므로 주의!!

                      (Ideone과 같은 온라인 IDE 서비스에서 소스 코드 옵션이 public일 경우 구글 등의 검색 엔진에 노출되므로!)


                2) 오프라인 코딩 테스트 

                    : 응시자가 많이 좁혀진 상태이므로 코딩 테스트를 보고 별도의 면접실로 안내되어 화이트보드 혹은 종이와 함께

                      자신이 문제를 해결한 과정 등에 대해서 설명하기도 한다.

 

         1-2. 코딩 테스트 준비를 돕는 다양한 서비스

                1) 코드업

                    : [문제] - [문제집]에서 [기초 100제]를 꼭 풀어보고 백준 온라인 저지로 넘어가기

                2) 백준 온라인 저지

                    : 알고리즘 분류 태그와 난이도를 부여하는 크롬의 확장 프로그램 solved.ac를 설치하기

                      [문제] - [알고리즘 분류]으로 이동하면 유형별 알고리즘을 풀 수 있는데, 책의 진도와 맞게 풀기

                      책을 완독한 이후에 SW 역량 테스트 문제를 풀기

                3) 프로그래머스

                   : 카카오 공채 문제를 모두 제공하는 사이트이다.

                     책을 통해서 기초 개념을 잡고, 추가로 프로그래머스에서 문제를 풀기

                4) SW Expert Academy

                   : 삼성에서 '상시 SW 역량테스트' 제도를 운영하고 있는데, A형을 응모해서 실력을 확인하길 바란다.

 

        1-3. 어떤 언어가 코딩 테스트에 유리할까?

              -  가장 유리한 언어는 Python과 C++이다.

 

2. 실습 환경 구축하기

   - 일반적인 코딩 테스트는 문제마다 소스코드를 1개만 제출하므로 굳이 별도의 개발 환경을 구축하지 않아도 된다.

     따라서 온라인 IDE를 사용하는 게 좋다.

 

        2-1. 온라인 개발 환경

              - 리플릿, 파이썬 튜터, 온라인 GDB이 있다.

나는 온라인 IDE로 리플릿을 선택했다.

 

        2-2. 오프라인 개발 환경

              - 파이참, 주피버 노트북, 비주얼 스튜디오 코드 등이 있다.

혹시 몰라 오프라인으로 파이참을 설치했다.
Run은 되는데..
뭐가 문제인지.. Python console은 안 된다ㅠㅜ 검색을 해도 잘 안 나온다ㅠ

일단 갈 길이 멀기 때문에 이렇게 만족하고 다음 장으로 넘어간다!

 

3. 복잡도

        - 복잡도의 종류

          1) 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수

          2) 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양

          +) 실제로 메모리를 더 많이 사용해 시간을 비약적으로 줄이는 방법으로 메모이제이션(memorization) 기법이 있는데
              이 내용은 8장에서 다룬다.

 

        3-1. 시간 복잡도

              - 시간 제한이 있다. (1~5초)
                 : 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는데 걸리는 시간

              - 빅오(Big-O) 표기법을 사용한다.

                 : 가장 빠르게 증가하는 항만을 고려하는 표기법 // 연산의 횟수에 focus

                    - 시간 복잡도는 언제나 최악의 경우를 우선적으로 고려해야 한다. (차수가 작은 항들을 완전히 무시하지 말 것!)

                 [연산]: 프로그래밍 언어에서 지원하는 사칙 연산, 비교 연산 등의 기본 연산을 의미

              - 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 C 언어를 기준으로
                통상 1초 이상의 시간이 소요된다.

                따라서 능숙한 개발자들은 문제의 조건을 확인한 뒤에 사용할 수 있는 알고리즘을 좁혀 나간다.

 

 

        3-2. 공간 복잡도

              - 메모리 제한이 있다. (128 ~ 512MB)
                 int arr[1000] : 4KB, int arr[1000000] : 4MB, int arr[2000][2000] : 16MB

              - 빅오(Big-O) 표기법을 사용한다.

 

        3-3. 시간과 메모리 측정

              - 파이썬에서는 프로그램 수행과 메모리 사용량을 측정할 수 있다. 자신이 설계한 알고리즘의 성능을 실제로 확인하며

                시간 측정 라이브러리를 사용해보는 습관을 기르는 것이 좋다.

                (ex. 선택 정렬과 기본 정렬 라이브러리 수행 시간 비교 가능)

+ Recent posts