자료구조 & 알고리즘

시간 복잡도(time complexity):알고리즘의 성능을 나타내는 지표입력 크기에 대한 연산 횟수의 상한을 의미낮으면 낮을 수록 좋음 ⏬예를 들어 어떤 문제를 해결하는 알고리즘 A,B,C가 있을 때, 시간 복잡도가 가장 낮은 알고리즘이 A라면 A를 사용하는 게 좋다

빅오 표기법에 대한 내용은 전 게시물에 작성해두었다. 참고하자!https://velog.io/@chanmi125/알고리즘-시간복잡도와-빅오-Big-O-표기법빅오 표기법의 성능 순서는 다음과 같이 나타낼 수 있다.가장 왼쪽 O(1)으로 갈수록 실행 횟수가 적은

지금까지 시간 복잡도와 빅오 표기법(Big O)에 대해 배워보았다. 이제 간단한 파이썬 코드 문제를 통해 그동안 배운 것들을 잘 기억하고 있는지 테스트해 보자!아래에 각 문제에 대한 정답과 코드 예제를 함께 정리해 두었다.해설: 이 함수는 리스트 lst의 첫 번째 요소

배열(Array)은 인덱스와 값을 일대일 대응해 관리하는 자료구조이다. 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있다.배열 요소(element): 배열을 구성하는 각각의 값인덱스(index): 배열에

스택stack의 어원은 ‘쌓는다’이다. 스택은 어원에서 짐작할 수 있듯이 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다. 선입후출 (FILO, First In Last Out): 가장 먼저 입력된 데이터가 가장 마지막에 출력되는 구조이다.예시: 티슈 사용

연결 리스트란? 연결 리스트(linked list): 각 노드(Node)가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드

큐queue는 '줄을 서다' 라는 뜻을 가지고 있다. 큐는 먼저 들어간 데이터가 먼저 나오는 자료구조이다. 맛집에서 줄을 선 순서대로 식당에 입장할 때를 생각하면 된다.이런 큐의 특징을 선입선출 또는 FIFO(first in first out)이라고 한다. 스택과 마찬

해시는 해시 함수를 사용해 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다. 보통은 인덱스를 활용해서 탐색을 빠르게 만들지만 해시는 키(key)를 활용해 데이터 탐색을 빠르게 한다.해시는 키와 데이터를 일대일 대응하여 저장하므로

앞서 자주 언급했던 것처럼 서로 다른 키에 대해서 해시 함수의 결괏값이 같으면 충돌Collision이라고 한다. 하나의 버킷에 2개의 값을 넣을 수는 없으므로 해시 테이블을 관리할 때는 반드시 충돌 처리를 해야 한다.그림을 보면 두 키는 서로 다르지만 해시 함수를 적용

트리tree는 자료구조에서 중요한 개념 중 하나로, 데이터를 저장하고 탐색하기에 유용한 구조를 갖고 있다.트리Tree는 계층적 구조를 나타내는 비선형 자료구조로, 그래프Graph의 일종이다. 하나의 노드에서 시작하여 그 노드를 중심으로 여러 개의 자식 노드들이 연결된

🌌 집합이란? 집합(Set)은 순서와 중복이 없는 원소들을 갖는 자료구조를 말한다. 예를 들어 어떤 A라는 그룹의 원소 구성이 {1,6,6,6,4,3}이면 이는 중복을 제외해 {1,6,4,3}으로 생각해야 한다. 순서는 따로 따지지 않으니 {6,1,3,4}와 같이

그래프는 노드vertex와 간선edge을 이용한 비선형 데이터 구조이다. 보통 그래프는 데이터 간 관계를 표현하는 데 사용한다.노드 - 데이터간선 - 노드 간 관계나 흐름여기서 간선은 방향이 있을 수도 있고 없을 수도 있다. 만약에 관계나 흐름에서 정도를 표현할 필요가

그래프 탐색 알고리즘(Graph Search Algorithm):그래프 구조에서 노드와 간선을 탐색하는 알고리즘을 말한다. 자료구조에서 데이터를 어떻게 구축할지 고민한다면, 알고리즘에서는 어떤 순서와 방식으로 탐색할지를 고민한다.그래프 탐색 알고리즘은 크게 두 가지로

최단 경로shortest path는 그래프 내의 두 노드 사이의 최단 경로를 찾는 데 사용되는 알고리즘이다. 주로 다음과 같은 두 가지 유형의 그래프에서 적용된다.1) 가중치 없는 그래프 (Unweighted Graphs): 간선 개수가 가장 적은 경로BFS를 사용하여