본문 바로가기

Computer Science/DS & Algorithm5

Linear Data Structure : 스택, 큐, 덱 개념 자료 간의 연결 형태에 따라 자료구조의 종류를 구별했을 때, 자료를 순차적으로 나열한 형태를 선형 자료구조라고 한다. 하나의 자료 뒤에 다른 하나의 자료가 오는 형식으로 선형 자료구조 안에서도 기본, 제한으로 나뉜다. 이 글에서는 제한 선형 자료구조에 속하는 스택, 큐, 덱에 대해 정리한다. 스택(Stack) 스택, 큐, 덱의 가장 큰 차이점은 데이터의 출입 방향이다. 스택은 데이터가 들어오고 나가는 길이 한 방향 밖에 없어서 데이터를 스택에서 뺄 경우 위의 사진과 같이 들어온 곳으로 나가게 된다. 책을 쌓는 것처럼 아래쪽부터 값이 차곡차곡 쌓이기 때문에 나중에 들어온 데이터가 먼저 나가는 LIFO(Last In First Out, 후입선출) 구조이다. 위 이미지처럼 세로 형태로 스택을 설명하는 그.. 2021. 7. 4.

Divide and Conquer : 분할 정복 - 퀵 정렬 개념 배열을 둘로 분할하고 분할한 배열을 재귀 호출로 정렬하여 하나의 배열로 만든다는 점이 합병정렬과 비슷하지만, 좌/우를 균등분할하는 것이 아니다. pivot(기준 원소)을 선정하여 pivot보다 작은 원소는 모두 왼쪽 배열로, 크거나 같은 원소는 모두 오른쪽 배열로 가도록 분할한다. * 위의 이미지에서 검은색 배경의 숫자가 pivot 특징 ▪ 불안정 정렬 ▪ 비교 정렬(값 비교에 기반한 정렬 알고리즘) ▪ 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 위치가 결정되기 때문에 반드시 끝나는 알고리즘이라는 것을 보장 가능 흐름 ① pivot 선정 ② [분할] pivot보다 작은 원소들이 앞에 오고, 뒤에는 값이 크거나 같은 모든 원소들이 오도록 배열을 둘로 분할 ③ [정복] 부분 배열을 정렬(배열.. 2021. 4. 18.

Divide and Conquer : 분할 정복 - 이분탐색, 합병정렬 개념 문제의 입력 사례를 두 개 이상의 작은 케이스로 분할한 후 분할한 입력의 답을 바로 구할 수 있다면 원래 문제의 답은 분할로 얻은 답들을 통해 구할 수 있는 방식. 상위 입력 사례의 해답을 하위 입력 사례 해답을 이용해 구하기 때문에 하향식(top-down) 풀이 방식에 속한다. 예시 1) 이분탐색 10 12 15 16 18 20 25 27 42 43 이분탐색을 사용하려면 배열이 이미 정렬된 상태여야 한다. 위와 같은 배열에서 27이 배열 안에 있는지 확인한다고 가정하자. ① [분할] 가운데에 위치한 원소를 기준으로 배열을 나누고 찾는 값이 가운데 원소보다 작으면 왼쪽 배열, 크면 오른쪽 배열을 선택 ② [정복] ①에서 선택한 부분에 찾고자 하는 값이 있는지 재귀적으로 이분 검색 ③ [병합] ②에서.. 2021. 4. 16.

Greedy : 탐욕법 개념 매 순간마다 그 상황에서 가장 최적인 선택을 하는 방식. 각 단계에서 내린 결정이 전체로 봤을 때도 최적일 거라는 보장은 없다. 위 사진을 참고하여 세 숫자의 합이 가장 커질 수 있는 경우를 생각해보자. 실제로 가장 큰 수는 109지만 Greedy algorithm의 결과로 나온 값은 25가 된다. 여기서 첫 줄의 '매 순간마다 그 상황에서 가장 최적인 선택을 하는 방식'을 떠올릴 수 있다. Greedy algorithm에 따른 숫자 선택 과정은 아래와 같다. ① 7에서 시작 ② 3과 12를 만났을 때 더 큰 수인 12 선택(3을 선택할 경우 99로 갈 수 있지만 미래의 선택에 대해서 생각하지 않음) ③ 12에서 5, 6을 만났을 때 더 큰 수인 6 선택 하지만 탐욕법을 이용해 항상 부분 최적해를 .. 2021. 2. 23.

[종만북] 알고리즘 설계 패러다임 - 무식하게 풀기 Brute-force (=exhaustive search) 컴퓨터의 계산 능력을 이용해 가능한 경우의 수를 모두 나열하면서 답을 찾는 방법 1. 재귀 호출과 완전 탐색 ◽ 재귀 호출 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 과정 재귀 호출에 사용되는 함수가 재귀 함수 ex) 1부터 n까지의 합 Base case : 더 이상 나눌 수 없는 가장 작은 단위의 작업 ex) 1부터 n까지의 합에서 n이 1이면 return 1 존재하는 모든 입력이 base case의 답을 이용해 계산될 수 있도록 base case를 선택해야 함 🔑 Boggle game ① 문제의 분할 ▫ 시작 위치 글자가 주어진 단어 첫 글자와 다르면 False.. 2020. 11. 7.

이전 1 다음

티스토리툴바