lsh424

탐색 알고리즘? - 컴퓨터에 저장된 자료를 신속하고 정확하게 찾아주는 알고리즘 이진 탐색(binary search) 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘으로 탐색 시간 복잡도는 O(logN) 탐색 방법: 분할-정복 방법 사용 ex) 정렬된 배열 [12,15,23,48,62,98,111,130] 에서 23을 찾는다면?? 1. 가운데 값 선택 -> 48 2. 우리가 찾고자하는 23은 48 좌측에 위치함으로 탐색범위가 12~23으로 줄어듬, 줄어든 탐색범위에서 중간 값 선택 -> 15 3. 23은 15 우측에 위치, 값은 하나만 남게 되고 이 값은 23과 일치 소스코드(파이썬) def binary_search(a:list, search_key): left, right = 0, len(a) wh..

오늘 알아볼 자료구조는 리스트입니다 :) 리스트란? 순서를 가지고 일렬로 나열한 원소들의 모임으로 데이터 목록을 다루는 자료구조로 기본 연산으로는 삽입, 삭제, 탐색이 있습니다. 리스트 구현 방법 1. 배열 이용 (순차적인 메모리 공간 할당) 2. 연결 리스트 이용 (노드에 분산 저장) 리스트의 연산 init(list) - 리스트 초기화 is_empty(list) - 리스트 공백 유무 검사 is_full(list) - 리스트 포화상태 유무 검사 insert(list, pos, item) - pos 위치에 item 추가 insert_last(list, item) - 리스트 맨 끝에 item 추가 delete(list, pos) - pos 위치의 요소 제거 get_entry(list, pos) - pos 위..

이전에 시간 복잡도 O(N^2)인 정렬 알고리즘들에 대해 포스팅했었는데요. 오늘은 시간 복잡도가 O(NlogN)인 정렬 알고리즘에 대해 알아보려 합니다! 시간복잡도가 O(NlogN)인 대표적인 정렬에는 퀵 정렬, 합병 정렬, 힙 정렬이 있습니다. 1. 퀵 정렬 분할 정복(divide and conquer)기법을 사용한 정렬로, 평균적으로 아주 빠른 성능을 갖는 알고리즘입니다. 정렬 방법 1. 주어진 리스트에서 하나의 원소를 고른다. (피벗) 2. 피벗을 기준으로 두 개의 파티션으로 분할한다. 파티션 1: 피벗보다 작은 원소, 파티션 2: 피벗보다 큰 원소 3. 분할된 파티션에 대해서도 리스트의 크기가 0 혹은 1이 될 때까지 1,2 과정을 반복한다. 소스코드(파이썬) def quick_sort(a: li..

www.raywenderlich.com/34-design-patterns-by-tutorials-mvvm 에 나오는 내용을 기반으로 번역 + 제가 공부한 내용을 토대로 정리했습니다. 혹시라도 잘못된 부분이 있다면 댓글로 남겨주세요 :) Design Patterns by Tutorials: MVVM Learn how and when to use the architecture-slash-design pattern of MVVM in this free chapter from our new book, Design Patterns by Tutorials! www.raywenderlich.com 지난번 MVC 패턴에 이어 오늘 정리할 내용은 MVVM 디자인 패턴입니다. ㅎㅎ 앞서 MVC패턴은 다양한 로직을 Cont..

방금 막 DFS/BFS 네트워크 포스팅을 했는데 알고리즘 하나 더 포스팅하려 합니다 ㅎㅎ (다른 주제로 포스팅하고 싶은데 노트북을 수리 맡긴 상황이라 알고리즘밖에 할 게 없네요 ㅜ) 바로 시작합니다. 이번에 풀어볼 문제는 역시 코딩 테스트 고득점 Kit에 들어있는 탐욕법 - 섬 연결하기입니다. programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 접근 방식: 1. 저는 가장 최소의 비용으로 섬을 연결해야 하기 때문에 가장 적은 비용이 드는 섬을 먼저 탐색하는 것이 좋을 것 같다고(?) 생각했습니다. 그래서 입력값인 costs를..

오늘 풀어볼 문제는 코딩 테스트 고득점 Kit에 들어있는 DFS/BFS - 네트워크입니다. 개인적으로는 이 문제는 여행경로와는 다르게 레벨 3치고는 엄청 쉬운 편(?) 인 것 같습니다. programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 접근 방식: 1. 주어진 2차원 배열을 갖고 그래프를 만듭니다. 2. 탐색을 해야 하므로 BFS함수를 작성합니다. 모든 탐색이 끝난 후 그래프에서 방문한 노드를 삭제해 줍니다. 한 번의 ..

인터넷: TCP/IP 프로토콜을 사용하여 정보를 주고받는 컴퓨터 통신망 인터넷 구성요소 호스트: 네트워크에 연결된 컴퓨팅 장치 (컴퓨터,서버등등..) 통신 링크: fiber, radio, satellite 등 노드 사이의 패킷을 전달하기 위한 통신 경로 패킷 스위치: 라우터, 링크 계층 스위치 라우터 - 패킷 위치를 추출하여, 그 위치에 대한 최적의 경로를 찾아 패킷을 다음 장치로 전달하는 장치, 여기서 최적의 경로란 일반적으로는 가장 빠르게 통신할 수 있는 경로를 의미 (통신 경로상 최단거리를 의미하는 건 아님!) 프로토콜 - 한 마디로 규약, 데이터 교환을 효율적으로 만드는 기능 수행 왜 이런 규약을 만드느냐!? -> 효율적인 정보 교환을 위해서, 만약 규칙이 없다면 원활한 정보 교환이 이루어지기 어..

2020/10/26 - [Swift&iOS/iOS] - [iOS] Cell을 재사용 시 생기는 문제점들과 해결 방법에 이어서 오늘은 셀을 재사용함으로써 생기는 조금 더 심화적인 문제를 다뤄보려 합니다. 이전 글에서는 셀의 index 별로 터치 됐다 안됐다를 기준으로 하트 버튼의 상태를 변경해 줬었는데요. 이제 하트 버튼이 동작하도록 해볼 예정입니다. 셀 안에 스위치, 체크박스, 하트(좋아요)와 같은 버튼등이 들어가게 되면 상황이 조금 골치 아파집니다. 셀을 재활용하기 때문에, 누르지도 않은 인덱스에 버튼이 눌려져 있다던가 아니면 눌렀는데도 버튼이 안 눌려져 있다던가... 다음 보시는 것처럼 스크롤 몇 번 해보면 아주 뒤죽박죽 난장판이 됩니다. ㅜㅜ 이 문제를 해결하기 위해서는 사용자가 버튼을 눌렀을 때 ..

우리는 테이블 뷰와 컬렉션 뷰를 설계할 때 그냥 셀을 사용하지 않고 재활용 셀(dequeueReusableCell)을 사용합니다. 왜 그냥 셀을 사용하지 않고 재활용 셀을 사용하느냐!? 만약에 우리가 테이블 뷰나 컬렉션 뷰에 표현해야 할 셀이 1만 개라고 해봅시다. 만약 셀을 재활용해서 사용하지 않는다면, 우리는 메모리에 1만 개의 셀을 갖고 있어야 합니다. 너무 메모리 관리 측면에서 비효율적이라는 것이죠. 특히나 아이폰은 유독 안드로이드 폰보다 램이 작은 거 아시죠? ㅎㅎ; 아무튼 그렇기 때문에 1만 개의 데이터를 표현하더라도 재활용 셀을 사용하면 메모리에는 화면에 보이는 10~20개의 셀만 갖고 있게 됩니다. 하지만 셀을 재활용하다 보니 생기는 문제점들이 몇 가지 있는데요. 대표적인 문제점이 바로 셀..

안녕하세요! 오늘은 메모이제이션(Memoization)에 대해 알아보려 합니다. 메모이제이션이 뭐냐?? 메모이제이션은 동일한 연산을 반복해야 할 때 이전에 연산한 값을 메모리에 미리 저장해 둠으로써 계산의 반복수행을 제거하여 프로그램 실행 속도를 향상시키는 기술입니다. 메모리에 저장해뒀다가 사용한다는 점에 있어서 캐싱의 범주에 속한다고 보면 될 것 같은데요. 메모이제이션은 어떤 함수의 인풋에 대한 아웃풋을 저장한다고 보시면 되고 (함수를 위한 캐싱), 우리가 보통 말하는 캐싱은 외부에서 들어오는 파일, 데이터를 저장해서 사용하는 용어로 생각하시면 될 것 같습니다. (혹시라도 틀린 부분이 있다면 꼭 댓글 남겨주세요!) 메모이제이션의 특징으로는, 보통 실행 속도가 빠른 알고리즘이 더 많은 메모리를 사용하듯이..