스택 예제: 미로찾기

스택스택은 데이터를 쌓는다. 그리고 가장 나중에 들어온 데이터를 먼저 처리한다. 당장 눈에 들어온 일부터 먼저 처리하는 느낌이다. 미로를 탐험하다보면 보고 있는 위치가 어떤 장소이냐에 따라 스택에 넣을 지 말지, 탐색을 할 지를 결정할 수 있다. 위치struct Pos { int row; int col; // 디버깅을 위한 편의 기능 friend ostream &operator 스택으로 미로찾기void StackMaze() { Stack s; Pos start = {1, 1}; // i = 1, j = 1 시작 지점 s.Push(start); while (!s.IsEmpty()) { Pos p = s.Top(); s.Pop(); ..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 8. 19.

[자료구조] Stack

자료구조를 사용하는 이유데이터는 구조화 된 여부에 따라 정형, 비정형으로 구분한다. 컴퓨터 시스템에서 데이터를 효율적으로 다루기 위해서는 데이터가 구조화되어야한다. 데이터를 효율적으로 저장하고 관리하기 위해 구조화 된 형태를 자료구조라고 한다. 배열, 스택, 큐 모두 자료구조이다. 자료구조마다 각기 다른 방식으로 데이터를 관리하고 처리한다. 스택개념스택은 후입선출원칙(LIFO)에 따라 데이터를 관리한다. 데이터를 넣는 순서와 반대로 데이터가 꺼내진다. 즉, 가장 마지막에 넣은 데이터가 가장 먼저 나오게 된다.스택에서 가장 마지막에 들어간 데이터의 위치를 top이라고 한다.스택은 push, pop, peek 연산이 있다. push 연산은 데이터를 넣는다. pop은 top에 있는 데이터를 제거한다. peek..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 8. 19.

알고리즘의 성능측정

성능측정을 해야하는 이유알고리즘이 창의적이거나 좋더라도 실행시간이 느리다면 사용하기가 어렵다. 따라서 알고리즘을 만들고 나면 성능을 측정해야한다.성능측정방법알고리즘의 성능을 분석하는 방법은 지표가 시간이냐, 공간이냐에 따라 달라진다. 시간복잡도알고리즘이 문제를 해결하는 데에 걸리는 시간을 시간복잡도라고 한다. 시간을 기준으로 알고리즘을 평가할 경우, 데이터의 크기에 따른 시간복잡도를 측정한다. 시간복잡도는 빅오표기법으로 표현한다.  공간복잡도알고리즘이 문제를 해결하는 데에 사용하는 메모리량을 공간복잡도라고 한다. 시간을 공간으로 알고리즘을 평가할 경우, 데이터의 크기에 따른 공간복잡도를 측정한다. 공간복잡도도 또한 빅오표기법으로 표현한다. 원본데이터를 기준으로 알고리즘이 문제를 해결하는데 필요한 추가적인..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 8. 11.

이진탐색

목적과 특징💡 조사범위를 절반씩 줄여가며 원하는 원소를 찾는 전략두개의 포인터(left, right)를 활용해 조사범위를 설정한다찾고자하는 원소와 middle 값의 크기를 비교해서 조사범위를 조정한다middle 값이 찾고자하는 원소보다 큰 경우, 왼쪽 조사를 위해 right의 인덱스를 내려서 갱신middle 값이 찾고자하는 원소보다 작은 경우, 오른쪽 조사를 위해 left의 인덱스를 올려서 갱신찾고하는 값이 있는 경우에 해당 원소의 인덱스를, 없으면 -1을 반환한다.구현코드C++int BinarySearch(int *arr, int n, int x) // 이진 탐색{ int left = 0; int right = n - 1; while (left x) { // REVIEW: 찾고자하는..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 8. 10.

선형탐색

정의💡 한쪽 끝에서 시작하여 원하는 요소를 찾을 때까지 목록의 각 요소를 조사하는 알고리즘요소를 찾지 못하는 경우에는 데이터셋의 끝까지 간다.효용배열, 연결리스트의 정렬여부와 무관하게 원소를 탐색할 수 있음그러나 배열이 정렬되어 있고 원소가 배열 내에 존재하는 경우에 탐색 성능이 올라감절차1. 시작: 컬렉션의 첫번째 원소에서부터 시작2. 비교: 현재의 원소와 찾고자하는 원소와 비교3. 확인: 현재 원소가 찾고자하는 원소인 경우 true 또는 현재 원소의 인덱스를 반환4. 이동: 찾고자 하는 원소가 아닌 경우에는 컬렉션의 다음 원소로 이동5. 반복: 컬렉션의 끝에 도달할 때까지 2에서 4의 과정을 반복6. 찾지 못한 경우: 컬렉션의 끝에 도달해도 원소를 찾을 수 없는 경우에는 찾을 수 없음 반환구현Hor..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 8. 7.

버블정렬

정의💡 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘버블 정렬은 다른 정렬과 다르게 모든 원소를 비교하는 것이 특징이다. 구현#include using namespace std;int main(){ int arr[] = {3,2,4,1,5}; int n = sizeof(arr) / sizeof(int); for(int i = 0; i arr[j+1]){ swap(arr[j], arr[j+1]); } } } for(int i = 0; i

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 8. 4.