본문 바로가기

전체 글

 (224)
[알고리즘] binary search(이진 탐색/이분 탐색) 이진 탐색이란이진 탐색이란 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다.이진 탐색은 배열의 중간을 기준으로 데이터를 탐색하기 때문에 반드시 데이터가 정렬된 상태로 존재해야 한다. 이진 탐색 알고리즘 동작 설명정렬된 list에서 query item을 찾아서 위치를 return한다. 1. list를 오름차순으로 정렬한다.2. left = 0, right = n-1부터 시작한다.3. middle = (start + end) / 2라고 두고 list[middle]과 query를 비교한다. 1) query right을 middle-1로 둔다. 2) query = list[middle]이면 return middle 3) query > list[middle]이면 ..
[Python] set (집합 자료형) 집합은 중복을 허용하지 않고, 순서가 없다는 특징을 갖고 있다. 집합은 리스트 혹은 문자열을 이용해서 초기화할 수 있다. 이때 set() 함수를 이용한다. 혹은 중괄호({}) 안에 각 원소를 콤마(,)를 기준으로 구분하여 삽입함으로써 초기화할 수 있다. # 집합 자료형 초기화 방법 1 data = set([1, 1, 2, 3, 4, 4, 5]) print(data) # {1, 2, 3, 4, 5} # 집합 자료형 초기화 방법 2 data = {1, 1, 2, 3, 4, 4, 5} print(data) # {1, 2, 3, 4, 5} 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다. 집합 자료형의 연산에는 합집합, 교집합, 차집합이 있다. 집합 자료형 관련 함수 data = set([1,..
[MySQL] GROUP BY, WHERE, HAVING GROUP BY특정 컬럼을 기준으로 데이터를 그룹핑한다.SELECT 문에 있는 모든 열은 집계 함수가 되거나 GROUP BY 절에 나타나야 한다. WHERE는 GROUPING하기 전,HAVING은 GROUPING한 후의 조건이다.1. 칼럼 그룹화SELECT 칼럼 FROM 테이블 GROUP BY 그룹화할 칼럼; 2. 조건 처리 후에 칼럼 그룹화SELECT 칼럼 FROM 테이블 WHERE 조건식 GROUP BY 그룹화할 칼럼; 3. 칼럼 그룹화 후에 조건 처리SELECT 칼럼 FROM 테이블 GROUP BY 그룹화할 칼럼 HAVING 조건식; 예시유형별로 갯수를 가져오고 싶을 때 주로 사용한다.단순히 COUNT 함수로 데이터를 조회하면 전체 갯수만을 가져온다. Referen..
[알고리즘] [그래프 탐색] DFS(깊이 우선 탐색) DFS는 Depth First Search로 깊이 우선 탐색이다.현재 정점에서 갈 수 있는 정점까지 계속 탐색하는 방법이다.탐색한 정점은 다시 탐색하지 않는다.BFS에 비해 간단하나, 단순 검색 속도 자체는 BFS에 비해 느리다.모든 노드들을 탐색해야 하는 경우에 많이 사용한다.인접 행렬로 구현할 경우에는 O(N^2)의 시간복잡도를 갖고 인접 리스트로 구현하면 O(N+E)의 시간복잡도를 갖는다. 재귀함수나 스택을 사용해 구현한다.1. 스택을 사용하여 구현1) 시작점을 스택에 넣는다.2) 반복문 안에 들어간다.3) 가장 위에 있는 노드를 변수에 저장하고 pop한다.4) 현재 노드가 방문 된 노드라면 visit배열에 체크한다.5) 현재 노드와 연결된 노드 중에서 방문하지 않은 노드를 스택에 push한다.6)..
[Python] 우선순위 큐 (PriorityQueue) PriorityQueue는 heapq를 사용해 구현되어 있다. #cpython/Lib/queue.py from heapq import heappush, heappop class PriorityQueue(Queue): '''Variant of Queue that retrieves open entries in priority order (lowest first). Entries are typically tuples of the form: (priority number, data). ''' def _init(self, maxsize): self.queue = [] def _qsize(self): return len(self.queue) def _put(self, item): heappush(self.queue..
객체지향 프로그래밍 들어가며 기상청 데이터 수집을 요청받았다. 한 곳의 기상청의 데이터만을 수집하면 된다고 생각했고 프로젝트 기간동안만 사용할 것이라고 생각해서 코드가 돌아가게만 구현했다. 하지만 이후에 다른 2곳의 기상청 데이터도 수집을 요청 받게 되었고 기존에 짰던 코드와 비슷한 코드가 반복해서 생성되게 되었고 처음 해당 코드를 접하는 사람은 코드를 이해하기 쉽지 않아 보였다. 따라서 리펙토링이 필요해보였고 유지보수가 용이하게 리펙토링을 하기 위해 객체지향에 대해 다시 공부하게 되었다. 객체는 기능으로 정의 메서드를 이용해서 기능 명세 객체와 객체는 기능을 사용해서 연결 - 기능 사용 = 메서드 호출 - 객체와 객체 상호 작용: 메시지를 주고 받는다고 표현 캡슐화 - 데이터 + 관련 기능 묶기 - 객체가 기능을 어떻게 ..
[알고리즘] 다이나믹 프로그래밍 (DP) 다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누고 그 작은 부분 문제들이 반복되는 것을 이용하여 풀어가는 방법이다. 모든 작은 문제들을 단 한번만 풀어야 하며, 그 결과를 어딘가 기록해 둠으로써 재사용한다. 부분 문제를 푸는 순서에 따라서 Top-Down과 Bottom-up으로 나뉜다. 메모이제이션은 자꾸만 반복되지만 그 결과값은 변하지 않는 작은 ㅁ누제들의 결과값을 저장하는 것을 의미한다. 메모이제이션을 통해 이미 결과값이 기록되는 특정 문제가 반복될 때, 불필요한 계산은 패스하고 기록되어 있는 값만 불러오면 아주 빠르게 해결할 수 있다.
[네트워크] OSI 7 Layer 1. Physical Layer 0과 1의 나열로 아날로그 신호로 바꾸어 전선으로 흘려보내고, (encoding) 아날로그 신호가 들어오면 0과 1의 나열로 해석하여 (decoding) 물리적으로 연결된 두 대의 컴퓨터가 0과 1의 나열을 주고받을 수 있게 해주는 모듈(module) PHY칩이라는 것으로 하드웨어적으로 구현되어 있다. 2. Data Link Layer 같은 네트워크에 있는 여러 대의 컴퓨터들이 데이터를 주고받기 위해서 필요한 모듈 ex. Framing Data Link Layer는 LAN카드에 구현되어 있다. 즉, 2계층 모듈도 1계층 모듈처럼 하드웨어적으로 구현되어 있다. 3. Network Layer 수 많은 네트워크들의 연결로 이루어지는 inter-network 속에서어딘가에 있는 ..

티스토리툴바