본문 바로가기
728x90

자료구조 및 알고리즘6

스택, 큐(Queue)란? 컴퓨터 과학에서 중요한 자료 구조인 스택(Stack)과 큐(Queue)에 대하여 알아보겠습니다.1. 스택(Stack)이란?스택(Stack)이라는 단어에 대해서 먼저 살펴보겠습니다. 스택(Stack)은 깔끔하게 정돈된 무더기를 말합니다. 예를 들어"a stack of books"라고 하면 책 한 무더기라는 뜻입니다.위 그림에서 검은 책, 갈색 책, 흰 책 이외에 여러 책들이 쌓여 있는 모습을 볼 수 있습니다. 위 그림처럼 책을 쌓기 위해서는 검은 책, 갈색 책, 흰 책 순서로 책을 쌓아야 합니다. 하지만 책을 사용하려 한다면 위에서부터 한 권씩 꺼내야 하기에, 제일 먼저 쌓았던 검은 책이 가장 마지막에 꺼내집니다. 책 한 무더기에서 먼저 들어간 책이 나중에 나오는 것과 동일하게 작동하는 것이 스택(Stac.. 2024. 9. 20.
트리란? 1. 트리란?1-1. 예시로 살펴보기트리를 간단한 예시 상황으로 이해해 보겠습니다.할아버지, 할머니, 아들, 딸, 며느리, 사위, 손자, 손녀로 이루어진 집안의 가계도를 그림으로 나타내고자 합니다.가계도를 그릴 때는 일반적으로 세대별로 정리하여 그립니다.예를 들면, 할머니와 할아버지는 같은 세대로 묶을 수 있습니다.아들, 딸, 사위, 며느리 또한 같은 세대로 묶을 수 있습니다.손자와 손녀 또한 같이 묶을 수 있습니다.가계도에서 세대를 나누는 기준은 혈연관계나 결혼을 통해 연결된 인물들이 동일한 세대에 속하는지 여부에 따라 구분됩니다. 예를 들어, 형제자매는 부모 세대에 속한 인물들의 자녀이므로 동일한 세대에 묶이며, 그들의 자녀들은 한 단계 아래 세대인 손자 세대로 묶입니다. 이 방식은 가계도에서 세대 .. 2024. 9. 14.
복잡도(Complexity)란? - 시간 복잡도 1. 등장 배경1-1. 연산의 난이도컴퓨터와 관련된 문제는 다양한 형태로 발생합니다. 이는 간단할 때도 있고, 때론 복잡할 때도 있습니다.예를 들어, 정렬 문제(Sorting Problem)는 간단한 편에 속합니다. 나열된 숫자들을 오름차순으로 정렬하게 될 일이 생겼다고 가정하겠습니다. 그리고 이를 스케쥴링 문제(Scheduling problem)와 비교해봅시다. 예를 들어, 학교 전체 정원에 대하여 학교 규정과 학생의 요구 등이 포함된 제한 사항(Constraint)들이 적용된 반 편성 문제를 생각해봅시다. 이 두가지 문제를 비교해보니 스케쥴링 문제가 정렬 문제보다 보기에 훨씬 더 복잡해 보입니다. 학생의 수 또는 학교의 규모가 커질수록 이 스케쥴링 문제를 해결하는 난도는 기하급수적으로 증가합니다.여기.. 2024. 8. 24.
DFS란? 1. DFS 기본 개념DFS(Depth-First Search, 깊이 우선 탐색)은 그래프나 트리 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나로, 가장 깊은 노드까지 탐색한 후, 다시 돌아와서 다른 경로를 탐색하는 방식으로 작동합니다. DFS는 트리의 모든 노드를 방문하거나, 그래프의 모든 정점을 탐색할 때 사용됩니다. DFS는 다양한 문제 해결에 적용되며, 알고리즘 자체는 재귀(Recursive)적 구조나 스택(Stack) 자료구조를 통해 구현할 수 있습니다.백트래킹(Backtracking)의 원리를 응용하는 알고리즘이기에 백트래킹에 대해 먼저 공부하고 오면 이해하기 쉽습니다.백트래킹에 대한 설명글 링크는 하단에 남기겠습니다.https://woojin1354.tistory.com/40 백 트래킹(.. 2024. 8. 23.
백 트래킹(Backtracking)이란? 1. 백트래킹의 기본 개념백트래킹은 탐색 알고리즘 중 하나로, 주어진 문제를 해결하기 위해 모든 가능한 경우의 수를 체계적으로 시도해보는 방법입니다. 중요한 점은 필요하지 않거나 잘못된 경로를 빨리 알아차리고, 그 지점에서 돌아가(=백트래킹) 더 나은 경로를 탐색하는 방식이라는 점입니다.2. 일상생활 예시 - 퍼즐 맞추기생각해볼 수 있는 예로 퍼즐 조각 맞추기를 설명해보겠습니다.상황 설정퍼즐 조각들이 있는데, 이걸 다 맞춰서 하나의 큰 그림을 완성해야 합니다.또한, 조각들이 많아서 처음에는 어디에 어떤 조각이 맞는지 알기 어렵습니다.퍼즐 맞추기 과정첫 번째 시도퍼즐 조각 하나를 잡고, 이 조각이 어디에 맞을지 생각해봅시다. 여러 위치에 시도해볼 수 있죠. 처음엔 적당히 하나를 골라서 시도해봅니다.조각이 .. 2024. 8. 23.
맵(map)이란 ? 1. 맵(map)을 사용하는 이유컴퓨터 프로그램이 효율적으로 동작하기 위해서는, 많은 데이터 중에서 필요한 정보를 빠르게 찾아야 합니다. 예를 들어, 전화번호부에 수천 개의 이름과 번호가 있을 때, "홍길동"이라는 이름을 입력하면 그에 맞는 전화번호를 빠르게 찾을 수 있어야 합니다. 맵은 이런 작업을 매우 효율적으로 처리할 수 있습니다.1-1. 비효율적인 방법효율성을 이해하기 위해 예시 상황을 제시하겠습니다. 여러분들이 운영하는 웹사이트가 있을 때, 웹사이트의 이용자(User)들은 웹사이트의 기능에 접근하기 위해 로그인을 시도하게 됩니다. 이때 사용자는 로그인을 하기 위해 자신의 아이디(ID)와 비밀번호(Password)를 여러분에게 제출합니다. 이를 아이디-비밀번호 쌍(Pair)이라고 부르겠습니다. 이.. 2024. 8. 12.
728x90

티스토리툴바