자료구조&알고리즘/기본개념12 swift 알고리즘 - 삽입정렬 한방에 이해하기 swift 알고리즘 - 삽입정렬 한방에 이해하기 삽입정렬 정의 삽입 정렬이라고 하면 어떤 데이터를 어디에 삽입을 하면서 정렬을 할까? 라는 생각을 할 수 있습니다. 먼저 어떤 데이터를 삽입을 할까요? 바로 정렬이 안된 데이터 입니다. 삽입 정렬에서 정렬이 안된 데이터를 key라고 부릅니다. 그럼 어디에 데이터를 삽입할까요? 바로 정렬이 된 데이터(배열) 입니다. 삽입정렬을 한마디로 정의하면 정렬이 안된 데이터를 정렬이 된 배열 속으로 삽입하는 것이라고 할 수 있습니다. 그럼 아래와 같이 정렬이 안된 [5,3,4,7,2] 라는 배열 데이터가 주어졌습니다. 이 데이터를 이제 삽입 정렬을 이용해서 정렬해야 합니다. 어떻게 해야 할까요? 삽입 정렬에서 데이터를 정렬하기 위해 몇 가지 규칙을 정합니다. [1] 배.. 2022. 8. 10. swift 알고리즘 - 버블정렬 쉽게 이해하기 swift 알고리즘 - 버블정렬 쉽게 이해하기 버블 정렬이란 버블정렬은 서로 인접한 두 요소를 비교하면서 정렬해 나가는 알고리즘입니다. 인접한 두 요소를 비교해서 크기가 순서대로 정렬이 안되어 있다고 판단되면 크기가 큰 데이터를 오른쪽으로 위치시키면서 정렬을 진행하고, 가장 큰 데이터가 가장 뒤로 가게 됩니다. 예를 들어 [7,4,5,1,3]이라는 정렬되지 않은 배열이 주어졌다고 가정해 보겠습니다. 여기서는 무엇과 무엇을 비교해야 할까요? 먼저 대상이 되는 숫자를 정해야 합니다. 위 배열에서는 첫번째 대상 숫자는 7입니다. (대상숫자는 비교의 시작이 되는 숫자라고 생각하시면됩니다.) 비교의 시작이 되는 숫자 = 대상숫자 그러면 7과 무엇을 비교해야 할까요? 버블정렬의 정의를 보면 서로 인접한 숫자와 비교.. 2022. 8. 10. swift 알고리즘 - 선택정렬 한방에 이해하기 swift 알고리즘 - 선택정렬 한방에 이해하기 선택정렬이란 정렬되지 않은 데이터들 가운데서 가장 작은 데이터를 차아 가장 앞의 데이터와 교환해 나가는 알고리즘 입니다. 배열 7, 4, 5, 1, 3 이라는 정렬되지 않은 데이터를 가지고 선택 정렬로 오름차순으로 정렬해 보겠습니다. 먼저 반복문은 총 몇개가 필요하며 필요한 준비물(변수)들은 어떤것들이 있을까요? 아래 그림을 보면서 하나씩 정해봅시다. 일단 선택정렬은 정해진 범위(데이터)에서 최소값을 찾을 찾는 것이 1차 목표이고 이 1차 목표를 달성하기 위해서 비교라는 것을 해야 합니다. 비교라는 것을 하기 위해서는 두개의 무언가가 필요합니다. 그래야 비교를 할 수 있겠죠? 1회 전에서는 7 부터 4, 5, 1, 3 을 각각 비교 해서 최소 값을 계속 업.. 2022. 8. 9. swift 자료구조 queue 코드로 정리2 - stack을 이용해서 구현 swift 자료구조 queue 코드로 정리2 - stack을 이용해서 구현 지난 포스팅(swift 자료구조 queue 코드로 정리 - 큐 일상생활 예제)에서 큐의 기본 정의와 array로 큐를 구현해 보았습니다. 지난 포스팅에 이어서 이번 포스팅에는 두개의 스택을 이용해서 큐를 구현해 보고자 합니다. 두개의 스택 leftStack과 rightStack 변수를 생성합니다. 이 두 변수의 타입은 배열 입니다. 왼쪽 스택과 오른쪽 스택 모두 합쳐서 하나의 스택이 되는 구조입니다. 그럼 왼쪽 스택과 오른쪽 스택은 각각 무슨 용도일까요? 먼저 오른쪽 스택은 큐에서 enqueue 에 사용됩니다. 즉, 자료구조 큐에 데이터를 삽입을 하면 오른쪽 스택(rightStack)에 삽입을 합니다. 왼쪽스택은 큐의 dequeu.. 2022. 8. 9. swift 자료구조 queue 코드로 정리 - 큐 일상생활 예제 swift 자료구조 queue 코드로 정리 - 큐 일상생활 예제 자료구조 큐란 일상생활의 예를들어 보면 자료구조 큐는 마트에서 줄서는 구조와 같습니다. 또는 버스를 탈려고 줄을 선다던가, 영화관에서 줄을 서는 구조와 같습니다. 제일 앞에 있는 사람이 제일 먼저 서비스를 받겠죠? 제일 마지막에 있는 사람이 제일 마지막에 서비스를 받구요. 일상생활에서의 이런 구조를 그대로 옮겨온 자료구조가 바로 큐 입니다. 큐의 작동 큐는 필수적으로 2가지 역할이 필요합니다. [1] 인큐(enqueue) : 데이터를 큐의 제일 뒤에 넣는 역할 [2]디큐(dequeue) : 큐의 제일 앞에 있는 데이터를 삭제 후 리턴하는 역할 그리고 부수적으로 큐가 비었는지 확인하는 역할과, 제일 앞의 데이터를 삭제하지 않고 리턴만 하는 역.. 2022. 8. 8. swift 자료구조 stack 코드로 정리 - 스택 일상생활 예제 swift 자료구조 stack 코드로 정리 스택이란? 스택은 우리 일생생활에서 쉽게 찾아 볼 수있는 구조 입니다. 예를들어 박스에 책을 한 권씩 높게 쌓아 올린 그림을 떠올려 볼 수 있고, 팬케이크를 한장씩 쌓아올린 그림을 떠오려 볼 수 있습니다. 이 예 말고도 많은데, 스택은 어떤 물건을 하나씩 쌓아 올린 구조라고 떠올리면 됩니다. 스택의 작업 스택은 대표적으로 두가지가 있습니다. [1] push : 스택의 맨 위에 요소를 추가합니다. (높이 쌓인 책들이 있는데 그 위에 책을 하나 올려 놓는 것입니다.) [2]pop : 스택의 맨 위에 요소를 제거 합니다. ( 높이 쌓인 책들이 있는데 그 중에서 제일 위에 있는 책을 제거하는 것입니다.) 스택을 한 마디로 정리하면 스택은 한쪽에서만 요소를 추가하거나 제.. 2022. 8. 8. swift 자료구조 - 연결리스트 코드로 정리 - 2 swift 자료구조 - 연결리스트 코드로 정리 - 2 지난 포스팅에서 swift로 연결리스트를 구현하고 Node들을 추가하는 기능까지 구현을 했습니다. Node들을 추가하는 함수에는 push, append, insert 를 각각 구현했죠. push는 연결리스트에서 새 노드를 연결리스트 제일 앞에 추가하는 함수입니다. append 는 연결 리스트에서 새 노드를 연결리스트 제일 뒤에 추가하는 함수 입니다. insert는 연결 리스트에서 새 노드를 특정 위치에 삽입하는 함수입니다. 위의 내용인 swift 자료구조 - linkdedlist 연결리스트 코드로 정리 - 1 이 포스팅에 모두 자세히 적어 놓았습니다. 이 포스팅을 읽기전에 위의 포스팅을 먼저 읽고 오셔야 이해가 됩니다. 그럼 이번 포스팅에서는 swif.. 2022. 8. 6. swift 자료구조 - 연결리스트 코드로 정리 - 1 swift 자료구조 - 연결리스트 코드로 정리 연결 리스트 연결리스트는 배열의 단점을 보완한 자료구조입니다. 배열의 단점으로는 크게 2가지가 있습니다. [1] 배열을 선언할 때 배열의 크기를 지정해버리면 지정한 크기 만큼 요소를 할당 할 수 있다는 것. 즉, 배열의 크기가 5면 요소를 6개, 7개 할당을 할 수 가 없다는 것입니다. [2]배열 안의 요소를 삭제할 때 오버헤드가 커진다. 예를 들어 1부터 5까지 5개의 요소가 들어 있는 배열에서 정 가운데 있는 숫자 3을 삭제한다면? 숫자 3의 자리는 비게 되고 빈공간을 채우기 위해서 뒤에 위치한 숫자 4와 5가 한칸씩 앞으로 이동하게 됩니다. 예제가 배열의 크기가 5개라서 그렇지 만개 십만개라면? 그 오버헤드는 엄청 클것입니다. 그래서 연결리스트 자료구조.. 2022. 8. 6. [그림으로 배우는 자료구조] 스택이란? [그림으로 배우는 자료구조] 스택이란? 스택에 대해서 배우기 전에 먼저 책들이 담긴 상자를 떠올려 봅시다. 자 이제 긴 박스에 담긴 책을 비우고 다시 새책을 3권 넣어보겠습니다. A, B, C 책 3권이 긴 박스에 들어갔습니다. 이제 긴 박스에서 책을 꺼내 보겠습니다. 제목이 A라는 책을 꺼내서 보고 싶은데 위에 B와 C라는 책이 있어서 A 책을 바로 꺼낼 수 가 없습니다. 그럼 어떻게 해야 할까요? C책을 먼저 꺼내고, B책을 꺼낸 후, A 책을 꺼내면 되겠죠? 스택도 긴 박스에 책을 하나씩 넣고 빼는것과 동일한 구조입니다. 스택에 데이터를 하나씩 순서대로 넣을 수 있고, 데이터를 꺼낼 때는 제일 마지막에 넣은 데이터부터 꺼낼 수 있습니다. 이러한 스택의 구조적인 특징을 LIFO(Last In Fris.. 2022. 7. 21. 이전 1 2 다음
