자료구조&알고리즘

O(1)의 시간으로 k번쨰 원소를 확인/변경 가능추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음메모리가 연속해서 존재하기때문에 Cache hit memory가 높다.메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림임의의 위치에 원소를 추가, 삭

k번째 원소를 확인/변경하기 위해 O(K)가 필요함.임의의 위치에 원소를 추가/임의의 위치의 원소 제거는 O(1)원소들이 메모리 상에 연속해있지 안하 Cache hit rate가 낮지만 할당이 다소 쉬움||배열|연결리스트||K번째 원소에 접근|O(1)|O(K)||임의

한쪽 끝에서만 자료를 넣거나 뺄 수 있는 자료구조FILO(First-In-Last-Out) 형식을 갖는 자료구조원소의 추가가 O(1) 원소의 삭제 O(1)제일 상단의 원소의 확인 O(1)제일 상단이 아닌 원소들의 확인 및 변경은 \`불가능'pos를 인덱스로 둠으로써 스

큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조FIFO(First In First Out) 형식을 따른다.원소의 추가가 O(1)원소의 제거가 O(1)제일 앞/뒤 원소의 확인이 O(1)양 끝의 원소를 제외하고, 나머지 원소들의 확인/변경이 불가능

스택과 큐는 모두 덱의 일부라고 할 수 있다.덱에서는 양쪽 끝에서 삽입과 삭제 모두 가능하다.O(1) 시간에 양쪽끝에서 삽입 삭제가 가능하다.배열로 구현한 스택에서는 앞쪽에서만 삽입 삭제가 일어난다. 또한 배열로 구현한 큐에서는 앞쪽에서만 삭제, 뒤쪽에서만 삽입이 일어

BFS BFS란 Breadth First Search의 약자로 넓이 우선 탐색을 의미한다. 주로 다차원의 배열에서 각 칸을 방문하는 경우 사용하는 알고리즘이다. 큐 자료구조와 함께 사용한다. 동작 방식 우선 (0,0)의 점을 방문 표시를 한 뒤, 큐에 넣는다. 그 다

하나의 함수에서 자기자신을 다시 호출해 작업을 수행하는 알고리즘이다.절차지향적 사고보다는 귀납적 사고가 필요하다.공부하면서 느낀것이지만 재귀로 짜여진 코드를 보고 하나하나 분석하기 보다는, n=k 일때 n=k+1 도 정의가능하다는 마음가짐으로 코드를 짜보고 분석하는 것

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘으로, 대표적으로 오목 같은 경우 놓을 수 있는 모든 수에 대한 상태공간트리를 만들어 해결하는 것과 같은 알고리즘이다.func(int k) 함수는 arr\[k]에 들어갈 수를 결정하는 함수이다. 만약 k

재귀적 방법으로 원소를 반 씩 쪼개나가면서 정렬을 수행하는 방법.절반으로 쪼개진 배열의 크기가 1이 될때까지 반복한다.크기가 1로 이루어진 배열들을 하나씩 정렬해가며 다시 배열을 채워나가는 방식배열을 쪼개는 경우: 첫번째 줄에서는 1번의 쪼갬, 두번째 줄에서는 2번의

정렬하고자 하는 배열의 빈도수를 저장하는 배열을 통해 배열을 하는 방법.정렬하고자 하는 배열의 크기가 N이고, 수의 범위가 K라고 할 떄, 시간복잡도는 O(N+K) 이다. 수의 범위가 적을때는 매우 유리한 정렬방법이다.각 자리수를 기준으로 정렬하는 방법.처음 1의 자리