[캐치 멘토링] "IT기업 개발자가 알려주는 인턴맞춤 코딩테스트" 후기

오늘은 '서용준 멘토'님의 "IT기업 개발자가 알려주는 인턴맞춤 코딩테스트" 강의를 수강하게 되었습니다.

강의는 이런 순서로 진행되었습니다.
- 자료구조, 알고리즘 공부했던 방법
- 문제풀이 노하우 및 예시

강의를 들으면서 정리가 필요했던 내용을 요약해서 블로그에 기술하고자 합니다.

---

<비전공자>

비전공자였지만, 언어도 모르는 상태에서 2020년 처음 프로그래밍을 공부하기 시작한 멘토님

진입장벽이 비교적 낮은 파이썬을 공부했고, '점프 투 파이썬' 책 처럼 무료로 볼 수있는 경우가 있어서

책과 강의를 통해 파이썬 언어를 공부했다고 하였다.

전공자인 나에게도 어려운 언어 공부인데, 처음 접한 언어로 취업까지 했다는 것이 새삼 대단하게 느껴졌다.

자료구조나 알고리즘 공부의 경우

SW Expert Academy 사이트에 있는

Learn - Course - Programming Intermediate 를 공부한 이후 Programming Adavanced과정까지 수료

여기에서는 자료구조를 배울 수 있는 짧은 강의와 그 자료구조를 이용해 풀 수 있는 문제가 몇가지 주어지는데,

동영상 내용의 이해가 어려워서 도움이 크게 되진 않았다고 소개해주셨다.

어떠한 자료구조를 배워야하는지에 대한 "목록"을 보기에는 매우 적합할 것 같았다.

---

<자료구조 공부 - 시작>

자료구조들을 공부하면서 어떻게 작동하는지를 직접 구현해보고

자료구조에 대해서 어느정도 이해가 잡히고 나서 코드로 알고리즘을 접한 멘토님의 말에

자료구조의 기초가 중요한데 문제 푸는 것에만 급급해서 쉬운 문제를 풀고, 다시 자료구조의 문제가 나오면 헤매는

내 모습을 반성하기도 했다.

---

<자료구조 공부 - 방법>

Programming Adavanced에서 그래프의 최소 비용 문제(응용 - 구현7)까지 구현이 가능하면  
어느정도 기업들의 코딩테스트 수행에는 문제가 없을거라고 했다.

이러한 공부 방법이 정답은 아니지만 나에게는 다양한 공부 방법 중 하나를 찾은 느낌이었다.

백준, 프로그래머스, LeetCode에서 문제를 풀어보며 자료구조의 순서에 따라 풀어본 경우는

백준(단계별로 풀어보기) 뿐이었던 것 같다.

그마저도 어렵다는 이유로 스택, 큐까지 완료를 하였지만 블로그에 코드 리뷰를 통해 다시 복습해봐야겠다고 생각했다.

>> SW Expert Academy 에서 자료구조에 대한 기초를 다 잡는 것도 한 방법!

멘토님이 대부분의 기업에서 코딩테스트를 수행해보면서 "시간복잡도"를 고려하는 문제의 비중은 적었고,

복잡한 구현을 해야하는 문제가 더 많았다. 

그때마다 백준 - 문제집 - 삼성 SW 역량 테스트 기출 문제 를 통해 연습했던 것이 도움이 되었다고 하였다.

삼성의 SW자격증 문제에는 A, B, C형이 있는데 A형 문제들을 여기서 많이 풀어볼 수 있다.

이 문제들의 특징은 구현이 복잡한 것인데 이 문제들로 연습을 해보는 것이 도움이 많이 될 것 같았다.

---

<알고리즘- 소개할 문제 (2048 게임)>

멘토링에서 접한 알고리즘은 2048게임 문제였다.

<2048>

1. 전체 블록을 상하좌우 네 방향 중 하나로 이동시킬 수 있음

2. 같은 값의 두 블록이 충돌하면 두 블록은 하나로 합쳐짐

3. (중요)한번의 이동에서 이미 합쳐진 블록은 또다른 블록과 합쳐질 수 없음

4. 이 문제에서는 게임과 달리 블록이 추가되지 않는다.

- 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 알아내야함
- 보드의 크기는 N * N이고 (이러한 조건)
- N은 1~20 임 (이러한 조건들 매우 중요)
- 0은 빈칸을 나타냄

문제 풀기전에
# 출력 : 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록
# 체크할 조건
# N * N 
# 1 <= N <= 20
# 0은 빈칸

처럼 조건들을 미리 적어놓고 풀어보는 것이 도움이 많이 될 것

---

<복잡한 알고리즘 푸는 방법>

요구하는 내용을 전부다 구현하려고 하면 디버깅도 잘 안되고 시간이 부족한 경우가 많은데, 

하나의 큰 요구사항이 있으면 요구사항을 쪼개서
각각에 대해서 구현하고 (클래스)
각각을 디버그 한다음에
조립하는 방식으로 풀어보면 매우 수월할 것

---

<요구사항 쪼개기>

1. 왼쪽 방향으로의 블록 이동 & 병합
# (board, N) -> None

>> 왼쪽 방향으로 이동하는 로직만 담은 클래스

2. 방향 전환 (회전)
# (board, direc) -> board

>> 1번조건에서의 왼쪽 방향으로만의 이동말고도 오른쪽, 위, 아래 이동은 
>> 판을 회전시킨다음 왼쪽으로 이동시키는 방식을 택함
오른쪽 이동할때 (좌우반전을 하면 왼쪽으로 가는 것이 오른쪽으로 가는 셈)
위쪽으로 이동할때 (반시계 90도로 회전하면 결국 위쪽으로 가는 셈)
아래쪽으로 이동할때 (시계 90도로 회전하면 결국 아래쪽으로 가는 셈)

>> 모든 연산이 끝나면 다시 판을 되돌리기

3. 가장 큰 블록 값 갱신

전체의 블록을 탐색해서 가장 블록이 큰 값이 무엇인지 찾는 함수를 만들기

---

<코드 리뷰>

<요구사항 쪼개기 - 1번>

j문으로 행을 순회하면서
020
000
000
처럼 주어질 경우

020에서 값을 찾으면 (2) <-> 값이 없는 왼쪽의 0과 바꿔주는 로직

- 병합된것은 merged 변수로 표현
- 바꿔야될 위치는 now 변수로 표현
- 같은숫자가 있으면 병합을 하고 한번 병합된 것은 병합되지 않도록 merged로 처리

move(board, N) 함수는

직접만든 board와 3x3 (N)을 테스트케이스로 입력하여 제대로 작동하는지 확인

함수를 다 만들었으면 먼저 디버그를 해본 후 다음 클래스를 설계해나가는 방식이 좋을 것이라고 배웠다.

<요구사항 쪼개기 - 2번>

rotate(board, d, N)
으로 하고 d는 1, 2, 3의 경우로 만들어

d == 1일때 오른쪽 방향으로 판단하고
board[i].reverse() 처럼 좌우반전 시키고

등등

board[i][j], board[N-1-j][i] 
처럼 인덱스를 다루는 것은 더 연습이 많이해야할 것 같았다.

<요구사항 쪼개기 - 3번>

maxblock(board, N)
result 를 전역변수로 두고 가장 큰값을 갱신시켜주게끔 했음

<백트래킹>

모든함수를 실제 실행 로직에서 가져다가 사용

BT(board, N, depth)

if depth == 5:
	maxblock(board, N)
	return

은 출력 조건 중 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 구하라고 하였으니 maxblock를 가져다 쓰는 것

for i in range(4): 
# 이것은 상하좌우 4방향으로 탐색하는 것을 보여줌

rotate(next_board, i, N)
# 바꿔가면서

move(next_board, N)
# 이동을 하는 것

# 보드를 회전시켰으니 다시 복구시켜주는 코드
if i == 1:
	rotate(next_board, i, N)

elif i == 2:
	rotate(next_board, 3, N)

elif i == 3:
	rotate(next_board, 2, N)

맨 마지막의에 
BT(next_board, N, depth+1)
처럼 해주어서 depth를 증가시키며 순회를 하게끔 함

---

* 백트래킹(backtracking)이란? 

: 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 
최적화 문제와 결정 문제를 푸는 방법

---

<메인 함수>

BT(field, N, 0) : 함수를 호출

이렇게 요구사항 쪼개기 방식을 통해 오답률이 훨씬 줄어들고 디버그에 사용되는 시간도 많이 줄어서
코딩테스트를 볼때 효과를 많이 볼 것이라고 도움 주셨다.

결론적으로 구현이 빡센 문제들을 요구사항을 쪼개가며 푸는 연습을 하면,

코딩테스트도 자신감있게 풀어낼 수 있을 것 같았다.

---

<사전질문>

Q. 처음 코딩테스트를 혼자 공부할때 좋은 방법?

A. 직접 자료구조를 구현해보면서 공부하는게 도움이 되었던 것 같아요.
너무 어려운것을 한번에 도전하기보단 난이도가 낮은 것부터 접근하는것도 괜찮은 방법같습니다.

가장 중요한 것은 기초가 되는 것에 시간을 가장 많이 들여서 공부해야한다는 것
기본적인 자료구조에서 완전히 이해했다고 생각할만큼 탄탄히 공부해야합니다.

스택, 큐는 자료구조자체로만 보면 어렵지 않지만 활용하는 알고리즘에서 어려워지기도 합니다.
저도 BFS, DFS 이해가 쉽지 않았는데, 일주일동안 그 자료구조만 공부해보니 익숙해졌습니다.

Q. 코딩테스트준비는 독학보다 스터디 방식?

A. 둘다 해본 경험으로써 스터디같은 경우에는 공부할 수 있는 동기를 계속 주입시켜주는 "정도"이지만,

혼자 공부를 지속할 수 있는 마음가짐이면 혼자 공부하는 것도 괜찮은 것 같습니다.

혼자 공부하는 것이 괴롭고 어렵고 힘들면 스터디도 도움이 될 것 같습니다.

Q. 코딩테스트 준비기간?
A. SSAFY 3기를 하면서 처음 프로그래밍 언어, 자료구조와 알고리즘 공부를 시작했었습니다.
6개월정도 알고리즘 문제연습을 엄청 많이 했었고, 그 이후로는 유지하는 정도로 한달에 1문제를 풀었습니다.

Q. 실력이 부족하더라도 계속 지원하면서 코딩테스트를 보는 것을 추천하시나요?

A. 네, 지원을 하고 실력을 늘리는 게 중요합니다.
면접, 코딩테스트.. 일단 지원해서 경험으로 실력을 늘리는 것이 중요합니다.

<중요한 것>
- 상세한 구현을 요하는 문제연습
>> 기업 코딩테스트 및 삼성 A형 기출문제
상세한 구현을 요하는 문제위주로 연습해보며 요구사항을 잘게 쪼개서 각각 디버그 해보기

- 요구사항 쪼개기
>> 쪼갠 요구사항을 각각 구현하며 디버그

---

마무리하며,

멘토링을 자주 받았던 시기도 있었지만 지금은 갈피를 못잡고 이것저것 공부를 하고 있었다.

취업준비에서는 입사 지원이 먼저이고, 계속 부딪혀보며 경험을 하는 것

또한 가장 난관이었던 코딩테스트 준비도 자료구조의 기초를 잘 알고 시간을 들여 탄탄히 해놓으면

자신감이 생긴다는 것을 배울 수 있었다.