들어가며오늘은 알고리즘에 조금이라도 관심이 있고 코딩테스트를 준비하는 사람이라면누구나 알만한 주제인 BFS에 대해 알아볼 것이다BFS는 코딩테스트 단골 유형으로 출제되고 응용 문제도 많아서BFS 코드의 기본 틀은 어느정도 암기를 해야 문제푸는데에 수월할 것이다 BFS란BFS는 Breadth First Search의 약자로 너비 우선 탐색이라는 의미를 가진다주어진 속성을 만족하는 노드를 찾기 위해 트리를 탐색하는 알고리즘이다. 너비 우선 탐색이라는게 무슨말인지 의문을 가질 수 있다트리 구조에서 가로 방향을 너비라고하고 세로 방향을 깊이라고 한다너비 우선 탐색은 같은 깊이의 가로 방향의 노드들을 전부 다 탐색하고그 다음 깊이로 내려가 또 같은 깊이의 노드들을 탐색하는 방식이다 위의 사진을 예시로 들면1 ->..

스택?스택은 간단히 말해서 한 쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조이다구조적으로 먼저들어간 원소가 가장 마지막에 나오므로FILO(Fist In Last Out) 라고도 불린다 위 사진은 접시를 쌓아올린 것이다일상 속 스택으로 접시더미에서 접시의 추가나 제거가 맨 위에서만 가능해 스택이라고 볼 수 있다자료구조 상에서의 스택을 그림으로 표현하면 위와 같다 스택은 성질로는원소의 추가/제거가 O(1)이고제일 상단 원소 확인이 O(1)이다 STL stack으로 스택을 활용할 수 있다int main(void) { stack S; S.push(10); // 10 S.push(20); // 10 20 S.push(30); // 10 20 30 cout 스택이 비어있을 때 top(), pop()을 호..

연결리스트?원소들을 저장할 때 데이터와 그 다음 원소의 위치를 포함하여 저장하는 자료구조이다연결리스트는 실제 메모리 공간에서 아무런 규칙없이 저장되기에각 node가 다음 원소의 위치를 화살표로 연결시켰다고하면 이해하기 쉽다 각 노드가 두개로 분리되어있는 이유는데이터를 저장하는 변수와 다음 데이터를 가리키는 포인터 변수로 구성되어있기 때문이다 연결리스트의 성질만 우선 나열해보자면1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함2. 임의의 위치에 원소를 추가/제거는 O(1)가 필요함 배열과 비교하면1. k번째 원소를 확인/변경 위해 O(1) 필요함2. 임의의 위치에 원소를 추가/제거는 O(k)가 필요함 연결리스트는 2번 성질이 가장 큰 장점이고연결리스트를 사용하는 이유이다 하지만 인덱싱이 불가능하다는..