알고리즘/개념4 [알고리즘] 스택과 큐 [ Do it! 알고리즘 코딩테스트 with JAVA ] 강의를 듣고 정리한 글 입니다. 스택(stack)____________스택은 삽입과 삭제 연산이 후입 선출로 이뤄지는 자료구조 이다,(Last-In-First-Out) 후입 선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징을 가진다. 새 값이 스택에 들어가면 top이 새 값을 가리키고 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 된다. 용어위치- top : 삽입과 삭제가 일어나는 위치연산- push : top 위치에 새로운 데이터를 삽입하는 연산- pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산- peek : top 위치에 있는 데이터를 단순 .. 2024. 7. 30. [알고리즘] 구간 합 [ Do it! 알고리즘 코딩테스트 with JAVA ] 강의를 듣고 정리한 글 입니다. 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다. 구간합 알고리즘을 활용하려면 우선 합 배열을 구해야 한다. 배열 A가 있을 때, 합 배열 S는 다음과 같이 정의한다.S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0] 부터 A[i] 까지의 합 합 배열은 기존의 배열을 전처리한 배열이라고 생각하면 된다. 합 배열을 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) 에서 O(1) 로 감소한다. 배열 A : 15 13 10 7 3 12합 배열 S : 15 28 38 45 48 600123.. 2024. 7. 22. [알고리즘] 배열과 리스트 [ Do it! 알고리즘 코딩테스트 with JAVA ] 강의를 듣고 정리한 글 입니다. ____________________________________________________________________________1.배열배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이다. - 연속된 메모리 공간에 존재하여 관리가 수월하다. 인덱스를 통하여 값에 바로 접근할 수 있다. - 자료구조의 크기가 클 수록 유리 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. - 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하기 때문 구조가 간단하여 코딩테스트에서 많이 사용한다. 시간 복잡도 삽입 / 삭제- 배열의 맨 앞 삽입 / 삭제 : O(n)-.. 2024. 7. 22. [알고리즘] 시간복잡도 [ Do it! 알고리즘 코딩 테스트 자바 ] 강의를 듣고 정리한 글 입니다. 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산횟수를 말한다.일반적으로 수행 시간을 1억번의 연산을 1초의 시간으로 간주하여 예측한다. 예를 들어 시간 제한이 2초인 문제라면,2억번의 연산 안에 답이 나오도록 설계를 해야 한다. 시간 복잡도 유형 n = 데이터의 수 1. 빅-오메가 ( Ω(n) ) : 최선일때 (best case) 의 연산 횟수를 나타낸 표기법 2. 빅-세타 ( Θ(n) ): 보통일 때 (average case) 의 연산 횟수를 나타낸 표기법 (N/2) 3. 빅-오 ( O(n) ): 최악일 때 (worst case) 의 연산 횟수를 나타낸 표기법 public class timeComp.. 2024. 7. 20. 이전 1 다음
