전체 글36 [알고리즘] 분할정복(divide and conquer) 분할정복이란 ? 분할정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법입니다. 대표적인 예로는 정렬 알고리즘 중 퀵 정렬이나 합병 정렬과 이진 탐색, 선택 문제, 고리 푸리의 변환(FTT) 문제들이 대표적입니다. 정렬 알고리즘 선택 정렬과 삽입 정렬의 최대 실행시간은 O(n^2)로 입력하는 배열의 크기가 크다면 정렬하는데 시간이 오래 걸릴 수 있습니다. 반면 분할정복 알고리즘을 사용하는 합병정렬의 실행시간은 O(nlogn)으로 퀵 정렬은 최대 O(n^2)지만 최선이나 평균의 경우 O(nlogn)으로 비교적 빠른 시간을 갖는 것을 볼 수 있습니다. 정렬 알고리즘 최대 실행 시간 최소 실행 시간 평균 실행 시간 선택 정렬 O(n^2) O(n^2) O(n^2) 삽입 정렬 .. 2022. 9. 21. [알고리즘] 백트래킹 (Backtracking) 백트래킹(Backtracking)이란 ? 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 깊이 우선 탐색 (DFS) vs. 백트래킹 (Backtracking) DFS DFS는 가능한 모든 경로를 탐색합니다. 그러므로 불필요한 경로를 사전에 차단하는 등의 행동이 없으므로 경우의 수를 줄일 수 없습니다. 따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능합니다. 백트래킹 해를 찾아가는 도중 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더 이상 가지 않고 되돌아갑니다. 이를 가지치기라고 하는데 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다. 하지만 만약 N! 의 경우의 수를 가진 문제에서.. 2022. 9. 14. [iOS] URLSession URLSession이란 ? 앱과 서버간의 데이터를 주고받기 위해서는 HTTP 프로토콜을 이용해서 데이터를 주고 받아야합니다. URLSession이란 앱에서 서버와 통신하기 위해 애플이 제공하는 API로 HTTP를 포함한 몇가지 프로토콜을 지원하고, 인증 / 쿠키 관리 / 캐시 관리 등을 지원합니다. 즉, iOS 앱에서 네트워킹을 하기 위해 필요한 API입니다. URLSession 사용 순서 Configuration 결정 Session 생성 Request에 사용할 url 설정 Task 결정 및 작성 URLSessionConfiguration URLSession을 생성하기 위해 필요한 요소입니다. Configuration을 생성할 때는 URLSession 정책에 따라 Default, Ephemeral, Ba.. 2022. 9. 13. [네트워크] TCP 3-way handshake / 4-way handshake TCP 3-way handshake란 ? 연결하고자 하는 두 장치 간의 논리적 접속을 성립하기 위해 사용하는 연결 확인 방식으로 3번의 확인 과정을 거친다고 해서 3-way handshake라고 합니다. 간단하게 표현하자면 다음과 같습니다. A → B : 내 말 들려 ? B → A : 잘 들려. 내 말은 들려 ? A → B : 잘 들려. SYN (synchronize sequence numbers) 연결 확인을 위해 보내는 무작위의 숫자값입니다. 무작위의 숫자값을 사용하는 이유는 ? Connection을 맺을 때 사용하는 포트는 유한 범위 내에서 사용하고 시간이 지남에 따라 재사용됩니다. 그러므로 두 통신 호스트가 과거에 사용된 포트 쌍을 사용할 가능성이 존재합니다. 서버 측에서 패킷의 SYN을 보고 패.. 2022. 9. 13. [iOS] strong / weak / unowned / 순환 참조 strong (강한 참조) 인스턴스의 주소값이 변수에 할당될 때, RC가 증가하면 strong(강한 참조)입니다. default값이 strong이므로 지금까지 우리는 자연스럽게 인스턴스를 생성하고 사용하던 것이 전부 strong이었던 것입니다. 이러한 strong에도 문제점이 있는데 그것이 바로 순환 참조입니다. 순환 참조 순환 참조가 발생할 경우, 영구적으로 메모리가 해제되지 않을 수 있습니다. 예시로 순환 참조의 경우에 대해 알아봅시다. class Student { var name: String var teacher: Teacher? init(name: String) { self.name = name } } class Teacher { var name: String var student: Studen.. 2022. 9. 8. 이전 1 ··· 3 4 5 6 7 8 다음
