exp_blog

1. Numpy 모듈 활용한 데이터 관리

• C언어로 구현된 파이썬 라이브러리
• 고성능 수치 계산 위해 제작
•  벡터, 행렬 연산에 있어 편리한 기능
• 데이터분석 라이브러리인 pandas와 matplotlib 의 기반으로 사용

cmd>> pip install numpy

#소스 코드에 import
import numpy as np #as np는 별명

2. Numpy 모듈 사용하기

1) Array 생성, 조회

arr = np.array([[1,2,3], [4,5,6], [7,8,9]])
arr

>>>arr([[1,2,3],
	[4,5,6],
        [7,8,9])

#array의 형태(크기)를 확인할 수 있다
arr.shape
>>>(3, 3)

#array의 자료형을 확인할 수 있다.
arr.dtype
>>>dtype('int64')

2) Array 연산 가능 

arr1 + arr2
arr1 / arr2
arr1 * arr2
arr1 - arr2

3) Array 생성, 조회

arr1 = np.arrange(10)
arr1 
>>>array([0,1,2,3,4,5,6,7,8,9])


arr1[0]
>>>0

arr1[3:9]
#3번째 요소부터 8번째 요소
>>>arr1([3,4,5,6,7,8])

arr1[:]
>>>>>>array([0,1,2,3,4,5,6,7,8,9])

4)numpy 모듈의 주요 함수

- 난수 발생 함수 : np.random.rand(5,3)

- 각 성분 절대갑 계산 : np.abs(arr1)

- 각 성분 제곱 계산 : np.square(arr1)

- 각 성분의 소수 첫 번째 자리에서 올림한 값 계산 : np.ceil(arr1)

- 각 성분의 소수 첫 번째 자리에서 내림한 값 계산 : np.floor(arr1)

- 각 성분이 NaN인 경우 True를, 아닌 경우 False를 반환하기 : np.isnan(arr1)

- 각 성분이 무한대인 경우 True를, 아닌 경우 False를 반환하기 : np.isinf(arr1)

- 각 성분에 대해 삼각함수 값 계산(cos / cosh / sin / sinh/ tan / tanh) : np.cos(arr1)

- 전체 성분에 대해 오름차순 정렬 : np.sort(arr1)

- 전체 성분에 대해 내림차순 정렬 : np.sort(arr1)[::-1]

- 행 방향으로 오름차순으로 정렬 : np.sort(arr1, axis = 0)

5)Numpy 모듈 주요 통계 함수 

- 전체 성분 합 계산 : np.sum(arr1)

- 열 간의 합을 계산 : np.sum(arr1, axis  = 1)

- 행 간의 합을 계산 : np.sum(arr1, axis = 0)

- 전체 성분의 평균 계산 : np.mean(arr1)

- 행 간 평균 계산 : np.mean(arr1, axis = 0)

- 전체 성분의 표준 편차, 분산, 최소값, 최대값 계산(std, var, min, max) : np.std(arr1)

- 전체 성분의 최소값, 최대값이 위치한 인덱스를 반환 (argmin, argmax) : np.argmin(arr1)

- 맨 처음 성분 부터 각 성분까지의 누적합 / 누적곱 계산(cumsum , cumprod) : np.cumsum(arr1)

3. Pandas 모듈 활용한 데이터 관리

- 정형 데이터 관리 시 사용

cmd>> pip install pandas

1) 주요 데이터 유형

2) Series 유형 : 생성하기

3) Series 유형 : 조회하기 

4) Series 유형 : 데이터 연산

5) Dataframe 유형 : 생성

6) Dataframe 유형 : 정렬

7) Dataframe 유형 : pandas에서 xls형식과 csv 형식 불러오기 (pip install xlrd 작업 후 )

8) DataFrame 유형 : 특정 컬럼 조회

9) DataFrame 유형 : 원하는 조건으로 조회 

10) Dafa Frame 유형 : 새로운 행과 열 추가하기

11) Data Frame 유형 : 행과 열 삭제하기

데이터를 행 단위로 가져오려면 판다스에서 제공하는 함수 사용

• loc : 인덱스 기준으로 행 데이터 읽기
• iloc : 행 번호를 기준으로 행 데이터 읽기

현재는 데이터가 숫자 형식으로 정렬되어 있어 행 번호 처럼 보이지만,

인덱스는 문자열로 지정할 수 있고, 숫자도 다르게 지정할 수 있습니다. 

인덱스 2를 삭제하면 행번호는 0번부터 시작해서 순서대로 이어지지만

인덱스는 그렇지 않다

loc 로 행 추출하기

-0번 인덱스 데이터 가져오기

import pandas as pd
comment1 = pd.read_excel('C:/Users/USER/Desktop/연습문제/댓글내용.xlsx')

print(comment1.loc[0])

번호 1
댓글내용 첫번째 댓글입니다
Name: 0, dtype: object

여러 개의 인덱스에 해당하는 행 데이터 추출

-만약,  1 , 2 인덱스의 데이터를 한꺼번에 가져오고 싶으면

리스트에 원하는 인덱스를 담아 loc 속성에 전달

import pandas as pd
comment1 = pd.read_excel('C:/Users/USER/Desktop/연습문제/댓글내용.xlsx')

print(comment1.loc[[0,1]])

 번호   댓글내용
0  1    첫번째 댓글입니다
1  2    두번째 댓글입니다

iloc 속성으로 행 데이터 읽어오기

행 번호를 통해 행 데이터를 가져온다

데이터프레임명.iloc[행번호]

print(comment1.iloc[0])

음수를 사용해서 데이터를 추출할 수도 있다

print(comment1.iloc[-1])

iloc를 통해 여러개의 행 데이터 가져오기

원하는 행 번호를 리스트에 담아 전달

iloc같은 경우는 행과 열 인덱스에 정수리스트를 전달해야 한다

print(comment1.iloc[[0,-1]])

loc, iloc를 통해 행과 열 데이터 가져오기

모든 행(:) 에 대해 'year' 과 'continent' 열 데이터만 가져와라

( : ) 모든 데이터를 가져와라 

print(df.loc[:,['year', 'continent']])

모든 행에 대하여 3번열 데이터 전까지 country(0), continent(1), year(2)의 열데이터만 출력

print(df.iloc[:,:3])

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

#BFS로 미로 탈출 알고리즘 정의
def bfs(maze, i, j, N, M):
    visited = [] #방문한 노드
    queue = [[i, j]] #BFS로 사용될 큐
    distance = [[0 for _ in range(M)] for _ in range(N)] #해당 지점까지의 거리를 담는 리스트
    distance[0][0] = 1 #첫 시작은 1
    
    while queue: 
        [i, j] = queue.pop(0) #BFS 큐에 넣어줌
        visited.append([i, j]) #방문 리스트에 쌓아줌
        
        #상하좌우 탐색
        if i < N-1 and maze[i+1][j] == 1 and [i+1, j] not in visited and [i+1, j] not in queue:
            queue.append([i+1, j])
            distance[i+1][j] = distance[i][j] + 1
        if j < M-1 and maze[i][j+1] == 1 and [i, j+1] not in visited and [i, j+1] not in queue:
            queue.append([i, j+1])
            distance[i][j+1] = distance[i][j] + 1
        if j > 0 and maze[i][j-1] == 1 and [i, j-1] not in visited and [i, j-1] not in queue:
            queue.append([i, j-1])
            distance[i][j-1] = distance[i][j] + 1
        if i > 0 and maze[i-1][j] == 1 and [i-1, j] not in visited and [i-1, j] not in queue:
            queue.append([i-1, j])
            distance[i-1][j] = distance[i][j] + 1
            
    return distance[N-1][M-1] #마지막 도착지의 거리를 반환

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1

7

6

1 2

2 3

1 5

5 2

5 6

4 7

예제 출력 1

4

n = int(input())
m = int(input())
adj = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
count = 0

for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

    
def dfs(now_pos):
    global count
    count += 1
    visited[now_pos] = True
    for next_pos in adj[now_pos]:
        if not visited[next_pos]:
            dfs(next_pos)
dfs(1)
print(count - 1)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1

5 17

예제 출력 1

4

from collections import deque
MAX = 100001
n, k = map(int, input().split())
array = [0] * MAX

def bfs():
    q = deque([n])
    while q:
        now_pos = q.popleft()
        if now_pos == k:
            return array[now_pos]
        for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2):
            if 0 <= next_pos < MAX and not array[next_pos]:
                array[next_pos] = array[now_pos] + 1
                q.append(next_pos)


>>>print(bfs())

생각해봤는데 dfs 랑 bfs를 언제쓸까라는 생각을 해보았다

결론적으로

• DFS :  방문해야하는 노드의 수가 많고 / 모든 노드의 수를 방문해야할 때
• BFS : 최단 거리 등 내가 원하는 노드만 방문해야할 때

이렇게 나눠서 쓰는게 맞는 거 같다 ㅎㅎ

1.이진 탐색 (Binary Search)

• 탐색할 자료 둘로 나누어 해당 데이터가 있을만한 곳 탐색
• 순차탐색과 비교해보면 이진탐색이 훨씬 더 효율적인 것을 알 수 있다

[저작자] by penjee.com

2. 분할정복 VS 이진 탐색

• 분할 정복 알고리즘(Divide and Conquer)
  • 분할 : 문제를 하나 또는 둘 이상으로 나눔
  • 정복 : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결 , 그렇지 않다면 다시 나눔
• 이진 탐색
  • 이진 : 리스트를 2개의 서브 리스트로 나눔
  • 탐색
    • 검색할 숫자(search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자 찾는다
    • 검색할 숫자(search) < 중간값 이면, 앞 부분 서브 리스트에서 검색할 숫자 찾는다

3. 코드 생성

-> 이미 정렬되어 있는 상태에서 진행해야 함

• [2,3,8,12,20] 일 때,
  • b_search(data_list , find_data) 함수 생성
    • find_data  : 찾는 숫자
    • data_list : 데이터 리스트
    • data_list의 중간값을 find_data와 비교
      • find_data < data_list[mid] 이면
        • 맨 앞부터  data_list[mid] 에서 다시 find_data 찾기
      • find_data > data_list[mid] 이면
        • data_list[mid] 부터 맨 끝까지 다시 find_data 찾기
      • 그렇지 않으면, data_list[mid] = find_data 이므로 
        • return data_list[mid]

4. 알고리즘 구현

def b_search(data, search):
	print(data)
    if len(data) == 1 and search == data[0]:
    	return True
    if len(data) == 1 and search != data[0]:
    	return False
    if len(data) == 0:
    	return False
    
    
    mid = len(data)//2
    
    if search == data[mid]:
    	return True
    else: 
    	if search > data[mid]:
        	return b_search(data[mid+1:], search)
        else:
        	return b_search(data[:mid], search)


import random
data_list = random.sample(range(100), 10)
>>>data_list.sort()
>>>[2, 5, 19, 21, 42, 47, 67, 72, 92, 98]

>>>b_search(data_list, 67)
>>>[2, 5, 19, 21, 42, 47, 67, 72, 92, 98]
>>>[67, 72, 92, 98]
>>>[67, 72]
>>>[67]
>>>True

5. 알고리즘 분석

-> n 개의 리스트를 매번 2로 나누어 1이 될 때까지 비교 연산 k회 진행하기 때문에

     k + 1 

1. 순차 탐색 이란?

• 데이터가 담겨있는 리스트를 앞에서 부터 하나씩 비교해서 원하는 데이터 찾는 방법

2. 연습

• data_list에 렌덤으로 10 개가 들어있을 때, 원하는 데이터의 위치를 리턴하는 순차탐색 알고리즘 작성
  • 원하는 데이터가 리스트에 없으면 -1 리턴

from random import *

data_list = list()
for num in range(10):
	data_list.append(randint(1,100))
    
>>>data_list
>>>[100, 87, 79, 14, 35, 84, 77, 88, 37, 61]

def sequencial(data_list, search_data):
	for index in rnage(len(data_list)):
    	if data_list[index] == search_data:
        	return index
    return -1


>>> sequencial(data_list, 77)
>>> 6

3. 알고리즘 분석

최악의 경우 리스트 길이가 n일 때, n번 비교해야 함

• O(n)

 map : 리스트의 요소를 지정된 함수로 처리해주는 함수

              원본 리스트를 변경하지 않고 새 리스트를 생성

• list(map(함수, 리스트))
• tuple(map(함수, 튜플))

ex)

>>> a = [1.2, 2.5, 3.7, 4.6]
>>> a = list(map(int, a))
>>> a
[1, 2, 3, 4]

모든 반복 가능한 객체를 넣을 수 있음

ex) range를 사용해서 숫자를 만든 뒤 숫자를 문자열로 변환

>>> a = list(map(str, range(10)))
>>> a
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

x = input().split()    # input().split()의 결과는 문자열 리스트
m = map(int, x)        # 리스트의 요소를 int로 변환, 결과는 맵 객체
a, b = m               # 맵 객체는 변수 여러 개에 저장할 수 있음