본문 바로가기

728x90

Coding Test 코딩테스트13

Do it 알고리즘 코딩테스트 하루코딩 4장 정렬 이론 # 10 버블정렬 인접한 데이터끼리 크기 비교하여 swap 시간 복잡도 O(n^2) // 1번 루프당 1개 픽스 0과 1 비교하여 스왑, 1과 2를 비교하여 스왑, ... 맨뒤가 정렬된 영역 정렬된 영역을 제외하고 0과 1 비교하여 스왑, 1과 2를 비교하여 스왑, ... 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면, 모두 정렬되어 있다는 뜻이므로 더 이상 정렬 수행하지 않아도 된다. # 11 선택 정렬 정렬 해야 되는 범위에서 최솟값 또는 최댓값을 찾고, 남은 정렬 해야 되는 부분의 가장 앞에 있는 데이터와 swap 시간 복잡도 O(n^2) // 1번 루프당 1개 픽스 # 12 삽입 정렬 이미 정렬된 데이터의 범위에 정렬되지 않은 하나의 데이터를 적절한 위치에 삽입시켜 정렬 .. 2022. 11. 17.

Do it 알고리즘 코딩테스트 하루코딩 3장 자료구조 이론 Do it 알고리즘 코딩테스트 하루코딩 3장 자료구조 요약 # 5 배열과 리스트 java 배열 메모리에 연속적인 공간에 값을 저장하는 자료구조 특징 1. 인덱싱O, 접근속도 ↑ 2. 값 삽입, 삭제 번거로움, 속도 ↓, 주변 값 이동시키는 과정 필요 3. 크기 선언할 때 지정O, 크기 고정 4. 구조 간단 리스트 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 특징 1. 인덱싱X, 접근속도 ↓, Head 포인터부터 순서대로 접근하여 속도 느림 2. 값 삽입, 삭제 편리, 속도 ↑, 주변 값 이동시키는 과정 필요X 3. 크기 선언할때 지정X, 크기 가변 4. 구조 복잡 java에서는 ArrayList LinkedList 상황별 유리한 자료구조 배열: 크기고정, 값 접근 리스트: 크기가변, 삽입,.. 2022. 11. 16.

Do it 알고리즘 코딩테스트 하루코딩 2장 디버깅 이론 # 3 디버깅 java 가장 뛰어난 논리오류 탐색법 구문오류 논리오류 컴파일러 디버거 로그보다 디버깅이 더 나은 스킬 나무 숲 경계해야 하는 것 거기가 오류라고 지엽적으로 억측하지 않기 디버깅 하는 법 1. 중단점 break point 지정 2. IDE의 디버깅 기능 실행 3. 논리 오류 탐색 코딩테스트에서 하기 쉬운 오류 1. 변수 초기화 오류 2. 인덱스 오류 3. 잘못된 변수 사용 오류 4. 자료형 범위 오류 java 자바에서는 처음부터 int 말고 long형으로 선언 음수가 아니어야 하는데 왜 음수가 나오지? 또는 매우 큰 수 1. 팩토리얼 2. 경우의 수 3. 순열 4. DP # 4 디버깅 python 5. 자동 형변환 오류 python 파이썬에서는 / 나누기 연산자의 결과가 항상 float /.. 2022. 11. 16.

Do it 알고리즘 코딩테스트 하루코딩 1장 시간복잡도 이론 #1 시간 복잡도 java 알고리즘 선택의 기준이 되는 시간 복잡도 (by소거법) 시간복잡도 == 수행시간 == 연산횟수 자바 1초 == 1억번 시간복잡도 유형 1. 빅오메가: 최선(best case)일 때 연산 횟수, 즉 1 2. 빅세타: 보통(average case)일 때 연산 횟수, 즉 N/2 3. 빅오: 최악(worst case)일 때 연산 횟수, 즉 N 코딩테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까? 빅오 표기법 다양한 테스트 케이스를 수행해 모두 통과해야 하므로 데이터의 크기 증가에 따른 수행시간 증가율 O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n) O(n!) 연산횟수 계산방법 알고리즘의 시간복잡도에 데이터의 최대 크기 N 대입 ex) O(n^2.. 2022. 11. 12.

이전 1 2 다음

728x90

티스토리툴바