iOS 기록보관소

이진 탐색(Binary Search) 분할정복 방식을 사용하여, 매 단계에서 탐색 범위를 반으로 줄여나가며 특정 값을 찾아내는 알고리즘 정렬된 배열에만 적용 가능하기 때문에, 이진 탐색을 수행하기 전에 배열이 정렬되어 있어야 한다. 시간복잡도 : O(logN) 1. 초기화 : 탐색 시작 전, 검색 범위를 배열의 전체로 설정 - 최소 인덱스 low(임의의 변수이름)를 0으로, 최대 인덱스를 배열의 마지막 인덱스 high(임의의 변수이름)로 설정 2. 중앙 요소 확인 : 배열의 중앙 요소를 찾는다. - (최소 인덱스 + 마지막 인덱스) / 2가 중앙 요소의 인덱스일 것이다. 3. 조건 판단 - 중앙 요소가 찾고자 하는 값과 같다면, 탐색을 종료하고 그 위치를 반환 - 중앙 요소가 찾는 값보다 크다면, 찾는 ..

힙이란? 트리 자료구조 중 하나 데이터 중 가장 크거나 작은 값을 계속 알아내야 할 때 유용하게 쓰일 수 있는 자료구조 : 우선순위 큐를 구현하기에 좋다! -> 최대 힙 / 최소 힙 두 종류가 있음 힙 조건 : Heap Condition 각 노드의 값은 그 노드의 모든 자손노드보다 커야 한다.(최대힙) / 작아야 한다. (최소힙) 트리는 완전해야 한다. - 중간에 빠진 노드 없이 완전히 채워진 트리를 의미함 바닥에는 빈 자리가 있어도 되지만, 빈 자리가 마지막 노드여야 한다. ( 빈자리의 오른쪽에 어떤 노드도 없어야 한다. ) 즉, 힙 조건을 만족하기 위해 빈 자리는 바닥 줄의 오른 쪽에만 존재할 수 있다. **** 검색, 삽입, 삭제에서 모두 O(logN)로 빠른 연산이 가능하게 하기 위해서는 트리가 ..

각 정렬/탐색별로 간단한 알고리즘과 시간복잡도만 정리 1. 선택정렬 (Selection Sort) 제자리 정렬 알고리즘의 일종. 주어진 리스트 중 최소값을 index의 값과 교체 -> index는 단계를 거듭할 수록 1씩 증가. 버블정렬보다는 빠름 최선: O(N^2) / 최악: O(N^2) 2. 삽입정렬 (Insertion Sort) 모든 요소를 앞에서부터 차례대로 비교하여, 자신의 위치를 찾아서 삽입 구현은 쉽지만 효율이 떨어짐. 선택정렬이나 버블정렬보다는 빠름 최선:O(N) / 최악: O(N^2) 3. 버블정렬 (Bubble Sort) 인접한 원소를 정렬시켜나감. 코드로 구현하기엔 쉽지만 느리다 최선: O(N) / 최악: O(N^2) 4. 병합정렬 (Merge Sort) 분할정복알고리즘의 일종. 부분..

이진탐색트리란? (BST, Binary Search Tree) '트리' 자료구조를 기반으로 한, 이진 탐색이 가능하도록 구현된 자료구조 기본적인 트리 구조에 아래와 같은 특징들이 추가된다. - 각 노드의 자식의 개수는 왼쪽에 1개 이하, 오른쪽에 1개 이하이다. (왼쪽/오른쪽에 자식이 있거나 / 없거나) - 왼쪽 자식노드에는 노드보다 작은 값이 들어갈 수 있다. - 오른쪽 자식노드에는 노드보다 큰 값이 들어갈 수 있다. ㅋㅋ 세상에서 제일 못생긴 이진탐색트리.. 아무튼 위처럼 생겼다. 이진탐색트리를 구현할 때는 연결리스트를 이용할 건데 연결리스트의 노드 만들 때 data, nextNode(포인터)의 항목을 갖는 클래스를 만들었었다. 마찬가지로 노드 클래스를 먼저 만들어주고, BST 클래스도 만들어주면 됨..

오늘 연결리스트라는 것을 새로 배운 기념으로.. https://www.acmicpc.net/problem/1158 어제 시간초과로 똥쌌던 위 문제를 연결리스트로 한 번 풀어봄 결과는 시간초과지만 연결리스트를 구현해본다는 것에 의미를 두었음 class Node { var data: T? var next: Node? init(data: T?, next: Node? = nil) { self.data = data self.next = next } } class LinkedList { var head: Node? init(head: Node?) { self.head = head } func append(data: T?) { if head == nil { head = Node(data: data) return } ..

재귀함수가 필요한 경우 1. 반복적인 작업이필요한 경우 ex) 팩토리얼 2. 하위문제의 계산결과를 통해 계산할 수 있는 경우 ex) 숫자의 합 구하기, 숫자 배열에서 최대값 구하기 재귀가 필요한 조건을 구분하는 것이 가장 어려운 부분인 듯 합니다. 특히 DP와 관련된 여러 문제를 다루어보면서 어떤 경우에 재귀를 사용해야할지 판단하는 것을 연습하는 것이 필요할 듯 하네요 재귀함수에 대한 오해 - 루프를 사용한 코드보다 무조건 빠르다? 경우에 따라 다르다. - 재귀함수 안에서는 루프를 쓰면 안된다? 아니다. 재귀함수 만드는 방법 상향식(Bottom-up), 하향식(Top-down) 두 가지 방식이 있습니다. 일반적으로 바텀-업 방식은 루프에 비해 딱히 장점이 없고, 코드가 간결하지 못하기 때문에 탑-다운 방..

스택과 큐는 임시 데이터를 처리할 수 있는 자료구조이다. 둘 다 데이터를 처리한 후에 버리는데, 데이터를 처리하는 순서에 중점을 두는 것이 특징이다. 스택에 대해 먼저 정리하려고 함 스택 (Stack) 스택의 끝에만 데이터를 삽입 (push) 스택의 끝에서만 데이터 삭제 (pop) 스택의 마지막 원소만 읽기 (read) ==> LIFO (Last In, First Out) 방식을 따른다. 스위프트에서는 스택이라는 자료구조가 따로 자료형이나 클래스 등으로 제공되지 않기 때문에 스택을 사용하려면 직접 구현해야 한다. (다른 대부분의 언어에서도 제공하지 않음) 굳이? 왜? 어떤 이점이 있을까? 1. 버그를 막을 수 있다 어떤 제약조건(스택의 경우, 입력받은 데이터의 끝에서만 동작함)이 있는 경우 그 조건에서만..

언어마다 'Hash Table' 이라는 자료 구조를 제공하는데 swift에서는 'Dictionary'라는 해시 테이블 자료구조를 사용할 수 있다. 해시 테이블이란 key-value 쌍을 갖는 리스트이며, 빠른 읽기가 가능하다. 무슨 말이냐? 예를 들어 메뉴와 가격이 적혀있는 메뉴판이 하나 있다. ( 아아 = 2500, 아바라 = 3500, 아이스초코 = 5000, 얼음물 = 10000, 레몬에이드 = 2000 ) 레몬에이드의 가격을 얻고싶다면? 배열로 생성하고, 검색할 경우 Linear Search를 사용한다. 한 배열 내에 존재하기 때문에 비슷한 주소값을 갖는다 하더라도 인덱스를 하나씩 뒤져봐야 하므로 O(N)만큼의 시간복잡도를 갖게 된다. 하지만 이 값이 해시테이블에 들어있다면? '레몬에이드'(key..

버블정렬과 선택정렬, 삽입정렬을 비교해보고, 빅오의 개념과 코드의 효율성에 대해 생각해보기 우선 오름차순으로 정렬하는 경우의 처리과정과 각각의 예제를 정리해봄 버블정렬 연속된 항목 비교 -> 정렬 -> 포인터를 한 칸 옮김 -> 반복 패스스루가 끝나면 다시 처음부터 정렬, 교환이 일어나지 않는 경우 루프 종료 버블정렬 예시 //오름차순으로 정렬 - bubble sort var arr = [2,1,3,4,5] var temp = 0 while true { var count = 0 for i in 0.. arr[i+1] { temp = arr[i] arr[i] = arr[i+1] arr[i+1] = temp count += 1 } } if count == 0 { break } } -> 버블정렬의 효율성은 O..

알고리즘을 공부하기 위해 가장 먼저 알아야 하는 것! 이해하기 쉽게 말하자면, 시간 복잡도 : 어떠한 문제를 해결하기 위한 데이터와 수행시간의 관계 (대충 느낌만 가집시다) Big O : 시간 복잡도를 직관적으로 표현하는 방법 => 데이터가 늘어날 때 알고리즘의 단계가 어떻게 바뀌는가? 또 알아두어야 할 것이 있는데, 보통 알고리즘에서의 최악의 경우를 빅오로 나타낸다. -- 느낌만 가져가봅시다 더보기 선형탐색으로 예를 들자면, 1부터 100까지 있는 배열이 있고, 인덱스 0부터 하나씩 늘려가며 탐색을 하는 알고리즘을 가정했을 때 1을 탐색할 때는 O(1)이 되지만, 100을 탐색하고자 한다면? 배열이 200까지 늘어나고, 200을 탐색하고자 한다면? 이는 O(N)이라고 표현하는 게 맞음 (O(N)이 무엇..