Coding Test/알고리즘 개념
[자료구조] 슬라이딩 윈도우
✔ 슬라이딩 윈도우 슬라이딩 윈도우란? 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하면서 문제를 해결하는 알고리즘 투 포인터 알고리즘과 매우 비슷하고 원리도 간단 시간 복잡도는 O(N) 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://inf.run/w9Tn
Coding Test/알고리즘 개념
자바를 사용한 코딩 테스트
Coding Test/알고리즘 개념
[자료구조] 투 포인터
✔ 투 포인터 투 포인터란? 2개의 포인터로 알고리즘의 시간 복잡도를 최적화하는 알고리즘 2개의 포인터를 문제에 주어진 조건에 맞게끔 잘 이동해서 값을 구함 시간 복잡도는 O(N) 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://inf.run/w9Tn
Coding Test/알고리즘 개념
[자료구조] 구간 합
✔ 구간 합 구간 합이란? 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 합 배열 없이 구간 합을 구할 경우, 시간 복잡도는 O(N) 합 배열을 사용할 경우, 시간 복잡도는 O(1) 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i - 1] + A[i] 합 배열 S를 만드는 공식 S[i] = S[i - 1] + A[i] 인덱스 0 1 2 3 4 배열 A 3 6 5 10 4 합 배열 S 3 9 (3 + 6) 14 (9 + 5) 24 (14 + 10) 28 (24 + 4) 구간 합을 구하는 공식 구현된 합 배열을 이용하면 한 번의 계산으로 구간 합을 쉽게 구할 수 있음 i에서 j까지의 구간 합 = S[j] - S[i - 1] 더보기 Do..
Coding Test/알고리즘 개념
[자료구조] 배열과 리스트
✔ 배열 배열이란? 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있음 배열의 특징 인덱스를 사용하여 값에 바로 접근할 수 있음 새로운 값을 삽입하거나 삭제할 때는 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하므로 어려움 배열의 크기는 선언할 때 지정하며, 한 번 선언하면 크기를 늘리거나 줄일 수 없음 구조가 간단하므로 코딩 테스트에서 많이 사용함 배열을 언제 사용할까? 데이터의 크기가 고정되어 있으며, 데이터의 접근이 많을 때 유리 ✔ 리스트 리스트란? 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 리스트의 특징 인덱스가 없어 값에 접근하려면 Head 포인터부터 순서대로 접근해야 하므로 속도가 ..
Coding Test/알고리즘 개념
[코딩 테스트 준비하기] 디버깅
✔ 코드의 논리 오류를 어떻게 잡을까? 가장 뛰어난 오류 탐색 방법은 디버깅 ✔ 디버깅은 왜 중요할까? 디버깅이란? 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정 디버깅은 코딩 테스트에 필요한 기술이고, 문제를 풀면서 반드시 해야 하는 과정 지엽적이며 오랜 시간이 걸리는 로그 대신 디버깅을 사용하자 ✔ 디버깅 활용 사례 살펴보기 오류 1. 변수 초기화 오류 찾아보기 변수 초기화를 어디에서 하는지 초기화 로직의 문제를 살펴보기 모든 변수가 정상적으로 초기화되고 있는지 디버깅을 이용해 확인 예) t가 2일 때, answer의 값이 0으로 초기화되지 않고 1번쩨 테스트 케이스에서 도출한 answer의 값이 남아있게 됨 → 초기화 로직에 문제가 있다는 것을 의미 오류 2. 반복문에서 인덱스 ..
Coding Test/알고리즘 개념
[코딩 테스트 준비하기] 시간 복잡도
✔ 알고리즘 선택의 기준이 되는 시간 복잡도 코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것 ✔ 시간 복잡도 표기법 알아보기 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측 시간 복잡도는 빅-오메가, 빅-세타, 빅-오로 정의 빅-오메가 : 최선일 때의 연산 횟수를 나타낸 표기법 빅-세타 : 보통(평균)일 때의 연산 횟수를 나타낸 표기법 빅-오 : 최악일 때의 연산 횟수를 나타낸 표기법 데이터의 크기가 커질수록, 시간 복잡도의 차이가 많이 발생 코딩 테스트에서는 다양한 테스트 케이스를 수행 모든 케이스를 통과해야 하므로 최악의 경우를 염두에 두고 빅-오 표기법을 기준으로 수행 시간..
