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