코딩 테스트 및 알고리즘 문제해결 공부 방법

코딩 테스트 및 알고리즘 문제해결 공부 방법 (고려대학교 KUCC, 2022년 4월) from Suhyun Park

코딩 테스트 및 알고리즘 문제해결 공부 방법 (고려대학교 KUCC, 2022년 4월)

1. 1. 코딩 테스트 및 알고리즘 문제해결 공부 방법 박수현 @고려대학교 KUCC · 2022년 4월 29일
2. 2. 안녕하세요! 박수현 me@shiftpsh.com 넥슨엔진스튜디오 기술연구팀 시스템개발파트장 solved.ac 개발자 ICPC국제 대학생 프로그래밍 대회 한국 국가대표, 2021 NYPC넥슨 청소년 프로그래밍 대회 출제위원, 2021 서강대학교 컴퓨터공학과 2학년 (휴학)
3. 3. 개발자가 되려면
4. 4. 채용 프로세스* * 회사별로 차이가 있을 수 있음 서류 접수 서류 평가 or 전화 인터뷰 코딩 테스트 and/or 과제 직무 역량 인터뷰 문화 적합성 인터뷰 채용 스크리닝screening 채용과 면접은 리소스를 많이 투여하는 일이기 때문에 일정 수준의 허들을 넘는 지원자만 인터뷰로 진행합니다
5. 5. 일정 수준의 허들 전공 지식 + 문제해결력 + 구현력을 정량평가하기 좋아서 코딩 테스트를 1차 허들으로 많이 사용합니다 * 자료구조, 알고리즘 설계 한정 전공 지식* 도메인 지식 협업 능력 커뮤니케이션 능력 문제해결력 구현력 성장가능 기업이 지원자가 개발자로서 기대하는 역량
6. 6. 능성 일정 수준의 허들 컴퓨터 알고리즘을 사용해 직접 코드를 작성하게 하여 전공 지식 + 문제해결력 + 구현력을 평가 ‘가장 먼 노드’, © 프로그래머스
7. 7. §0 어디부터 시작해야 하나요? 프로그래밍 언어 정복 → 빈출 알고리즘 공부 → 문제해결 연습
8. 8. C++을 하라고 하던데 1. 2. 3. 직무와 관련된 언어 자신있는 언어 쉬운 언어 아직 언어를 못 정했다면, 회사가 허용하는 언어 중 C++은 같은 알고리즘을 구현했을 때 실행 시간이 가장 빠르고 메모리 사용량이 가장 적으며, 코딩 테스트가 프로그래밍 대회와 비슷한 점이 많아 공부할 리소스가 많다는 장점이 있지만, 일반적으로 C++ 이외의 언어에서 문제의 해결가능성을 보장하지 않는 알고리즘 대회들과는 다르게 코딩 테스트는 실행 시간과 메모리 사용량 제한 등에 관대하므로 사용하고 싶은 언어를 사용해도 무방합니다. 중 하나를 골라 봅시다
9. 9. 회사가 허용하는 언어 채용공고를 확인합시다! S전자 소프트웨어 역량테스트 K사 블라인드 공채 G사 Online Challenge Python, C++, Java는 대부분의 기업에서 허용하고 있습니다
10. 10. 직무와 관련된 언어 채용공고를 확인합시다! N사 게임 클라이언트 엔지니어 K사 채용연계형 인턴십 2022 D마켓 프론트엔드 엔지니어 T증권 DevOps 엔지니어
11. 11. 개인적인 추천 고른 언어의 문법과 자료구조에 익숙해질 때까지 연습합시다! Python Java C++ 입문하기 쉬움 / 현업에서 자주 쓰임 현업에서 자주 쓰임 가장 효율적 + 이외 자신이 사용하기 편한 언어
12. 12. §1 프로그래밍 언어 정복 + 문제해결 환경 적응하기 코드업 기초 100제 - codeup.kr 100문제 · C, C++, Java, Python 한정 백준 단계별로 풀어보기 - acmicpc.net/step 9단계까지 76문제
13. 13. §1 프로그래밍 언어 정복 + 문제해결 환경 적응하기 solved.ac CLASS 1 - solved.ac/class/1 36문제 · 푼 사람 수 내림차순 정렬 추천
14. 14. 정답을 보고 푸는 걸 두려워하지 마세요! 새로운 걸 배우는 경우 혼자 고민하는 것보다 빠르고 효과적입니다 §1 프로그래밍 언어 정복 + 문제해결 환경 적응하기 문제를 풀다 막힌다면… 코드업 게시판 활용 백준 질문 검색 활용 구글 검색
15. 15. §2 빈출 알고리즘/자료구조 #구현* #문자열 #그래프 * ‘구현’은 알고리즘은 아니지만 문제 분류로서는 빈출 **K사 제외하고 기초 수준만 #정렬 #브루트포스 #그리디 #집합과 맵 #최단 거리 #DP** #힙 #스택 #큐
16. 16. 시간 복잡도와 공간 복잡도 계산 컴퓨터는 간단한 동작을 1초에 1억 번 한다 수 하나는 4B ~ 8B다 n = 5,000이네, 그럼 O(n²) 정도는 돌겠구나! n = 200,000이네, 그럼 O(n log n)이나 이보다 빠른 알고리즘을 짜야겠구나. int a[10000000]은 40,000,000B = 40MB int a[5000][5000]은 100,000,000B = 100MB 알고리즘과 자료구조의 시간 복잡도와 공간 복잡도를 기억하도록 합시다 문제의 제한을 보고 쓸 수 있는 알고리즘과 쓸 수 없는 알고리즘을 구분하는 연습을 합시다
17. 17. 빈출 알고리즘/자료구조 공부 solved.ac 태그 / 백준 알고리즘 분류 - solved.ac/problems/tags 문제 난이도 오름차순 정렬 추천
18. 18. 빈출 알고리즘/자료구조 공부 프로그래머스 코딩 테스트 고득점 Kit - programmers.co.kr/learn/challenges?tab=algorithm_practice_kit 38문제
19. 19. 어떤 순서로 공부해야 할지 모르겠다면 백준 단계별로 풀어보기 - acmicpc.net/step 25단계까지 순서대로 풀어보기 solved.ac CLASS - solved.ac/class CLASS 3-4까지 풀어보기
20. 20. 어떤 알고리즘을 공부해야 할지 모르겠다면 solved.ac 태그 레이팅 앞서 언급한 ‘빈출 알고리즘’ 중 레이팅이 낮은 알고리즘 문제들 골라 풀어보기
21. 21. §3 문제 해결 연습 실전에서는 아무도 문제가 어떤 난이도와 알고리즘인지 알려주지 않는다 문제를 읽고 어떤 접근법을 적용할 수 있을지 떠올리는 시간을 줄이는 것을 목표로 합시다
22. 22. 백준을 이용하고 있다면 티어와 분류를 끕시다
23. 23. 랜덤 디펜스 수준에 맞는 아무 문제나 잡고 풀어봅시다 → solved.ac 검색: -@$me lang:ko solved:100.. *s5..g4 내 가 푼 문 제 를 제 외 하 고 한 국 어 문 제 들 중 에 1 0 0 명 이 상 이 해 결 한 문 제 들 중 에 실 버 5 에 서 골 드 4 난 이 도 의 문 제 들 만 → 백준 고급 검색 이용해 보기 → 프로그래머스에서 레벨 2 or 3만 필터 걸고 안 푼 문제 중 아무 문제나 풀어 보기
24. 24. 추천하는 타임라인 문 제 오 픈 + 2 0 분 + 4 0 분 + 6 0 분 + 8 0 분 말 그대로 추천하는 방법입니다! 각자에게 맞는 문제해결 방법을 찾아봅시다
25. 25. +20분 문 제 오 픈 + 2 0 분 + 4 0 분 + 6 0 분 + 8 0 분 푸는 방법을 대충이라도 알 것 같다 → 좋아요! 계속 생각해 봅시다 전혀 감이 안 잡힌다 → 알고리즘 분류를 확인해 봅시다 나중에... ✓ ✓ 알고 있는 알고리즘이었다면, 해당 분류의 문제들 더 풀면서 연습해 보기 모르는 알고리즘이었다면, 인터넷 블로그 등을 참조해 해당 알고리즘 기본 익히기
26. 26. +40분 문 제 오 픈 + 2 0 분 + 4 0 분 + 6 0 분 + 8 0 분 ✓ ✓ ✓ 문제를 잘못 읽음 문제를 침착하게 다시 읽어 봅시다 구현이 너무 복잡함 함수를 많이 써 가면서 코드를 깔끔하게 짜 봅시다 예외 케이스 미고려 n = 1인 경우라던가, 배열 인덱스를 초과하는 경우가 있는지 꼼꼼히 확인합시다 틀렸다: 틀렸거나 출력 초과, 런타임 에러, 간혹 시간 혹은 메모리 초과 → 어떤 상황에서 틀리는지 생각해 보고 틀리는 예제를 직접 만들어 봅시다 ✓ 시간 혹은 메모리 초과 무한 루프가 돈다거나, 큐나 스택 같은 자료구조에 원소가 무한히 많이 들어가지는 않는지 확인합시다 이런 경우 로컬에서 작은 데이터셋을 돌려도 시간 초과가 발생할 수 있다는 점에서 맞았지만 비효율적인 경우와는 다릅니다
27. 27. +40분 문 제 오 픈 + 2 0 분 + 4 0 분 + 6 0 분 + 8 0 분 틀렸을 리 없는데 비효율적이다: 시간 혹은 메모리 초과 → 알고 있는 다른 접근법을 생각해 봅시다 여전히 전혀 모르겠다 → 이 문제는 놓아주고, 다른 풀이들을 참고해 봅시다 나중에... ✓ ✓ 일주일 정도 후에 문제를 혼자 힘으로 다시 풀어보기 비슷한 분류의 문제들을 풀면서 연습하기 ‘이건 이렇게 풀면 되는구나’를 얻어가는 데 의미를 둡시다 뜻밖의 좋은 인사이트를 얻을 수도 있어요! 나중에... ✓ ✓ 혹시 까먹었다면, 첫 번째 접근법에서 사용한 알고리즘과 자료구조의 복잡도 숙지하기 언어 사용이 아직 미숙하다면, [<x> 언어 최적화 코테] 같은 걸 검색해서 적용해 보기
28. 28. +80분 문 제 오 픈 + 2 0 분 + 4 0 분 + 6 0 분 + 8 0 분 여전히 틀리거나 비효율적이다 → 다른 풀이들을 참고해 보거나 다른 접근법을 시도해 봅시다 나중에... ✓ ✓ ✓ 혹시 까먹었다면, 이전 접근법에서 사용한 알고리즘과 자료구조의 복잡도 숙지하기 풀이를 봤다면, 일주일 정도 후에 문제를 혼자 힘으로 다시 풀어보기 비슷한 분류의 문제들을 풀면서 연습하기
29. 29. 회고: 문제를 풀고 나서 문 제 오 픈 + 2 0 분 + 4 0 분 + 6 0 분 + 8 0 분 얻어갈 수 있으면 얻어갑시다: ✓ ✓ 이런 상황에서 이런 알고리즘/자료구조/테크닉을 쓰는구나 이런 상황에서 이렇게 하면 틀리는구나/비효율적이구나 블로그 글 쓰기 등의 방식으로 기록하기: 기록하는 게 즐거운 경우라면 시도해 봅시다 딱히 그렇지 않다면 기록하는 게 귀찮아서 문제를 안 풀게 될지도…
30. 30. 회고: 문제를 풀고 나서 문 제 오 픈 + 2 0 분 + 4 0 분 + 6 0 분 + 8 0 분 다른 사람들의 코드를 마구 참고합시다: ✓ ✓ 베끼는 것과 참고하는 것은 다릅니다 생각하지도 못한 인사이트를 얻을 수도 있습니다 ’백준 23721번’, ‘프로그래머스 레벨2 탑 풀이’과 같은 식으로 검색해 봅시다 백준을 쓰는 경우 ‘맞힌 사람’ 탭에서 공개된 코드들을 볼 수 있습니다: 언어 필터를 걸 수도 있어요
31. 31. §4 이걸 언제까지? solved.ac 어려운 실버 ~ 쉬운 골드 프로그래머스 레벨 3 무난하게 풀 수 있을 때까지* * 준비하는 기업에 따라 다를 수 있음
32. 32. 난이도 보는 방법 solved.ac 브론즈 실버 골드 플래티넘 프로그래머스* Lv. 1 Lv. 2 Lv. 3 Lv. 4 * 대략적인 비교임 SWEA(삼성)* D1~D3 D4~D5 D6+ LeetCode* Easy Medium Hard 참고 자료로만 활용해 주세요 Codeforces* *800 *1200 *1400 *1600 *1900 *2100
33. 33. 최근 코딩 테스트 난이도 경향 추측치 / 참고 자료로만 활용해 주세요 solved.ac B S G P 프로그래머스 (대략) 1 2 3 4 K사 1차(2021), 7문제 제일 쉬운 난이도 제일 어려운 난이도 합격을 가른 문제의 난이도 (추정) K사 1차(2022), 7문제 N사 기술직군(2021 상반기), 4문제* * 코딩 테스트 이외 서류에 의한 영향을 많이 받음 L사(2021 하반기), 6문제 S은행 ICT(2021), 4문제 + SQL 1문제 T사(2022), 3문제 C엔터 IT개발(2021), 2문제
34. 34. 최근 코딩 테스트 출제 분야 경향 추측치 / 참고 자료로만 활용해 주세요 K사 1차(2021) K사 1차(2022) N사 기술직군(2021 상반기) L사(2021 하반기) S은행 ICT(2021) T사(2022) C엔터 IT개발(2021) #구현 #시뮬레이션(=구현) #문자열 #브루트포스 #그래프 탐색 #정렬 #이분 탐색 #다익스트라 #투 포인터 #다이나믹 프로그래밍 #구현 #그래프 탐색 #백트래킹(=브루트포스) #집합과 맵 #트리(=그래프) #수학 #그리디 #비트마스크 #다이나믹 프로그래밍 #구현 #문자열 #그래프 탐색 #정렬 #슬라이딩 윈도우 #구현 #문자열 #파싱(=문자열) #브루트포스 #정렬 #집합과 맵 #재귀 #투 포인터 #구현 #문자열 #파싱(=문자열) #다이나믹 프로그래밍 #SQL #구현 #많은 조건 분기 #그리디 #구현 #문자열 #파싱(=문자열)
35. 35. 필요에 따라 SQL도 출제되는 추세* 프로그래머스와 LeetCode를 활용합시다 - programmers.co.kr/learn/challenges * 채용공고를 꼼꼼히 확인합시다
36. 36. §5 과제형 스크리닝 REST API? JSON 파서? K사 2차(2021)
37. 37. (프로세스에 있다면) 열심히 해야지 방법이 없습니다 보통 이직/경력직 면접이거나, 지원자에 대한 높은 스탠다드를 두는 회사들에서 협업 능력, 코딩 스타일, 도메인 지식 등 코딩 테스트로 물어볼 수 없는 것들을 물어보기 위해 등장합니다* 전공 지식* 도메인 지식 협업 능력 커뮤니케이션 능력 문제해결력 구현력 성장가능 * 역시 채용공고, 특히 채용 프로세스를 잘 확인합시다
38. 38. 능성 추천하는 공부 방향 개발 분야 정하기 → 개인/팀 프로젝트 해 보기 or 관련 강의 수강
39. 39. 웬만하면 알아두면 좋은 것들 Git - 버전 컨트롤 소프트웨어 (협업 툴) GitHub - Git 저장소 자신의 개발 분야도메인 에 대한 기본적인 지식 굳이 과제 준비가 아니더라도 써 본 적 있다고 하면 면접관들의 눈이 초롱초롱해질 만한 것들
40. 40. §6 여담 코딩 테스트 과몰입 금지! → → 코딩 테스트는 개발자 채용의 첫 허들일 뿐이고, 코딩 테스트에서 얼마나 잘하는가는 그 사람이 개발자로서 얼마나 훌륭한가를 말해주지는 않습니다 (반대로 알고리즘 공부가 어렵다고 너무 스트레스 받을 필요는 없습니다) solved.ac 티어와 레이팅은 기획 의도부터가 실력을 정확히 나타내기 위한 지표보다는 학습자의 동기 부여를 위함이었습니다
41. 41. §6 여담 문제 푸는 게 재밌어서 과몰입을 해버렸어요, 어떻게 하나요? → 프로그래밍 대회에 참가해 봅시다! Kick Start G사 채용연계형 대회 codingcompetitions.withgoogle.com/kickstart ICPC 국제 대학생 프로그래밍 경시대회 (3인 팀) icpckorea.org UCPC 전국 대학생 프로그래밍 대회 동아리 연합 (3인 팀) ucpc.me SCPC S리서치 대학생 프로그래밍 대회 research.samsung.com/scpc Codeforces ELO 레이팅이 있는 프로그래밍 대회 codeforces.com
42. 42. §6 여담 채용연계형 대회에서 좋은 성과를 내면 뜻밖의 인사를 받을 수 있을지도 모릅니다
43. 43. §6 여담 solved.ac는 코딩 테스트를 준비하는 분들과 알고리즘 문제해결을 사랑하는 모두가 더욱 더 재미있게 문제를 풀 수 있도록 고심하고 있습니다! 사이트를 이용하시면서 불편하신 점이나 추가하면 좋을 만한 기능이 있다면 언제든 부담없이 shift@solved.ac로 제안해 주세요!
44. 44. Q&A
45. 45. 감사합니다! 이 슬라이드의 저작권은 shiftpsh.com에 있습니다. 슬라이드를 허락 없이 외부에 공유하지 말아주세요.