조이의 개발 성장 다이어리

우선순위 큐(Priority Queue) 란? 기존의 큐(Queue)가 선입선출(FIFO, First-In, First-Out) 구조였다면 우선순위 큐는 우선순위가 높은 데이터가 먼저 선출되는 구조의 자료구조이다. 주로 우선순위 큐는 최소값/최대 값부터 먼저 빠져나오는 힙을 사용하여 구현한다. 힙 포스팅 참고 Swift로 우선순위 큐 구현하기 최소힙/최대힙 원리를 알고 구현했으면 그걸 그대로 가져오기만 하면 된다. import Foundation struct PriorityQueue { var heap = Heap() var count : Int { return heap.count } var isEmpty : Bool { return heap.isEmpty } mutating func pop() -> T..

Swift로 힙을 구현하기 전에, 우선 힙의 개념을 정리해보고자 한다. 힙(Heap) 이란? 1) 완전 이진 트리 (왼쪽에서 오른쪽으로 차례대로 채워진 이진 트리) 2) 최소 힙 : 부모 노드의 값은 항상 자식 노드들의 값보다 작거나 같다. (보통 코딩테스트에서는 이걸 기본으로 하고, 최대를 구해야할 때는 음수로 치환해서 품. 다익스트라 알고리즘에서도 사용) -> 루트 노드가 최소값 최대 힙 : 부모 노드의 값은 항상 자식 노드들의 값보다 크거나 같다. -> 루트 노드가 최대값 * 우선순위 큐를 구현할 때 힙을 자주 쓰는 이유는, 노드의 값이 작아질수록 혹은 클수록 우선순위가 높아진다고 고려했을 때 힙에서 데이터를 추출할 때 우선순위가 높은 것(가장 작은것 혹은 가장 큰 것)부터 먼저 추출되므로 우선순위..

Swift로 직접 자료구조 구현하기 - 덱 ✅ 간단하게 알아보는 덱 - 스택과 큐의 연산을 모두 가지고 있는 자료구조이다. - 앞, 뒤에서 삽입, 삭제 모두 가능한 자료구조 1) 뼈대 잡기 (더블 스택을 사용한 큐와 동일) struct Dequeue { var input = [T]() var output = [T]() var isEmpty : Bool { return input.isEmpty && output.isEmpty } var size: Int { return input.count + output.count } var first: T? { if isEmpty { return nil } return output.isEmpty ? input.first! : output.last! } var last:..

Swift로 직접 자료구조 구현하기 - 큐 ✅ 간단하게 알아보는 큐 - 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조로, FIFO(First-In, First-Out), 선입선출 구조 이다. - 마치 음식점에서 줄섰을 때, 먼저 줄 선 사람부터 식당에 들어가는 것과 같다 - 메소드는 enqueue() : 큐에 데이터를 넣기 / dequeue() : 큐에 데이터를 꺼내기 가 있다. 1) 뼈대 잡기 struct Queue { var elements:[T] = [] var isEmpty: Bool { return elements.isEmpty } var size: Int { return elements.count } } 2) 메소드 추가 - enqueue(), dequeue() mutating fun..

Swift로 직접 자료구조 구현하기 - 스택 스택 개념 설명과 C 언어 코드는? 여기를 참고해주세요! 혹시 틀린 부분이 있다면 지적해주시면 감사하겠습니다! 1) 뼈대잡기 - 스택에 담길 요소를 담은 배열 elements - count는 스택의 크기로, 배열의 크기이며 isEmpty는 스택이 비어있는지 확인하는 변수로, pop 연산이나 peek 연산 수행 시 쓰인다. struct Stack { var elements: [T] = [] //제너릭으로 배열 생성 var count : Int { return elements.count } var isEmpty : Bool { return elements.isEmpty } } 2) 관련함수 - 스택에는 데이터를 추가하는 push(), 데이터를 꺼내오는 pop() ..

스택(Stack)이란? 데이터를 쌓아 올리는 자료형 -> 후입 선출 형태(LIFO:Last-In First-Out, 가장 최근에 들어온 데이터가 가장 먼저 나감) 스택의 구조 스택에서의 입출력은 맨 위에서만 발생한다. (한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조) 스택 상단(top) : 스택에서 입출력이 이루어지는 부분 요소(element) : 스택에 저장되는 것 스택의 연산 push 연산 : 스택에 데이터 추가 pop 연산 : 스택의 데이터 삭제 peek 연산 : 삭제하지 않고 보기만 하는 연산 스택의 구현 is_empty() : 스택이 비어있는지를 검사하는 함수 -> top이 -1이면 공백 is_full() : 스택이 포화 상태인지를 검사하는 함수 -> top이 MAX_STACK_SIZE-1이면..

선택 정렬이란? 오름차순으로 정렬할 경우, 가장 작은 숫자를 선택하여 왼쪽으로 이동하거나 가장 큰 숫자를 선택하여 오른쪽으로 이동하는 정렬 방법이다. (내림차순의 경우, 가장 작은 숫자는 오른쪽으로, 가장 큰 숫자는 왼쪽으로 이동한다) 즉, 배열에서 최소값을 찾아 이 최소값을 배열의 첫 번째 요소와 교환하고 그 다음에는 첫 번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하여 두 번째 요소와 교환한다. (최대값을 찾아 배열의 마지막 요소와 교환하고 그 당므에는 마지막 요소를 제외한 나머지 요소들 중에서 가장 큰 값을 선택하여 마지막에서 두 번째 요소와 교환한다.) 이 과정을 (배열의 크기-1) 만큼 반복하여 배열이 모두 정렬될 때까지 반복한다. 최소값을 찾아 교환하는 방식 void selec..

동적 메모리 할당이란? int a[100]과 같이 고정된 크기로 필요한 메모리 할당을 하는 방법을 정적 할당이라고 한다. 그러나 프로그램을 작성하면서 얼마나 많은 입력이 있을지 알 수가 없는 경우가 많다. 만약 고정된 크기보다 더 큰 입력이 들어온다면 프로그램을 처리하지 못하며, 더 작은 입력이 들어온다면 메모리를 낭비하게된다. 따라서, 이러한 문제를 해결하기 위해 실행 중에 필요한 만큼의 메모리를 운영체제에서 할당받아 사용하고, 사용이 끝나면 다시 시스템에 메모리를 반환하는 기능을 동적 메모리 할당(dynamic memory allocation)이라고 한다. 이 때, 동적 메모리가 할당 되는 공간은 힙(heap)이다. 힙은 운영체제가 사용되지 않는 메모리 공간을 모아 놓은 곳이다. 동적 메모리 할당 형..

포인터란? 다른 변수의 메모리 주소(바이트 단위)를 가지고 있는 변수 정수형, 실수형, 문자형 등 여러 가지 자료형으로 선언될 수 있다. 주소연산자 : & 간접 (참조) 연산자 : * ex) int *p; // 정수형 포인터 선언 int a = 200; //정수형 변수 선언 p = &a; //포인터 p는 a의 메모리 주소를 가리킨다. 즉, p는 변수 a를 가리킨다. p의 값은? : 변수 a의 주소값 *p의 값은? : 변수 a가 실제로 가지고 있는 값(200) 위 코드에 *p = 20을 마지막에 추가하면 a의 값은? : 20으로 바뀐다. 포인터 p는 변수 a를 가리키고 있어서 값을 복사하는 것이 아니다. 따라서 *p의 값을 변경하면 a의 값도 같이 바뀐다. 널 포인터 어떤 객체도 가리키지 않는 포인터이다...

구조체란? 타입이 다른 데이터를 묶는 방법 구조체 정의 - 구조체 명 struct student { int id; char name[20]; int midterm; int final; }; student : 구조체와 구조체를 구별해주는 식별자. 구조체 태그 라고도 함 id, miterm, name, final : 구조체 멤버 구조체 변수 선언 : struct student aStudent; -> 이렇게 선언해야만 메모리가 잡힘 구조체 변수 선언과 초기화 동시에 : struct student aStudent = {20191111, "율짱", 100, 90}; 구조체 정의 - 구조체 타입 typedef struct student{ int id; char name[20]; int midterm; int fin..