coding interview university
1.0.0
원래는 소프트웨어 엔지니어가 되기 위한 학습 주제에 대한 간단한 할 일 목록으로 이 목록을 만들었지만 오늘날 볼 수 있는 큰 목록으로 늘어났습니다. 이 학습 계획을 거친 후 저는 Amazon에서 소프트웨어 개발 엔지니어로 채용되었습니다! 아마 당신은 나만큼 공부하지 않아도 될 것입니다. 어쨌든 필요한 모든 것이 여기에 있습니다.
몇 달 동안 하루에 8~12시간씩 공부했어요. 이것이 내 이야기입니다. Google 인터뷰를 위해 8개월 동안 풀타임으로 공부한 이유
참고하세요: 당신은 나만큼 공부할 필요가 없습니다. 나는 알 필요도 없는 일에 많은 시간을 낭비했다. 이에 대한 자세한 정보는 아래에 있습니다. 소중한 시간을 낭비하지 않고 목적지에 도착할 수 있도록 도와드리겠습니다.
여기에 나열된 항목은 거대 기업인 Amazon, Facebook, Google 및 Microsoft를 포함한 거의 모든 소프트웨어 회사의 기술 인터뷰를 준비하는 데 도움이 됩니다.
행운을 빕니다!
인도네시아 바하사
불가리아 사람
스페인어
독일 사람
일본어(일본어)
마라티어
광택
포르투갈어 브라질레이로
러시아인
Tiếng Viet - 베트남어
우르두어 - اردو
우즈벡어
বাংলা - 방글라
ខ្មែរ - 크메르어
简体中文
繁체중국어
아프리카 어
아라비아 말
프랑스 국민
그리스 사람
이탈리아 사람
한국어(한국어)
말라얄람어
페르시아어 - 페르시아어
텔루구어
태국어
터키어
모스크바
히브리어
힌두교
후원자가 되어 코딩면접대학을 지원해보세요!
이것은 대기업의 소프트웨어 엔지니어가 되기 위한 나의 다개월 학습 계획입니다.
필수의:
코딩에 대한 약간의 경험(변수, 루프, 메소드/함수 등)
인내심
시간
이것은 프론트엔드 엔지니어링이나 풀스택 개발이 아닌 소프트웨어 엔지니어링을 위한 학습 계획입니다. 다른 곳에서도 이러한 진로에 대한 슈퍼 로드맵과 교과 과정이 있습니다(자세한 내용은 https://roadmap.sh/ 참조).
대학의 컴퓨터 과학 프로그램에서는 배울 것이 많지만 인터뷰를 위해서는 75% 정도만 아는 것만으로도 충분하므로 여기서는 그 내용을 다룹니다. 완전한 CS 독학 프로그램을 위해 Kamran Ahmed의 컴퓨터 과학 로드맵(https://roadmap.sh/computer-science)에 내 학습 계획을 위한 리소스가 포함되어 있습니다.
그것은 무엇입니까?
왜 그것을 사용합니까?
사용방법
당신이 충분히 똑똑하지 않다고 생각하지 마세요
비디오 리소스에 대한 참고 사항
프로그래밍 언어 선택
데이터 구조 및 알고리즘 관련 서적
인터뷰 준비 도서
내 실수를 저지르지 마세요
당신이 보지 못하는 것
일일 계획
코딩 질문 연습
코딩 문제
알고리즘 복잡도 / Big-O / 점근적 분석
데이터 구조
배열
연결리스트
스택
대기줄
해시 테이블
더 많은 지식
바이너리 검색
비트별 연산
나무
나무 - 소개
이진 검색 트리: BST
힙/우선순위 큐/바이너리 힙
균형 검색 트리(세부 사항이 아닌 일반적인 개념)
순회: 선주문, 중위, 후순, BFS, DFS
정렬
선택
삽입
힙 정렬
퀵소트
병합 정렬
그래프
감독
방향이 없는
인접 행렬
인접 목록
순회: BFS, DFS
더 많은 지식
재귀
동적 프로그래밍
디자인 패턴
조합론(n은 k 선택) 및 확률
NP, NP-완전 및 근사 알고리즘
컴퓨터가 프로그램을 처리하는 방법
캐시
프로세스와 스레드
테스트
문자열 검색 및 조작
시도
부동 소수점 숫자
유니코드
엔디안
네트워킹
최종 검토
이력서 업데이트
직업 찾기
면접과정 및 종합면접 준비
면접이 언제 올지 생각해 보세요
면접관에게 질문이 있습니다
일단 일자리를 구했다면
---------------- 이 지점 아래의 모든 항목은 선택사항입니다. ----------------
추가 도서
시스템 설계, 확장성, 데이터 처리(4년 이상의 경험이 있는 경우)
추가 학습
AVL 트리
나무를 펴다
빨간색/검은색 나무
2-3개의 검색 트리
2-3-4 트리(일명 2-4 트리)
N-ary(K-ary, M-ary) 트리
B-트리
컴파일러
Emacs와 vi(m)
Unix 명령줄 도구
정보 이론
패리티 및 해밍 코드
엔트로피
암호화
압축
컴퓨터 보안
쓰레기 수거
병렬 프로그래밍
메시징, 직렬화 및 대기열 시스템
에이*
고속 푸리에 변환
블룸 필터
하이퍼로그로그
지역 구분 해싱
반 엠데 보아스 나무
증강된 데이터 구조
균형 검색 트리
kD 트리
목록 건너뛰기
네트워크 흐름
서로소 집합 및 합집합 찾기
빠른 처리를 위한 수학
함정
선형 프로그래밍
기하학, 볼록 껍질
이산수학
일부 주제에 대한 추가 세부정보
비디오 시리즈
컴퓨터 과학 강좌
서류
대기업의 소프트웨어 엔지니어로 일하고 싶다면 꼭 알아야 할 사항은 다음과 같습니다.
나처럼 컴퓨터 과학 학위 취득을 놓쳤다면, 이 방법으로 당신의 인생을 4년 정도 절약할 수 있습니다.
이 프로젝트를 시작했을 때 나는 힙의 스택에 대해 전혀 몰랐고, Big-O에 대해서도 전혀 몰랐으며, 트리에 대해서도, 그래프를 탐색하는 방법에 대해서도 전혀 몰랐습니다. 정렬 알고리즘을 코딩해야 했다면 정말 끔찍했을 것입니다. 내가 사용한 모든 데이터 구조는 언어에 내장되어 있었고, 그 내부에서 어떻게 작동하는지 전혀 몰랐습니다. 내가 실행 중인 프로세스에서 "메모리 부족" 오류가 발생하지 않는 한 메모리를 관리할 필요가 없었으며 그런 다음 해결 방법을 찾아야 했습니다. 나는 내 인생에서 몇 가지 다차원 배열과 수천 개의 연관 배열을 사용했지만 처음부터 데이터 구조를 만든 적이 없습니다.
장기적인 계획이에요. 몇 달이 걸릴 수도 있습니다. 이미 이것에 대해 많이 알고 있다면 시간이 훨씬 덜 걸릴 것입니다.
⬆ 맨 위로 돌아가기
아래의 모든 내용은 대략적인 내용이므로 위에서 아래로 순서대로 항목을 다루어야 합니다.
저는 진행 상황을 추적하기 위한 작업 목록을 포함하여 GitHub의 특별한 마크다운 방식을 사용하고 있습니다.
GitHub 기반 마크다운에 대해 자세히 알아보기
이 페이지에서 상단 근처의 코드 버튼을 클릭한 다음 "ZIP 다운로드"를 클릭하세요. 파일의 압축을 풀면 텍스트 파일로 작업할 수 있습니다.
마크다운을 이해하는 코드 편집기를 열면 모든 형식이 깔끔하게 표시됩니다.
다음과 같은 항목을 확인할 수 있도록 새 브랜치를 생성하세요. 대괄호 안에 x를 넣으세요: [x]
Fork 버튼을 클릭하여 GitHub 저장소( https://github.com/jwasham/coding-interview-university 를 포크하십시오.
로컬 저장소에 복제합니다.
자식 클론 https://github.com/<YOUR_GITHUB_USERNAME>/coding-interview-university.gitcd 코딩-인터뷰-대학 git 원격 업스트림 추가 https://github.com/jwasham/coding-interview-university.git git 원격 set-url --push upstream DISABLE # 개인 진행 상황을 원래 저장소로 다시 푸시하지 않도록 합니다.
변경을 완료한 후 모든 상자에 X를 표시하십시오.
git commit -am "Marked personal Progress"git pull upstream main # 포크를 원래 저장소의 변경 사항으로 최신 상태로 유지 push # 포크에 푸시하기만 하면 됩니다.
⬆ 맨 위로 돌아가기
성공적인 소프트웨어 엔지니어는 똑똑하지만 많은 사람들은 자신이 충분히 똑똑하지 않다는 불안감을 갖고 있습니다.
다음 비디오는 이러한 불안감을 극복하는 데 도움이 될 수 있습니다.
천재 프로그래머의 신화
혼자가는 것은 위험합니다: 기술 분야에서 보이지 않는 괴물과 싸우기
⬆ 맨 위로 돌아가기
일부 비디오는 Coursera 또는 EdX 수업에 등록해야만 볼 수 있습니다. 이를 MOOC라고 합니다. 때로는 수업이 진행되지 않아 몇 달을 기다려야 하므로 접근이 불가능할 수도 있습니다.
온라인 강좌 리소스를 YouTube 동영상(바람직하게는 대학 강의)과 같이 무료로 항상 이용 가능한 공개 소스로 대체하여 특정 온라인 강좌가 진행 중일 때뿐만 아니라 언제든지 이러한 리소스를 공부할 수 있도록 하는 것이 좋을 것입니다.
⬆ 맨 위로 돌아가기
코딩 인터뷰를 위해 프로그래밍 언어를 선택해야 하지만, 컴퓨터 과학 개념을 공부하는 데 사용할 수 있는 언어도 찾아야 합니다.
바람직하게는 언어가 동일하므로 하나만 능숙하면 됩니다.
제가 학습 계획을 세울 때 대부분 C와 Python이라는 두 가지 언어를 사용했습니다.
C: 매우 낮은 수준입니다. 포인터와 메모리 할당/할당 해제를 처리할 수 있으므로 데이터 구조와 알고리즘을 뼈대로 느낄 수 있습니다. Python이나 Java와 같은 고급 언어에서는 이러한 기능이 숨겨져 있습니다. 일상적인 작업에서는 훌륭하지만 이러한 하위 수준 데이터 구조가 어떻게 구축되는지 배울 때 금속에 가까워지는 느낌이 좋습니다.
이 책은 짧은 책이지만 C 언어를 잘 다룰 수 있게 해 줄 것이며 조금만 연습하면 금방 익숙해질 것입니다. C를 이해하면 프로그램과 메모리가 작동하는 방식을 이해하는 데 도움이 됩니다.
책을 너무 깊게 읽을 필요는 없습니다(또는 끝까지 읽을 필요도 없습니다). C로 편안하게 읽고 쓸 수 있는 곳으로 가세요.
C는 어디에나 있습니다. 공부하는 동안 책, 강의, 비디오 등 어디에서나 예를 볼 수 있습니다.
C 프로그래밍 언어, 제2판
Python: 현대적이고 표현력이 뛰어납니다. 매우 유용하고 인터뷰에서 코드를 덜 작성할 수 있기 때문에 배웠습니다.
이것이 내가 선호하는 것입니다. 물론 당신이 좋아하는 일을 하세요.
필요하지 않을 수도 있지만, 새로운 언어를 배울 수 있는 사이트는 다음과 같습니다:
운동
코드워
해커어스
스케일러 주제(Java, C++)
Programiz PRO 커뮤니티 챌린지)
인터뷰의 코딩 부분을 수행하는 데 익숙한 언어를 사용할 수 있지만 대기업의 경우 다음이 확실한 선택입니다.
C++
자바
파이썬
이것을 사용할 수도 있지만 먼저 읽어보세요. 주의사항이 있을 수 있습니다:
자바스크립트
루비
인터뷰를 위한 언어 선택에 관해 제가 쓴 글은 다음과 같습니다: 코딩 인터뷰를 위한 언어 하나 선택. 이것은 내 게시물의 원본 기사입니다. 인터뷰를 위한 프로그래밍 언어 선택
당신은 언어에 매우 편안하고 지식이 있어야합니다.
선택 사항에 대해 자세히 알아보세요.
코딩 인터뷰에 적합한 언어를 선택하세요
여기에서 언어별 리소스를 확인하세요.
⬆ 맨 위로 돌아가기
이 책은 컴퓨터 과학의 기초를 형성할 것입니다.
당신이 편안하게 사용할 수 있는 언어로 하나만 선택하세요. 당신은 많은 독서와 코딩을 하게 될 것입니다.
C 알고리즘, 파트 1-5(번들), 3판
기초, 데이터 구조, 정렬, 검색 및 그래프 알고리즘
Python의 데이터 구조 및 알고리즘
작성자: Goodrich, Tamassia, Goldwasser
나는 이 책을 좋아했다. 그것은 모든 것 이상을 다루었습니다.
파이썬 코드
내 빛나는 책 보고서: https://startupnextdoor.com/book-report-data-structures-and-algorithms-in-python/
당신의 선택:
굿리치, 타마시아, 골드와서
Java의 데이터 구조 및 알고리즘
세지윅과 웨인:
알고리즘 I
알고리즘 II
알고리즘
책을 다루는 무료 Coursera 강좌(저자가 강의합니다!):
당신의 선택:
굿리치, 타마시아, 마운트
C++ 2판의 데이터 구조 및 알고리즘
세지윅과 웨인
C++ 알고리즘, 파트 1-4: 기초, 데이터 구조, 정렬, 검색
C++ 파트 5의 알고리즘: 그래프 알고리즘
⬆ 맨 위로 돌아가기
이런 것을 여러 개 구입할 필요는 없습니다. 솔직히 "코딩 인터뷰 크래킹"이면 충분할 것 같지만 더 연습하기 위해 더 많이 구입했습니다. 하지만 나는 항상 너무 많은 일을 합니다.
나는 이 두 가지를 모두 샀다. 그들은 나에게 많은 연습을 주었습니다.
공개된 프로그래밍 인터뷰: 인터뷰를 통해 나만의 방식으로 코딩하기, 4판
C++ 및 Java의 답변
이것은 코딩 인터뷰 크래킹을 위한 좋은 워밍업입니다.
너무 어렵지 않습니다. 대부분의 문제는 인터뷰에서 보는 것보다 쉬울 수 있습니다(내가 읽은 내용에 따르면).
코딩 인터뷰 크래킹, 6판
자바의 답변
하나를 선택하세요:
프로그래밍 인터뷰의 요소(C++ 버전)
Python 프로그래밍 인터뷰의 요소
프로그래밍 인터뷰의 요소(Java 버전) - 동반 프로젝트 - 책의 모든 문제에 대한 메소드 스텁 및 테스트 사례
⬆ 맨 위로 돌아가기
이 목록은 여러 달에 걸쳐 늘어나서 감당할 수 없을 정도로 늘어났습니다.
더 나은 경험을 하실 수 있도록 제가 저지른 몇 가지 실수가 있습니다. 그리고 몇 달의 시간을 절약할 수 있습니다.
나는 몇 시간 동안 비디오를 보고 많은 양의 메모를 했는데, 몇 달 후에는 기억하지 못하는 것이 많이 생겼습니다. 나는 복습할 수 있도록 3일 동안 내 노트를 검토하고 플래시카드를 만들었습니다. 나에게는 그 모든 지식이 필요하지 않았습니다.
내 실수를 저지르지 않도록 읽어주세요.
컴퓨터 과학 지식을 유지합니다.
문제를 해결하기 위해 저는 일반용과 코드형의 2가지 유형의 플래시카드를 추가할 수 있는 작은 플래시카드 사이트를 만들었습니다. 각 카드에는 서로 다른 형식이 있습니다. 모바일 우선 웹사이트를 만들었기 때문에 어디서든 휴대전화나 태블릿에서 리뷰를 작성할 수 있습니다.
무료로 직접 만들어보세요:
플래시카드 사이트 저장소
나는 플래시카드를 사용하는 것을 권장하지 않습니다. 너무 많고 대부분은 필요하지 않은 퀴즈입니다.
하지만 내 말을 듣고 싶지 않다면 여기로 가세요.
내 플래시 카드 데이터베이스(1200개 카드):
내 플래시 카드 데이터베이스(최대 1800개 카드):
저는 어셈블리 언어와 Python 퀴즈부터 기계 학습 및 통계에 이르기까지 모든 것을 다루는 카드를 가지고 있다는 것을 명심하세요. 요구되는 것보다 너무 많은 것입니다.
플래시카드에 대한 참고사항: 처음으로 답을 알고 있다는 것을 인식할 때, 답을 안다고 표시하지 마세요. 같은 카드를 보고 여러 번 정확하게 대답해야 카드를 실제로 알게 됩니다. 반복하면 그 지식이 뇌 속 더 깊이 자리잡게 될 것입니다.
내 플래시카드 사이트를 사용하는 대안은 나에게 여러 번 추천되었던 Anki입니다. 기억을 돕기 위해 반복 시스템을 사용합니다. 사용자 친화적이고 모든 플랫폼에서 사용할 수 있으며 클라우드 동기화 시스템이 있습니다. iOS에서는 25달러지만 다른 플랫폼에서는 무료입니다.
Anki 형식의 내 플래시카드 데이터베이스: https://ankiweb.net/shared/info/25173560 (@xiewenya에게 감사드립니다).
일부 학생들은 데크를 열고, 카드를 편집하고, 카드를 클릭하고, "스타일링" 라디오 버튼을 선택하고, "white-space: pre" 멤버를 추가하여 해결할 수 있는 공백 관련 서식 문제를 언급했습니다. 카드 클래스로.
이것은 매우 중요합니다.
데이터 구조와 알고리즘을 배우면서 코딩 인터뷰 질문을 시작해 보세요.
문제를 해결하려면 배운 내용을 적용해야 합니다. 그렇지 않으면 잊어버릴 것입니다. 제가 이런 실수를 했습니다.
예를 들어 연결된 목록과 같은 주제를 배우고 그 주제에 어느 정도 익숙해지면 다음과 같습니다.
코딩 인터뷰 책(또는 아래 나열된 코딩 문제 웹사이트) 중 하나를 엽니다.
연결리스트에 관해 2~3가지 질문을 해보세요.
다음 학습 주제로 넘어갑니다.
나중에 다시 돌아가서 2~3개의 연결 목록 문제를 더 풀어보세요.
당신이 배우는 각각의 새로운 주제에 대해 이렇게 하십시오.
이 모든 것을 배우는 동안 문제를 계속 풀어보세요. 학습 후가 아닙니다.
지식을 위해 고용되는 것이 아니라 지식을 적용하는 방법입니다.
이에 대한 많은 리소스가 아래에 나열되어 있습니다. 계속하세요.
귀중한 시간을 빼앗을 수 있는 방해 요소가 많이 있습니다. 집중과 집중이 어렵습니다. 가사가 없는 음악을 켜면 꽤 잘 집중할 수 있습니다.
⬆ 맨 위로 돌아가기
다음은 널리 사용되는 기술이지만 이 연구 계획의 일부는 아닙니다.
자바스크립트
HTML, CSS 및 기타 프런트엔드 기술
SQL
⬆ 맨 위로 돌아가기
이 강좌에서는 많은 주제를 다룹니다. 각각에는 며칠이 걸릴 수도 있고 일주일 이상이 걸릴 수도 있습니다. 일정에 따라 다릅니다.
매일 목록의 다음 주제를 선택하고 해당 주제에 대한 비디오를 시청한 다음 이 과정에서 선택한 언어로 해당 데이터 구조 또는 알고리즘의 구현을 작성하세요.
여기에서 내 코드를 볼 수 있습니다.
기음
C++
파이썬
모든 알고리즘을 외울 필요는 없습니다. 자신만의 구현을 작성할 수 있을 만큼 충분히 이해할 수 있어야 합니다.
⬆ 맨 위로 돌아가기
Why is this here? I'm not ready to interview.
그럼 돌아가서 이 글을 읽어보세요.
프로그래밍 문제 해결을 연습해야 하는 이유:
문제 인식 및 올바른 데이터 구조와 알고리즘이 적합한 위치
문제에 대한 요구 사항 수집
인터뷰에서처럼 문제를 해결하는 방법을 이야기합니다.
컴퓨터가 아닌 화이트보드나 종이에 코딩하기
솔루션의 시간 및 공간 복잡성 생각해내기(아래 Big-O 참조)
솔루션 테스트
인터뷰에는 체계적이고 의사소통적인 문제 해결을 위한 훌륭한 소개가 있습니다. 프로그래밍 인터뷰 책에서도 이런 내용을 얻을 수 있지만 저는 이것이 훌륭하다고 생각했습니다: 알고리즘 디자인 캔버스
컴퓨터가 아닌 화이트보드나 종이에 코드를 작성하세요. 일부 샘플 입력으로 테스트합니다. 그런 다음 이를 입력하고 컴퓨터에서 테스트해 보세요.
집에 화이트보드가 없다면 미술품 가게에서 큰 그림판을 사세요. 소파에 앉아서 연습해도 됩니다. 이것이 나의 "소파 화이트보드" 입니다. 크기 조절을 위해 사진에 펜을 추가했습니다. 펜을 사용하면 지울 수 있으면 좋겠다고 생각하게 될 것입니다. 빨리 지저분해집니다. 저는 연필과 지우개를 사용해요.
코딩 문제 연습은 프로그래밍 문제에 대한 답을 외우는 것이 아닙니다.
⬆ 맨 위로 돌아가기
여기에서 주요 코딩 인터뷰 책을 잊지 마세요.
문제 해결:
해결책을 찾는 방법
Topcoder 문제 설명을 분석하는 방법
코딩 인터뷰 질문 동영상:
IDeserve (88 동영상)
투샤르 로이(재생 목록 5개)
문제 해결 방법을 안내하는 Super
Nick White - LeetCode 솔루션(187 비디오)
솔루션과 코드에 대한 좋은 설명
짧은 시간에 여러 개를 시청할 수 있습니다.
FisherCoder - LeetCode 솔루션
도전/연습 장소:
Leet코드
내가 가장 좋아하는 코딩 문제 사이트. 아마 준비하게 될 1~2개월 동안 구독료를 지불할 가치가 있습니다.
코드 연습은 위의 Nick White 및 FisherCoder 비디오를 참조하십시오.
해커랭크
탑코더
코드포스
다정함
괴짜를 위한 괴짜
알고전문가
Google 엔지니어가 만든 이 리소스는 기술을 연마하는 데에도 훌륭한 리소스입니다.
프로젝트 오일러
매우 수학에 중점을 두고 있으며 코딩 인터뷰에는 적합하지 않습니다.
⬆ 맨 위로 돌아가기
자, 잡담은 그만하고 배워봅시다!
하지만 배우는 동안 위에서부터 코딩 문제를 해결하는 것을 잊지 마세요!
여기서는 구현할 것이 없습니다. 동영상을 시청하고 메모를 하면 됩니다! 이야!
여기에는 많은 비디오가 있습니다. 이해할 때까지 충분히 지켜보세요. 언제든지 돌아와서 검토할 수 있습니다.
그 뒤에 숨겨진 모든 수학을 이해하지 못한다면 걱정하지 마십시오.
Big-O 측면에서 알고리즘의 복잡성을 표현하는 방법을 이해하면 됩니다.
Harvard CS50 - 점근 표기법(비디오)
Big O 표기법(일반 빠른 튜토리얼)(비디오)
Big O 표기법(및 Omega 및 Theta) - 최고의 수학적 설명(비디오)
스키에나 (영상)
UC 버클리 빅오(영상)
상각 분석(영상)
TopCoder(반복 관계 및 마스터 정리 포함):
계산 복잡성: 섹션 1
계산 복잡성: 섹션 2
치트 시트
[리뷰] 18분 만에 알고리즘(재생목록) 분석하기(영상)
글쎄요, 이 정도면 충분합니다.
"Cracking the Coding Interview"를 진행하면 이에 대한 장이 있고 마지막에는 다양한 알고리즘의 런타임 복잡성을 식별할 수 있는지 확인하는 퀴즈가 있습니다. 슈퍼 리뷰와 테스트입니다.
⬆ 맨 위로 돌아가기
메모리에서 연속적이므로 근접성은 성능에 도움이 됩니다.
필요한 공간 = (배열 용량, >= n) * 항목 크기, 그러나 2n이더라도 여전히 O(n)
O(1) 끝(추가 공간 할당을 위해 분할 상환), 인덱스 또는 업데이트 시 추가/제거
O(n) 다른 곳에 삽입/제거
배열과 포인터를 사용하여 코딩을 연습하고 인덱싱을 사용하는 대신 인덱스로 이동하는 포인터 수학을 연습하세요.
메모리가 할당된 새로운 원시 데이터 배열
size() - 항목 수
용량() - 담을 수 있는 항목 수
is_empty()
at(index) - 주어진 인덱스에 있는 항목을 반환하고 인덱스가 범위를 벗어나면 폭발합니다.
푸시(아이템)
insert(index, item) - 인덱스에 항목을 삽입하고 해당 인덱스의 값과 후행 요소를 오른쪽으로 이동합니다.
prepend(item) - 인덱스 0에서 위의 삽입을 사용할 수 있습니다.
pop() - 끝에서 제거, 값 반환
delete(index) - 인덱스에서 항목을 삭제하고 모든 후행 요소를 왼쪽으로 이동합니다.
제거(항목) - 값을 찾고 해당 값이 포함된 인덱스를 제거합니다(여러 위치에 있는 경우에도).
find(item) - 값을 찾고 해당 값이 있는 첫 번째 인덱스를 반환합니다. 값이 없으면 -1을 반환합니다.
resize(new_capacity) // 비공개 함수
내부적으로 int 배열을 할당할 수 있지만 해당 기능을 사용하지 마세요.
16으로 시작하거나 시작 숫자가 더 큰 경우 2 - 16, 32, 64, 128의 거듭제곱을 사용합니다.
용량에 도달하면 크기를 두 배로 조정합니다.
아이템 팝시 크기가 용량의 1/4이면 절반으로 조정
어레이 CS50 하버드 대학교
어레이(비디오)
UC Berkeley CS61B - 선형 및 다중 차원 어레이(비디오)(15분 32초부터 시청 시작)
동적 배열(비디오)
가변 배열(비디오)
배열 정보:
벡터(자동 크기 조정이 가능한 가변 배열)를 구현합니다.
시간
공간
설명(영상)
구현할 필요가 없습니다
size() - 목록의 데이터 요소 수를 반환합니다.
비어 있음() - 비어 있으면 bool이 true를 반환합니다.
value_at(index) - n번째 항목의 값을 반환합니다(처음에는 0부터 시작).
push_front(value) - 목록 맨 앞에 항목을 추가합니다.
pop_front() - 앞 항목을 제거하고 해당 값을 반환합니다.
push_back(value) - 끝에 항목을 추가합니다.
pop_back() - 최종 품목을 제거하고 해당 값을 반환합니다.
front() - 앞 항목의 값을 가져옵니다.
back() - 최종 품목의 값을 가져옵니다.
insert(index, value) - 인덱스에 값을 삽입하여 해당 인덱스의 현재 항목이 인덱스의 새 항목을 가리킵니다.
erasure(index) - 주어진 인덱스에서 노드를 제거합니다.
value_n_from_end(n) - 목록 끝에서 n번째 위치에 있는 노드의 값을 반환합니다.
reverse() - 목록을 반대로 바꿉니다.
Remove_value(value) - 목록에서 이 값을 가진 첫 번째 항목을 제거합니다.
포인터에 대한 포인터
핵심 연결 목록과 배열(영상)
실제 연결 목록과 배열 비교(영상)
연결 목록 CS50 Harvard University - 직관력을 키워줍니다.
단일 연결 목록(영상)
CS 61B - 연결된 목록 1(비디오)
CS 61B - 연결 목록 2(비디오)
[리뷰] 4분 안에 연결되는 목록(동영상)
설명:
C 코드(동영상) - 전체 동영상이 아닌 노드 구조 및 메모리 할당에 대한 부분만 설명합니다.
연결 목록과 배열:
연결 목록을 피해야 하는 이유(동영상)
알았어: 포인터에 대한 지식이 필요하다: (포인터가 가리키는 주소를 변경할 수 있는 함수에 포인터를 전달할 때) 이 페이지는 ptr에서 ptr로의 이해를 돕기 위한 것입니다. 나는 이 목록 순회 스타일을 권장하지 않습니다. 영리함으로 인해 가독성과 유지 관리성이 저하됩니다.
구현(테일 포인터를 사용하거나 사용하지 않고 수행함):
이중 연결 목록
스택(비디오)
[리뷰] 3분만에 쌓인다 (영상)
구현하지 않습니다. 배열로 구현하는 것은 간단합니다.
머리 부분에 대기열을 추가하고 꼬리 부분에서 대기열을 제거하는 연결된 목록을 사용하는 잘못된 구현은 O(n)이 될 것입니다. 왜냐하면 마지막 요소 옆에 다음 요소가 필요하기 때문에 각 대기열 제거의 전체 순회가 발생하기 때문입니다.
대기열에 넣기: O(1) (상각, 연결 목록 및 배열 [탐색])
대기열 제거: O(1) (연결된 목록 및 배열)
비어 있음: O(1) (연결된 목록 및 배열)
enqueue(value) - 사용 가능한 저장소 끝에 항목을 추가합니다.
dequeue() - 값을 반환하고 가장 최근에 추가된 요소를 제거합니다.
비어 있는()
가득한()
enqueue(value) - 꼬리 부분에 값을 추가합니다.
dequeue() - 값을 반환하고 가장 최근에 추가된 요소를 제거합니다(앞)
비어 있는()
대기열(비디오)
원형 버퍼/FIFO
[리뷰] 3분 만에 대기열 만들기(영상)
꼬리 포인터와 함께 연결된 목록을 사용하여 구현합니다.
고정 크기 배열을 사용하여 구현합니다.
비용:
hash(k, m) - m은 해시 테이블의 크기입니다.
add(key, value) - 키가 이미 존재하는 경우 값을 업데이트합니다.
존재합니다(키)
get(키)
제거(키)
핵심 해시 테이블(영상)
데이터 구조(영상)
전화번호부 문제(영상)
분산 해시 테이블:
Dropbox의 즉시 업로드 및 저장 공간 최적화(동영상)
분산 해시 테이블(비디오)
체이닝을 사용한 해싱(비디오)
테이블 더블링, Karp-Rabin(비디오)
개방형 주소 지정, 암호화 해싱(영상)
PyCon 2010: 강력한 사전(영상)
PyCon 2017: 더욱 강력한 사전(영상)
(고급) 무작위화: 범용 및 완전 해싱(비디오)
(고급) 완벽한 해싱(동영상)
[리뷰] 4분 만에 해쉬 테이블 만들기 (동영상)
비디오:
온라인 강좌:
선형 프로빙을 사용하여 배열로 구현
⬆ 맨 위로 돌아가기
이진 검색(정렬된 정수 배열)
재귀를 이용한 이진 검색
이진 검색(비디오)
이진 검색(비디오)
세부 사항
청사진
[리뷰] 4분 안에 이진 검색(영상)
구현하다:
절대 정수
교환
바이트의 비트 수를 계산하는 4가지 방법(비디오)
비트 카운트
32비트 정수에서 설정 비트 수를 계산하는 방법
이진법: 플러스와 마이너스(2의 보수를 사용하는 이유) (비디오)
1초 보수
2초 보수
단어
좋은 소개: 비트 조작(비디오)
C 프로그래밍 튜토리얼 2-10: 비트 연산자(비디오)
비트 조작
비트별 연산
바이틱스
비트 트위들러
비트 트위들러 인터랙티브
비트 해킹(영상)
실무 운영
(2^1에서 2^16 및 2^32)까지 2의 거듭제곱 중 많은 것을 알아야 합니다.
비트 치트 시트
&, |, ^, ~, >>, <<를 사용하여 비트 조작에 대해 잘 이해하십시오.
2s 및 1s 보수
세트 비트 카운트
스왑 값:
절대값:
⬆ 맨 위로 돌아가기
BFS 참고사항:
DFS 참고사항:
레벨 순서(BFS, 큐 사용)
시간 복잡도: O(n)
공간 복잡도: 최고: O(1), 최악: O(n/2)=O(n)
시간 복잡도: O(n)
공간 복잡도: 최고: O(log n) - 평균 최악의 트리 높이: O(n)
중위(DFS: 왼쪽, 자체, 오른쪽)
후위(DFS: 왼쪽, 오른쪽, 자체)
선주문(DFS: 셀프, 왼쪽, 오른쪽)
나무 소개(영상)
트리 순회(영상)
BFS(폭 우선 탐색) 및 DFS(깊이 우선 탐색)(동영상)
[리뷰] 4분 만에 찾은 너비우선탐색(동영상)
[리뷰] 4분 안에 깊이 우선 탐색 (동영상)
[리뷰] 11분 만에 보는 트리 순회(재생 목록)(영상)
insert // 트리에 값을 삽입합니다.
get_node_count // 저장된 값의 개수를 가져옵니다.
print_values // 최소부터 최대까지 트리의 값을 인쇄합니다.
삭제_트리
is_in_tree // 주어진 값이 트리에 존재하면 true를 반환합니다.
get_height // 노드의 높이를 반환합니다(단일 노드의 높이는 1입니다).
get_min // 트리에 저장된 최소값을 반환합니다.
get_max // 트리에 저장된 최대값을 반환합니다.
is_binary_search_tree
삭제_값
get_successor // 주어진 값 다음으로 트리에서 가장 높은 값을 반환합니다. 값이 없으면 -1을 반환합니다.
이진 검색 트리 - C/C++ 구현(비디오)
BST 구현 - 스택 및 힙의 메모리 할당(비디오)
이진 검색 트리에서 최소 및 최대 요소 찾기(비디오)
이진 트리의 높이 찾기(비디오)
이진 트리 순회 - 너비 우선 및 깊이 우선 전략(비디오)
이진 트리: 레벨 순서 탐색(비디오)
이진 트리 순회: 선주문, 중위, 후순(비디오)
이진 트리가 이진 검색 트리인지 확인하세요(비디오)
이진 검색 트리에서 노드 삭제(비디오)
이진 검색 트리의 중위 후속자(비디오)
이진 검색 트리 검토(영상)
소개(영상)
MIT (영상)
C/C++:
구현하다:
끼워 넣다
sift_up - 삽입에 필요함
get_max - 제거하지 않고 최대 항목을 반환합니다.
get_size() - 저장된 요소 수를 반환합니다.
is_empty() - 힙에 요소가 없으면 true를 반환합니다.
extract_max - 최대 항목을 반환하고 제거합니다.
sift_down - extract_max에 필요함
제거(x) - 인덱스 x에서 항목을 제거합니다.
heapify - heap_sort에 필요한 요소 배열에서 힙을 만듭니다.
heap_sort() - 정렬되지 않은 배열을 가져와서 최대 힙 또는 최소 힙을 사용하여 정렬된 배열로 바꿉니다.
트리로 시각화되지만 일반적으로 저장 공간(배열, 연결 목록)에서는 선형입니다.
더미
소개(영상)
이진 트리(비디오)
나무 높이 비고 (영상)
기본 조작(동영상)
완전한 이진 트리(비디오)
의사코드(영상)
힙 정렬 - 시작으로 이동(비디오)
힙 정렬(비디오)
힙 만들기(비디오)
MIT 6.006 알고리즘 소개: 바이너리 힙
CS 61B 강의 24: 우선순위 대기열(비디오)
선형 시간 BuildHeap(최대 힙)
[리뷰] 13분만에 힙(재생목록)(영상)
최대 힙을 구현합니다.
⬆ 맨 위로 돌아가기
참고:
연결된 목록을 정렬하는 것은 권장하지 않지만 병합 정렬은 가능합니다.
연결 목록의 병합 정렬
정렬 알고리즘 안정성
정렬 알고리즘의 안정성
정렬 알고리즘의 안정성
정렬 알고리즘 - 안정성
버블 정렬 없음 - 끔찍함 - O(n^2), n <= 16인 경우 제외
정렬을 구현하고 최상의 경우/최악의 경우, 각각의 평균 복잡성을 파악합니다.
정렬 알고리즘의 안정성("Quicksort는 안정적인가요?")
연결된 목록에는 어떤 알고리즘을 사용할 수 있나요? 배열 중 어느 것입니까? 둘 중 어느 것인가요?
힙 정렬에 대해서는 위의 힙 데이터 구조를 참조하세요. 힙 정렬은 훌륭하지만 안정적이지는 않습니다.
Sedgewick - Mergesort (5 비디오)
1. 병합정렬
2. 상향식 병합 정렬
3. 정렬 복잡성
4. 비교기
5. 안정성
Sedgewick - Quicksort (영상 4개)
1. 퀵소트
2. 선정
3. 중복 키
4. 시스템 정렬
UC 버클리:
CS 61B 강의 29: 정렬 I(비디오)
CS 61B 강의 30: 정렬 II(비디오)
CS 61B 강의 32: 정렬 III(비디오)
CS 61B 강의 33: V 정렬(비디오)
CS 61B 2014-04-21: 기수 정렬(영상)
버블정렬(영상)
버블 정렬 분석(영상)
삽입 정렬, 병합 정렬(영상)
삽입 정렬(영상)
병합 정렬(영상)
퀵소트(비디오)
선택 정렬(영상)
병합 정렬 코드:
출력 배열 사용(C)
출력 배열 사용(Python)
내부(C++)
빠른 정렬 코드:
구현(C)
구현(C)
구현(파이썬)
[리뷰] 18분만에 (재생목록)정렬
4분 만에 빠른 정렬(동영상)
4분 만에 힙 정렬(동영상)
3분 만에 병합 정렬(동영상)
2분 안에 버블 정렬(동영상)
3분 만에 선택 정렬(동영상)
2분 만에 삽입 정렬(동영상)
구현하다:
병합 정렬: O(n log n) 평균 및 최악
