마쏘's 개발 성장기

Ch2. 코딩 테스트 개요16~20년 코테 기출 유형 분석

1. 최신 출제 경향과 준비 방향

    - IT 직군에서 코딩 테스트를 보는 대표적인 기업은 삼성전자, 카카오, 라인이 있다.

    - 보통 2~5시간 동안 8개 이하의 알고리즘 문제들을 풀도록 한다. (얼마나 정확하고, 빠른 알고리즘인지 순위를 매김)

         1-1. 코딩테스트는 문제 해결 능력을 확인하는 시험

                - 잘못된 편견
                 : 기업에서 주관하는 코딩 테스트는 매우 높은 사고력이나 어려운 알고리즘 기반의 지식을 요구하지 않는다.

                   따라서 코딩 테스트에는 주로 기초 알고리즘에 기반하는 문제가 출제된다.

                - 코딩 테스트 기출 유형 빈도수

                   simulation or BFS/DFS > greedy >> sort or dynamic programming > binary search or shortest path

                   (구현 or BFS/DFS > 그리디 > 정렬 or 다이나믹 > 이진 탐색 or 최단 경로)

        1-2. 기업별 문제 출제 경향

               - 카카오는 문자열을 처리하는 구현 문제와 다양한 케이스를 고려해야 안정적으로 만점을 받을 수 있는 문제들이,

                 삼성전자는 문제를 바르게 읽고, 예외 상황을 적절히 처리하는 방식으로 소스코드를 작성해야 하는 문제들이

                 출제되었다.

               - 보통 합격자는 문제의 평균 69%를 풀었으며, 불합격자는 평균 38%의 문제를 풀었다고 한다.

2. 연도별 코딩 테스트 유형 분석

   - 알고리즘 대회 수상 경험이 있는 응시자는 삼성전자, 카카오, 라인 모두 합격권에 있다.

     (국제 알고리즘 대회 기준, 코드포스 블루 이상, ACM-IMPC 서울 지역 대회 본선에 안정적으로 진출할 수 있는 수준)

  - 공채를 기준으로 설명하지만, 인턴 채용의 경우에도 비슷한 수준과 유형의 문제로 출제된다.

        2-1. 2020년

              - 삼성전자(완전 탐색, 시뮬레이션, DFS/BFS)
                : 완전 탐색 유형에서 시뮬레이션 유형으로 바뀌고 있는 추세이다. 둘 다 요구하는 문제가 출제되고 있으므로
                  사소한 조건을 고려하면서, 약간 응용된 BFS/DFS 소스 코드를 작성할 수 있는 수준으로 공부하자.

              - 라인(시뮬레이션, 문자열, 자료구조 [4/6])

        2-2. 2019년

              - 삼성전자(완전 탐색, 시뮬레이션, DFS/BFS)
                 : 기출문제가 잘 알려져 좋은 성적을 받고 있기 때문에 2문제를 맞혀야 통과할 수 있었다.

              - 카카오(1차:시뮬레이션, 이진 탐색, 자료 구조 중 7문제 [3/7]예상)(2차:추천 시스템 개발 1 문제)

                 : REST API, JSON 등의 원리에 대해 이해하고 있어야 풀 수 있는 개발형 코딩 테스트가 출제되었다. -> 부록 C

              - 라인(상:탐색,시뮬레이션,문자열,다이나믹 프로그래밍 [3/5]예상)(하:자료구조,완전탐색,시뮬레이션 [4/6])

        2-3. 2018년

              - 삼성전자(완전 탐색, 시뮬레이션, DFS/BFS)

              - 카카오(1차:시뮬레이션, 그리디, 자료 구조 중 7문제 [3/7]예상)(2차:시뮬레이션 개발 1 문제)

                 : REST API, JSON 등의 원리에 대해 이해하고 있어야 풀 수 있는 개발형 코딩 테스트가 출제되었다. -> 부록 C

              - 라인(상:탐색,시뮬레이션,그리디,다이나믹 프로그래밍 [2/5])(하:그리디,탐색,시뮬레이션,문자열 [2/4]예상)

        2-4. 2017년

              - 삼성전자(완전 탐색, 시뮬레이션, DFS/BFS)

              - 카카오(1차:시뮬레이션, 그리디, 문자열 중 7문제 [4/7]예상)(2차:클롤러 개발 1 문제)

                            (3차:시뮬레이션, 그리디, 문자열 중 5문제 [3/5]예상)

                 : REST API, JSON 등의 원리에 대해 이해하고 있어야 풀 수 있는 개발형 코딩 테스트가 출제되었다. -> 부록 C

              - 라인(상:탐색,시뮬레이션,그리디 [3/5])(하:그리디,시뮬레이션,문자열 [2/5]예상)

        2-5. 2016년(이하 생략)

3. 성공적인 취업을 위한 가이드

    3-1. 채용 프로세스
           : [서류 검토] -> [코딩 테스트] -> [기술 면접] -> [인성 면접]

            3-1.1) 대기업과 스타트업의 채용 프로세스 비교

                   - 대기업은 코딩 테스트에, 스타트업은 기술 면접에 더 비중을 둔다.

            3-1.2) 알고리즘 문제만 잘 풀면 될까?

                   - 알고리즘 외에도 컴퓨터 구조, 운영체제 등 컴퓨터 공학 전반에 대한 다양한 지식에 관해 공부해야 한다.

                   - 인성 면접에 대한 질의 응답도 준비해야 한다.

    3-2. 기술 면접의 대표 유형

           : 알고리즘 문제 풀이와 질의응답/ 포트폴리오 질의응답/ 컴퓨터공학 지식 질의응답 유형으로 진행한다.

           : 본질은 업무에서 요구하는 만큼의 컴퓨터 이론 지식을 갖추고 있으며, 필요한 관련 프로젝트에 경험이 있고,

             알고 있는 내용을 논리 정연하게 설명할 수 있으면 된다.

            3-2).1) 알고리즘 문제 풀이와 질의응답 형식

            3-2).2) 포트폴리오 질의응답 형식

            3-2).3) 컴퓨터 공학 지식 질의응답 형식

             // 추후에 p73

    3-3. 기술 면접의 준비

           : 기업에서 원하는 직원은 문제를 풀어 정답 판정을 받는 지원자가 아니라, 자신이 어떤 방법으로 문제에 접근하여

             어떠한 알고리즘을 사용했는지를 논리 정연하게 설명할 수 있는 지원자를 원한다.

             -> 평소 기술 블로그나 깃허브 저장소를 운영하며 능력을 키워갈 수 있다.

            3-3).1) 깃허브 사용하기

            3-3).2) 기술 면접의 어려움

            3-3).3) 인성 면접 질문 리스트
                        Q1.

                        Q2.

                        Q3.

    3-4. 알고리즘 문제 사이트
           : 외국계 기업에 취업하려는 취업 준비생이나 국제 알고리즘 대회를 준비하는 학생은 아래 사이트를 추천한다.

             (영어 문제를 해석하는 능력 또한 필요하다)

             3-4).1) 코드 시그널

             3-4).2) 코드 포스

             3-4).3) 정올

    3-5. 커뮤니티 사이트

             3-4).1) 생활코딩

             3-4).2) BOJ Slack

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이 있다.

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

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

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

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. 선택 정렬과 기본 정렬 라이브러리 수행 시간 비교 가능)

코딩 테스트를 준비하다가 확실하게 회사의 산업에 따라서 유리한 언어가 있다는 생각이 들었다.

삼성 기출 문제만 열심히 풀던 내가 라인이나 카카오 온라인 코딩 테스트를 접했을 때의 충격이란...!
(문자열만 나오면 C++을 사랑하는 저는 웁니다..ㅠㅜ)

그래서 미루고 미루다 Python에 대해서 공부해야겠다는 다짐을 했고, 

이것이 취업을 위한 코딩 테스트다! 라는 책을 보고 python과 추가로 있는 c++ 파일까지 보면서 알고리즘을 뽀개보려고 한다.

(진짜 대학생 때도 한빛미디어에서 나온 책들의 덕을 톡톡히 봤는데 진짜 사랑합니다)

책에서 추천하는 단계가 있다.   

1. 초급 단계     

      1) 파이썬 문법 공부(부록 A 이용)

      2) 코드업에서 쉬운 문제부터 200문제 가량 풀기

      3) 유형별 알고리즘 이론(2부)과 기출문제(3부)학습하기

      4) 백준 온라인 저지에서 유형별 문제 5개 이상 풀기

   2. 중급 단계

      5) 책 완독 후 백준 온라인 저지에서 삼성 SW 역량테스트 문제집 풀기

      6) 프로그래머스에서 카카오 문제집 풀기

      7) 책의 2부와 3부를 중심으로 주요 알고리즘 유형 복습하기

나는 5단계에 있는 삼성 SW 역량테스트 문제를 풀었고, DFS 또는 BFS로 푼 다른 풀이와 좋은 풀이를 공부한 상태이다.
(이것도 차근차근히 올려야하는데.. 이제 깃허브도 알고, 블로그에 기록도 하니까 잘 올려야지!!)파이썬은 처음 배우는 거니까 1단계부터 빠르게 훑어볼 생각이다ㅎㅎ

필자의 직강 동영상을 볼 수 있는 링크이다.

www.youtube.com/playlist?list=PLRx0vPvlEmdBFBFOoK649FlEMouHISo8N

필자에게 질문을 남기거나 코드를 볼 수 있는 github이다.

github.com/ndb796

현재 책에 나온 부록 A(파이썬 문법 공부)를 한 번 훑었고, 1장부터 공부하러 고고!

해당 문제의 백준 사이트 링크
https://www.acmicpc.net/problem/14502

입력)

- 세로 크기 N과 가로 크기 M (3 <= N, M <= 8)

- 연구소 모양을 나타내는 N*M 크기의 2차원 정수 배열(0 or 1 or 2)

- 2<= 바이러스(2)의 개수 <= 10

출력)

-  얻을 수 있는 안전 영역의 최대 크기

입, 출력 분석)

- (3 <= N, M <= 8) 이므로 안전 영역의 최대 크기가 정수를 넘지 않는다. 따라서 integer로 정의한다.

핵심)

- 주어진 연구소 지도에 벽 3개를 세운다.

- 바이러스를 퍼트린다.

- 바이러스가 다 퍼졌으면 안전 영역을 구한다.

위 과정을 주어진 연구소 지도에 벽 3개를 세우는 모든 경우로 다 해본다.

예시 분석)

- (생략)

실수) 

- 예전에 풀었던 것을 다시 보면서 올리는 중이라 어떤 부분에서 실수를 했는지 기억이 잘 안나지만,

 첫 삼성 기출 문제였던 만큼 문제를 이해하고, 문제 유형이나 구현 및 설계까지 시간이 오래 걸렸던 것으로 기억한다.

- 이런 걸 가끔 볼 때마다 나도 조금씩 실력이 늘고 있다는 생각이 든다!

구현)

#include <stdio.h>
#include <queue>
using namespace std;

int N = 0, M = 0, maxArea = 0;
int lab[9][9] = { 0, };
int virus[9][9] = { 0, };
queue<pair<int, int>> vPos;

int dx[4] = { 0, -1, 0, 1 }; // 왼, 위, 오, 아래
int dy[4] = { -1, 0, 1, 0 };

void spreadVirus() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			virus[i][j] = lab[i][j];
			if (lab[i][j] == 2)
				vPos.push({ i,j });
		}
	}
	while (!vPos.empty()) {
		int vx = vPos.front().first;
		int vy = vPos.front().second;
		vPos.pop();
		int x = 0, y = 0;
		for (int i = 0; i < 4; i++) {
			x = vx + dx[i];
			y = vy + dy[i];
			if (x < 0 || y < 0 || x >= N || y >= M)
				continue;
			if (virus[x][y] == 0) {
				virus[x][y] = 2;
				vPos.push({ x, y });
			}
		}
	}
}

void buildWall(int idx, int cnt) {
	if (cnt == 3) {
		spreadVirus(); // 벽 3개를 다 세웠으면 바이러스 퍼트리기
		int area = 0;
		for (int i = 0; i < N; i++) { // 안전 영역 계산하기
			for (int j = 0; j < M; j++) {
				if (virus[i][j] == 0)
					area += 1;
			}
		}
		area > maxArea ? maxArea = area : maxArea;
		return;
	}
	int nx = 0, ny = 0;
	for (int i = idx; i < (N*M); i++) {
		nx = i / M; ny = i%M;
		if (lab[nx][ny] == 0) {
			lab[nx][ny] = 1;
			buildWall(nx*M + ny, cnt + 1);
			lab[nx][ny] = 0;
		}
	}
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			scanf("%d", &lab[i][j]);
	}
	buildWall(0, 0); // 벽 3개 세우기
	printf("%d", maxArea);
	return 0;
}

입력)

- 10개의 테스트 케이스

- 100x100 크기의 2차원 정수 배열

출력)

-  출력값이 integer 범위를 넘지 않음!

- #(테스트 케이스 번호) (각 행의 합, 각 열의 합, 각 대각선의 합 중 최댓값)

입, 출력 분석)

- (생략)

핵심)

- for문을 잘 다룰 수 있는 능력만 있다면 충분히 할 수 있다.

예시 분석)

- (생략)

실수) 

- 대각선 / 부분에서 x index는 증가하고, y index만 99(100아님!)에서 감소한다는 것

구현)

#include<stdio.h>
using namespace std;

#define SIZE 100
int arr[SIZE][SIZE] = {0,};
int MAX = 0;

int main(int argc, char** argv) {
	int test_case;
	for (test_case = 1; test_case <= 10; ++test_case) {
		MAX = 0;
		scanf("%d", &test_case);
		for (int i = 0; i < SIZE; i++){
			int temp = 0;
			for (int j = 0; j < SIZE; j++){
				scanf("%d", &arr[i][j]);
				temp += arr[i][j]; // 각 행의 합
			}
			if(MAX < temp) MAX = temp;
		}
		for (int j = 0; j < SIZE; j++){
			int temp = 0;
			for (int i = 0; i < SIZE; i++)
				temp += arr[i][j]; // 각 열의 합
			if(MAX < temp) MAX = temp;
		}
		int temp1 = 0, temp2 = 0;
		for (int i = 0; i < SIZE; i++){
			temp1 += arr[i][i];
			temp2 += arr[i][(SIZE-1)-i]; // 실수한 부분!
		}
		if(MAX < temp1) MAX = temp1;
		if(MAX < temp2) MAX = temp2;
		
		printf("#%d %d\n", test_case, MAX);
	}
	return 0;
}

추천) 1210. ladder1 문제를 먼저 풀기를 추천한다.

https://masso.tistory.com/23?category=881145

입력)

총 10개의 테스트 케이스

테스트 케이스의 번호, 사다리 정보가 들어있는 100 x 100 크기의 이차원 배열

(0: 아무것도 없음, 1 : 사다리, 2 : 도착 지점)

출력)

# 해당 테스트 케이스 번호, 가장 짧은 이동 거리를 가지는 사다리의 y index 출력

입, 출력 분석)

입력을 보면 마지막 줄에 존재해야할 2가 없음에 주의해야 한다.

핵심)

1210. ladder1 문제 풀이 링크 참고

입력 분석을 통해
- x == 99에 도달할 때까지, 가장 짧은 칸을 이동해온 y index를 구해야 함을 알았다.

복수 개인 경우 가장 큰 x좌표
- y(0 -> 99)로 탐색하며, 짧거나 같은 거리를 가지는 사다리가 있을 때 y index를 갱신하면 된다.

예시 분석)

(생략)

실수) 

- 도착 지점에 도착하는 사다리 중에 짧은 거리를 가지는 사다리를 구하는 문제인 줄 알았는데,가만히 입력을 보니까 2가 없는 것을 알게 되었다. (이래서 사람이 편견이 무섭다)

구현)

#include<iostream>
using namespace std;

int map[100][100]; // 100x100 크기의 이차원 배열
int dx[3] = { 1, 0, 0 };  // 0: 아래, 1: 왼쪽, 2: 오른쪽
int dy[3] = { 0, -1, 1 }; // 0: 아래, 1: 왼쪽, 2: 오른쪽

int main(int argc, char** argv) {
	int test_case, T = 0, ans = 0;
	for (test_case = 1; test_case <= 10; ++test_case) {
		scanf("%d", &T);
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++)
				scanf("%d", &map[i][j]);
		}
		int minLen = 10000; // 0. minLen 정의
		for (int j = 0; j < 100; j++) {
			if (!map[0][j]) continue;
			int x = 0, y = j, dir = 0, len = 1; // 1. len 정의
			while (x < 100) {
				int cnt = 0, key = 0;
				for (int i = 0; i < 3; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx < 0 || nx >= 100 || ny < 0 || ny >= 100) continue;
					if (map[nx][ny]) {
						cnt++;	key += i; // 아래 0, 왼 1, 오 2
					}
				}
				if (cnt == 2 && key < 3) { // 회전
					if (dir == 0) dir = key;
					else dir = 0;
				}
				if (x == 99) break;
				x += dx[dir]; y += dy[dir];	len++; // 2. 총 len 구하기
			}
			if(minLen >= len){ // 3. len 갱신하기
				minLen = len;
				ans = j;
			}
		}
		printf("#%d %d \n", T, ans);
	}
	return 0;
}