오도원입니다.

건강과 행복을 위하여

반응형

전체 글 305

Algorithm. 문자열 - 문자열 매칭

1. 문자열 처리 예제) 다음 중 x안에 y가 존재하는지 찾아보자. 2. 문자열 매칭(패턴 매칭) 텍스트 문자열(t)에서 패턴 문자열(p) 포함 여부를 찾는 것. 고지식한 패턴 검색 알고리즘 카프-라빈 알고리즘 KMP 알고리즘 보이어-무어 알고리즘 파이썬의 패턴 매칭 3. 고지식한 알고리즘(Brute Force) 텍스트 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작 # t : 텍스트 # p : 패턴 # N : 텍스트의 길이 # M : 패턴의 길이 def BruteForce(t, p): N = len(t); M = len(p) i = 0 # 텍스트 인덱스 j = 0 # 패턴 인덱스 while i < N and j < M: if t[i] != p[i]: # 다..

Algorithm. 문자열 - 해싱

자주 수행되는 작업들 디렉토리 경로 따라가기 디렉토리 내에 존재하는 파일들 나열하기 특정 파일의 존재 유무 판별하기 해당 작업들은 시스템의 성능 저하의 원인이 된다. 이 작업들은 검색에 기반해서 수행되는 작업들이므로 어떻게 해결해야할까. 1. 해싱 특정 항목 검색 시, 탐색 키에 대한 산술적 연산으로 키가 있는 위치를 계산하여 바로 찾아가는 방법이다. O(1) 시간 복잡도 1. 직접 번지 테이블 직접 번지 테이블(배열)에 저장하는 경우 전체 키(key)들의 집합(U)이 작은 경우에 효율적이다. 키 k가 테이블(T)에서 위치 k에 저장 테이블(배열)의 크기 = 집합 U의 크기 그러나 전체 키 값들의 집합 U가 클 때, 현실적인 컴퓨터 메모리 공간에서 테이블 T를 생성하는 것은 불가능하다. 또한 실제 저장되..

04-1. 대중교통 공공데이터

1. 대중교통 데이터 내려받기 https://pay.tmoney.co.kr/index.dev 티머니 카드&페이 티머니카드, 어린이/청소년할인, T마일리지적립, 소득공제, 유통/교통/모바일결제, 고속/시외버스예매 pay.tmoney.co.kr 1. 이용안내 선택 2. 대중교통 통계자료 선택 3. 2020년 4월 교통카드 통계자료 선택 4. 월간 교통카드 통계자료 다운로드 이제 다운받은 엑셀 파일을 살펴보자. 버스정류장별 이용현황 지하철 노선별 역별 이용현황 지하철 유무임별 이용현황 지하철 시간대별 이용현황 이렇게 4가지의 통계자료를 볼 수 있다. 가장 먼저 활용할 데이터는 '지하철 유무임별 이용현황' 데이터이다. 2. 지하철 유무임별 이용현황 데이터 정제하기 지하철 유무임별 이용현황 시트를 선택하고 'su..

아름다운 것은 먼 곳에 있다

가장 단순하면서도 쉬운 요리라고 할 수 있는 라면조차도 '라면을 맛있게 끓이는 법'이라고 인터넷을 검색하면 수십가지의 레시피가 검색되는 시대이다. 삶의 의식주와 가치, 모든 것이 메뉴얼화 되어가는 듯한 세상에서 우리는 살아가고 있다. 이러한 세상에서 도대체 우리는 어떠한 삶의 태도로 살아가야할까.

Algorithm. 2주차 스터디 정리

1. 백트래킹 2. 그래프의 기본과 탐색 3. 그래프의 최소 비용 문제 1. 백트래킹 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾는다. 2. 그래프의 기본과 탐색 객체들 사이의 연결 관계 표현 정점(vertex)집합과 정점을 연결하는 간선(edge)집합으로 구성 1) 깊이 우선 탐색(DFS) 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 2) 너비 우선 탐색(BFS) 시작 정점에서 인접한 정점을 먼저 모두 차례로 방문 3. 그래프의 최소 비용 문제 프림 알고리즘 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘 크루스칼 알고리즘 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 다익스트라 알고리즘..

Algorithm. 3주차 스터디 계획

3주차 스터디 계획 https://swexpertacademy.com/main/learn/course/subjectList.do?courseId=AVuPDYSqAAbw5UW6 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이번 주 공부할 내용은 문자열 탐색입니다! 파이썬은 타 언어에 비해서 문자열을 다루는데 굉장히 강력한 언어입니다. 그러면 이러한 파이썬의 특성을 이용해서 문자열 탐색을 공부해봅시다. 1. 문자열 탐색 1) 학습 목표 1. 해싱에 대한 기본 개념에 대해 이해한다. 2. 문자열에서 패턴을 탐색하는 주요한 알고리즘에 대해 이해한다. 3. 트라이, 접미어 트리, 접미어 배열에 대해 학습하고 문자열 ..

Algorithm. 그래프 - 다익스트라 알고리즘

https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 최단 경로 간선의 가중치가 있는 directed graph가 있을 때, 두 정점 사이의 경로들 중 간선의 가중치가 합이 최소인 경로 단일 시작점 최단 경로 문제 출발점에서 다른 모든 정점들에 이르는 최단경로를 구하는 문제 다익스트라 알고리즘 : 음의 가중치 허용 안함. 밸만 포드 알고리즘 : 음의 가중치 허용, 음의 사이클은 허용 안함 모든 쌍 최단 경로 문제 모든 정점 쌍 간의 최단 경로를 구하는 문제 플로이드-워샬 알고리즘 : 동적계획..

Algorithm. 그래프 - 크루스칼 알고리즘

1. 크루스칼 알고리즘 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 정점이 n개인 그래프에서 n-1개의 간선을 선택하는 방식 초기 상태는 n개의 정점들이 하나의 트리가 된다. 하나의 정점을 포함하는 n개의 상호 배타 집합이 존재 간선을 선택하면 간선의 두 정점이 속한 트리가 연결되고 하나의 집합으로 합쳐진다. 사이클이 생기면 안된다. 두 정점이 같은 집합의 원소인지 검사해야한다. 동작과정 최초, 모든 간선을 가중치에 따라 오름차순 정렬 최소 가중치 간선부터 선택하면서 트리 증가 사이클이 존재하면 다음 가중치 낮은 간선 선택 n-1개의 간선이 선택될 때 까지 (2) 반복 소스코드 # G : 그래프 def mst_kruskal(G): mst = [] # 선택된 간선 집합, 공집합으로 ..

Algorithm. 그래프 - 프림 알고리즘

1. 프림 알고리즘 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘 임의의 정점을 하나 선택해서 시작 선택한 정점들과 인접한 정점들 중 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때 까지 (2) 반복 두 종류의 상호 배타 집합(disjoint set)이 필요 트리 정점 : 최소 신장 트리에 선택된 정점들 비트리 정점 : 선택되지 않은 정점들 소스코드 # G : 그래프 # s : 시작 정점 def mst_prim(G, s): key = [INF] * N # 가중치를 무한대로 초기화 pi = [None] * N # 트리에서 연결될 부모 정점 초기화 visited = [False] * N # 방문 여부 초기화 key[s] = 0 # 시작 정점의 가중치를 0으로 ..

Algorithm. 그래프 - 최소 신장 트리

1. 그래프 최소 비용 문제 : 최소 신장 트리 문제 vs 최단 경로 문제 최소 신장 트리 문제 가중치 그래프에서 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제 최단 경로 문제 시작 정점에서 목표 정점까지 가는 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제 2. 신장 트리(Spanning Tree) 정점인 n개인 undirected graph에서 n개의 정점과 n-1개의 간선으로 구성된 트리 즉, 모든 vertex set을 포함해야한다. 신장 트리의 수는 정점의 개수와 간선의 수의 비례한다. 3. 최소 신장 트리(Minimum Spanning Tree) 가중치 그래프의 신장 트리 중 간선들의 가중치의 합이 최소인 신장 트리 프림 알고리즘과 크루스칼 알고리즘이 존재한다.

03-4. 인구 공공데이터 - 산점도

지금까지의 그래프는 다음과 같다. 위의 그래프는 연령대별 성별 비율을 알아보기 힘들다. 1. 꺾은선 그래프로 표현하기 남성 데이터와 여성 데이터를 서로 다른 색의 꺾은선 그래프로 표현해보자. file = open('gender.csv') data = csv.reader(file) m = [] f = [] name = input('지역 입력 => ') for row in data: if name in row[0]: for i in range(3, 104): m.append(int(row[i].replace(',', ''))) # 남성 데이터 저장 f.append(int(row[i+103].replace(',', ''))) # 여성 데이터 저장 break plt.plot(m, label='Male') plt..

03-3. 인구 공공 데이터 - 파이차트

1. 우리 동네 인구 구조를 파이 차트로 나타내기 제주도의 남녀 성별 비율을 barh()그래프로 나타내보자. import csv import matplotlib.pyplot as plt file = open('gender.csv') data = csv.reader(file) m = [] f = [] name = input('지역 입력 => ') for row in data: if name in row[0]: for i in row[3:104]: m.append(-int(i.replace(',',''))) for i in row[106:]: f.append(int(i.replace(',', ''))) plt.style.use('ggplot') plt.figure(figsize=(10,5), dpi=300)..

Algorithm. 그래프 - 상호배타 집합

1. 서로소 또는 상호배타 집합(Disjoint set) 교집합이 없는 집합 집합에 속한 특정 원소로 각 집합을 구분 대표자(representative) 상호배타 집합 표현 연결 리스트, 트리 2. 상호배타 집합 연산 Make-Set(x) : 원소 x만 속한 집합을 생성 Find-Set9x) : 원소 x가 속한 집합을 알아내는 연산, 해당 집합의 대표자를 반환 Union(x, y) : 원소 x가 속한 집합과 원소 y가 속한 집합을 합치는 연산, 대표자는 본인이 설정 3. 연결 리스트 표현 같은 집합의 원소들을 하나의 연결 리스트로 관리 연결리스트의 첫번째 원소가 집합의 대표원소 각 원소는 대표원소를 가리키는 링크를 갖는다. 4. 트리 표현 집합(disjoint set)을 하나의 트리로 표현 자식 노드가 ..

Algorithm. 그래프 탐색

1. 그래프 탐색 그래프의 모든 정점을 빠짐없이 탐색 2. 깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS) 깊이 우선 탐색(DFS) 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 시작 정점에서 한 방향을 선택해서 다음 정점으로 이동 선택된 정점에서 (1)을 반복 수행하면서 계속 깊이 탐색 이미 방문한 정점은 재방문 안한다. 더 이상 갈곳이 없으면 부모노드로 되돌아가 다시 깊이 탐색 스택을 사용한다 DFS 재귀 호출 # G : 그래프 # v : 시작 정점 # visited : 정점의 방문 여부, False로 초기화 # G[v] : 그래프 G에서 v의 인접리스트 def dfs(G, v): visited[v] = True # v를 방문 표시 visi..

Algorithm. 그래프 기본

1. 친구관계 A와 B는 친구를 (A - B)로 표현 2. 그래프 객체들 사이의 연결 관계 표현 정점(vertex)집합과 정점을 연결하는 간선(edge)집합으로 구성 G = (V, E) |V| : 정점 수, |E| : 간선 수 |V| = n개의 정점은 최대 C(n, 2) = n*(n-1)/2 개의 간선이 가능 3. Directed Graph vs Undirected Graph Undirected Graph 서로 대칭적이지 않은 관계 기업간의 공급관계, 작업의 선후 관계 등을 표현 4. 가중치 그래프(Weighted Graph) 간선에 비용이 추가된 그래프 5. 용어 인접(adjacency) : 두 정점 사이에 간선이 존재할 경우 인접하다고 한다. 완전 그래프 : 모든 정점이 인접한 그래프 부분 그래프 :..

Algorithm. 백트래킹 - 동전 거스름돈

1. 동전 거스름돈 총금액 800, 동전 종류 : 10, 50, 100, 400, 500 그리디 : 500, 100, 100, 100 -> 최적해가 아니다 소스코드 # coin[] : 동전의 금액을 젖아 # choice[] : 선택한 동전 집합 # best : 거스름돈에 대한 최소 동전 개수 def coinChange(choice, N, money): global best if best N best = N else: for i in range(len(coin): if money - coin[i] >= 0: choice[N] = coin[i] coinChange(choice, N+1, money-coin[i])

Algorithm. 백트래킹 - 순열

1. 순열 예시) 원소 개수 n = 4 -> 집합 = {A, B, C, D}, 4!인 24가지의 경우가 존재 따라서 상태 공간 트리에서의 단말노드의 수는 24개이다. 24개의 후보해가 존재한다는 것이고 이것은 단말노드의 수와 같다. 노드 방문 시마다 원소를 가리키는 인덱스 값을 저장 같은 원소 수를 갖는 부분집합과 순열의 상태 공간 트리의 높이는 같다. 순열의 경우 높이가 다른 노드는 선택지 수가 동일하지 않다. 선택할 때마다 다음 선택의 선택지 수가 하나씩 줄어든다. 소스코드 # order[] : 순열의 순서를 저장하는 리스트 def permutation(order, k, n): if k == n: # 다 선택하면 print_order_array(order, n): # 출력 else: check = [..

Algorithm. 백트래킹 - 부분집합

1. Power set 집합의 모든 부분집합 (공집합, 자기자신 포함) 집합의 원소개수가 n => 부분집합의 개수는 2^n 1 또는 0 값을 가지는 비트열 리스트로 부분집합 표현 소스코드 # a[0, ... , n-1] : 집합에 대한 비트표현 저장, 크기는 원소의 수 # k : 선택한 횟수(현재 노드의 높이) # n : 모든 선택 수(트리의 높이) def subset(a, k, n): if k == n: # 모든 선택이 끝난 상태 (단말노드 도착) process_solution(a, n) # else: a[k] = 0 # k번째 원소 포함 안하는 경우 subset(a, k+1, n) a[k] = 1 # k원소 포함하는 경우 subset(a, k+1, n) 백트래킹 구현은 상태공간트리와 동일한 함수호출트..

Argorithm. 백트래킹

1. n-Queens 문제 n x n 체스판에서 n개의 퀸들을 서로 위협하지 않도록 배치하는 문제 2. 백트래킹 초기 상태에서 목표 상태로 가는 경로를 탐색하는 기법 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾는 기법 최적화(optimize)문제와 결정(decision)문제를 해결할 수 있다. 최적화 문제 미로 찾기, Subset sum 등 결정 문제 n-Queen, Map coloring 등 루트까지 되돌아갔는데 더이상 선택지가 없다면 답이 없는 것이다. 백트래킹의 핵심은 상태 공간 트리를 탐색하는 것! 해를 찾기 위한 선택의 과정을 트리로 표현 트리의 내부 노드는 해로 가는 중간 상태 트리의 단말 노드는 하나의 후보해에 대한 최종 상태 상태 공간 트리를 깊이 우선 탐색(DFS)하는 방법이 백..

반응형