스택이란 ? stack의 뜻을 사전에서 찾아보니 쌓이다, 채우다, 무더기 라는 뜻이 나온다. 그럼 자료구조에서 스택이란 무엇일까 ? 바로 데이터를 순서대로 쌓는 자료구조이다. 음 .. 간단하게 예시를 들어보자면 스택은 박스다. 박스에 물품들을 차곡차곡 쌓다보면 마지막에 저장한 물품을 가장 먼저 꺼내게 된다. 스택도 동일한 구조이다. 스택의 특징 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out) 구조이다. 즉, 스택은 박스와 같은 구조로 양 옆과 바닥이 막혀 있어서 한 방향으로만 뺄 수 있는 구조이다. 넣은 순서와 꺼낸 순서가 역순이 된다 예를 들자면 스택에 0, 1, 2의 순서로 데이터를 넣고 꺼낸다면 2, 1, 0 순서로 꺼내게 된다. 파이썬에서 스택은..
연결 리스트란? 원소들을 저장할 때 그다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 원소들은 이곳저곳에 흩어져 있다. 파이썬에서는 배열과 연결 리스트의 장점을 합친 리스트를 사용한다. 연결 리스트의 성질 k 번째 원소를 확인/변경하기 위해 O(k)가 필요함 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트의 종류 배열과 다르게 리스트에는 몇 개의 종류가 있다. 단일 연결 리스트(Singly Linked list) 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트 [데이터1] -> [데이터2] -> [데이터3] -> None 이중 연결 리스트(Doubly Lin..
배열이란? 메모리 상에 원소를 연속하게 배치한 자료구조 배열에 저장되는 요소들은 모두 동일한 자료형을 가져야 한다. 배열은 생성될 때 크기가 정해진다. 파이썬에서는 리스트 타입이 배열의 기능을 한다. 배열의 성질 O(1)에서 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리 양(=overhead)가 거의 없음 Cache hut rate가 높음 배열의 인접한 요소들은 함께 캐시에 로드되어 캐시 라인 활용을 최대화하며, 이로 인해 데이터 접근 시간을 줄여 더 빠른 연산을 가능케 하는 것 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 기능과 구현 # 1차원 배열 = 리스트 arr = [1, 2, 3, 4] print(arr[3]) # 4 출력 # 2차원 배열 arr2 = [[1, 2, 3]..
시간 복잡도(Time Complexity) 컴퓨터는 1초에 연산을 몇 번 할 수 있을까? 문제를 풀 때는 대략 1초에서 1억번 정도로 잡는다. 이렇듯 알고리즘 문제를 해결할 때, 코드의 실행 시간과 메모리 사용량은 중요한 요소이다. 효율적인 알고리즘을 작성하려면 어떻게 코드를 구성해야 할지 고민해야 한다. 이 때 중요한 개념 중 하나가 시간 복잡도와 공간 복잡도, Big-O 표기법이다. 시간 복잡도란 무엇인가? 알고리즘의 시간 복잡도는 입력값의 크기에 따라 알고리즘이 얼마나 많은 연산을 수행하는지를 나타내는 지표이다. 즉, 내 코드의 실행 시간이 얼마 걸리는지 알 수 있다. 시간 복잡도를 분석하여 입력값이 커질 때 알고리즘의 실행 시간이 어떻게 증가하는지 예측할 수 있다. 메모리는 시간이 흐를수록 효율적..
1. 알고리즘이란? 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법, 문제를 해결하는 방법 한 문제를 해결하는 방법은 한 가지만 있는 게 아니라 무수히 많을 수 있다. 자주 쓰이는 문제 해결 방법(알고리즘)은 패턴화하기. (BFS, DFS, DP, 다익스트라 등등) 각 상황에 적합한 알고리즘을 선택할 수 있어야 한다 2. 알고리즘 평가기준 1. 시간 복잡도: 적은 시간을 잡아먹는 알고리즘 2. 공간 복잡도(메모리): 최대한 적은 용량의 메모리를 사용 3. 구현 복잡도: 간단하게 구현 코테에서는 공간보다는 시간을 더 중요하게 생각한다. 코딩테스트 준비하기 1.시간 복잡도 알고리즘 선택의 기준이 되는 시간 복잡도 시간 복잡도를 정의하는 3가지 유형 빅-오메가: 최선일 때 연산 횟수 빅-세타: 보통일 ..
큐란 무엇인가 ? 먼저 Queue의 사전적 의미는 줄, 대기행렬이다. 자료구조에서 큐는 처음에 저장한 데이터를 가장 먼저 꺼내는 것이다. 간단하게 예를 들어보자면 줄 서기 ! 만약 맛집에 가려고 줄을 서고 있는데 뒤에 있는 사람이 먼저 들어간다면 ? 너무 불공평하지 않은가 ? 큐도 0, 1, 2 데이터를 넣고 꺼낼 때도 0, 1, 2 로 꺼내게 된다. 큐의 특징 FIFO, LILO -> 선입선출 즉, 순서대로 처리 큐 메서드 메서드 설명 boolean add(Object o) 지정된 객체를 Queue에 추가한다. 성공하면 true를 반환, 저장공간이 부족하면 예외 발생 Object remove() Queue에서 객체를 꺼내 반환. 비어있으면 예외 발생 Object element() 삭제없이 요소를 읽어온..
