- [ 공부/알고리즘 ][자료구조] 스택과 큐2023-12-22 09:17:50스택 삽입과 삭제 연산이 후입선출LIFO로 이뤄지는 자료구조 삽입과 삭제가 한 쪽에서만 일어난다. 새 값이 스택에 들어가면 top이 새 값을 가리킨다. 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게된다. 깊이 우선 탐색(DFS), 백트래킹 종류의 알고리즘에서 효과적, 후입선출은 재귀함수 알고리즘 원리와 일맥상통하기 때문 스택 용어 top : 삽입과 삭제가 일어나는 위치 push : top 위치에 새로운 데이터를 삽입하는 연산 pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peak : top 위치에 현재 있는 데이터를 단순 확인하는 연산 큐 삽입과 삭제 연산이 선입선출FIFO로 이뤄지는 자료구조 삽입과 삭제가 양방향에서 일어난다. 너비 우선 탐색(BFS)에서 자주 사용 ..
- [ 공부/알고리즘 ][알고리즘] 구간 합2023-12-21 09:37:58합 배열 기존 배열을 전처리한 배열로 합배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(1)로 감소 합배열 s의 정의 s[i] = a[0] + a[1] + ... + a[i] a[i]~a[j]까지 배열 합을 합 배열 없이 구하는 경우 최악의 경우 시간 복잡도가 O(N) 합 배열을 사용하면 O(1)안에 답을 구할 수 있다. 합 배열을 만드는 공식 S[i] = S[i-1] + A[i] 구간 합 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 구간 합 알고리즘을 활용하기 위해선 합 배열을 우선 구해야 한다. 구간 합을 구하는 공식 S[j] - S[i-1] 관련 문제 보기 백준 11659번 구간 합 구하기 4
- [ 공부/알고리즘 ][자료구조] 배열과 리스트2023-12-20 09:48:08배열과 리스트 배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 인덱스 값을 통해 참조할 수 있고 선언한 자료형의 값만 저장 가능 인덱스를 사용하여 값에 바로 접근할 수 있다. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다. 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 구조가 간단하다. 리스트 노드*를 포인터로 연결한 자료구조 ArrayList, LinkedList, Stack, Vactor 등 *노드 : 값과 포인터를 묶은 것 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. 값에 접근하는 속도가 느리다. 포인터로..
- [ 공부/알고리즘 ][알고리즘] 복잡도2023-12-19 20:14:44복잡도 알고리즘의 성능을 나타내는 척도 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘 공간 복잡도 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 시간 복잡도 시간 복잡도란 문제를 해결하는데 걸리는 시간과 입력의 함수 관계이다. 알고리즘의 시간 복잡도는 주로 빅-오 표기법을 사용하며 빅-오표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 간단하게 표현하자면 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석한 것 빅 오메가 : 최선일 때 빅 세타 : 보통일 때 빅 오 : 최악일 때 # 100 미만의 랜덤 숫자 n이 있고, n을 구하기 위해 100번 반복하는 반복문을 작성한 경우 빅 오메가 → n이 0인 경우이므로 1 빅 세타 → 평균치이므로 n/..