Python

8. 다이나믹 프로그래밍

다이나믹 프로그래밍 (동적계획법) 메모리 공간을 약간 더 사용하여 연산속도를 비약적으로 증가시키는 방법 점화식(인접한 항들 간의 관계식)을 그대로 코드로 옮겨서 구현할 수 있다. (피보나치 수열) 이미 계산된 결과(부분 문제)를 별도의 메모리에 저장하여 다시 계산하지 않도록 한다. 구현은 일반적으로 두가지 방식(top-down / bottom-up)으로 구성된다. Top-down: 재귀함수를 이용하여 큰 문제 해결을 위해 작은 문제를 호출하는 방식 Bottom-up: 단순히 반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 문제를 모아 큰 문제를 해결하는 방식 (전형적인 형태) 결과 저장용 리스트는 DP 테이블이라고 불린다. DP 사용 조건 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모..

자료형

리스트 1. 선언, 입력 변수명 = [] or list() 변수명 = [데이터1, 데이터2, ...] 2. 읽기 변수명[인덱스번호] 3. 추가 변수명.append(데이터) 변수명.insert(인덱스번호, 데이터) 4. 삭제 변수명.remove(데이터) del 변수명[인덱스번호] 5. 수정 변수명[인덱스번호] = 수정할값 ▷ 관련 함수들 append(): 요소 추가 a = [1,2,3] a.append(4) a >> [1,2,3,4] sort() / sorted(): 리스트 정렬 sort, sorted 모두 key, reverse 매개변수를 갖고 있다. reverse에는 bool값을 넣고, 디폴트는 reverse=False(오름차순)이다. key에는 정렬을 목적으로 하는 함수를 넣을 수 있고, lambda..

파이썬의 self

클래스 붕어빵 틀 변수와 함수를 묶어서 하나의 새로운 객체(타입)으로 만드는 것 인스턴스 붕어빵 (슈붕파 손들어~) 붕어빵 틀에 반죽을 넣어 만들어진 붕어빵 class BusinessCard: def set_info(self,name,email,addr): self.name=name self.email=email self.addr=addr → set_info 메서드는 네 개의 인자를 받는데 name,email,addr은 사용자로부터 받은 데이터를 메서드로 전달할 때 사용되는 인자이다. 그렇다면 self는 무엇일까? 클래스 내부에 정의된 함수(메서드)의 첫번째 인자는 반드시 self여야 한다. class Foo: def func1(): print("func 1") def func2(self): print(..

Union-Find 알고리즘

Union-Find 서로소 집합 자료구조 (서로소: 공통 원소가 없는 두 집합) union: 2개 원소로 이루어진 집합을 하나의 집합으로 합치기 find: 특정 원소가 속한 집합이 무엇인지 알려주기 동작 방법 union 연산 서로 연결된 두 노드를 확인 A의 루트노드 A'와 B의 루트노드 B'를 찾기 (find) 모든 union 연산을 처리할 때까지 1과정 반복 구체적인 알고리즘 동작 방법은 다음과 같다. 부모 테이블 초기화 노드 개수 크기의 부모 테이블을 만들어 초기화한다. (초기값은 자기 자신을 부모로 갖도록 설정) 각각의 union 연산을 확인 union(1,4): 1과 4의 루트노드를 각각 찾아 둘 중 더 작은 값으로 둘의 부모노드 값을 변경 코드 구현 # 특정 원소가 속한 집합 찾기 def fi..

2) 탐색&시뮬레이션

1. 회문 문자열 검사 해답 #1: 문자열을 하나씩 s에 입력받아 s의 len 절반만큼 for문을 돌아 앞과 뒤의 문자를 비교해준다. n = int(input()) res = [] for i in range(n): s = input() #문자열 하나씩 입력받아 처리 s = s.upper() #전부 대문자화 size = len(s) for j in range(size//2): if s[j]!=s[-1-j]: res.append("#%d NO" %(i+1)) break else: res.append("#%d YES" %(i+1)) for x in res: print(x) 해답 #2: 이게 간지다.. n = int(input()) res = [] for i in range(n): s = input() #문자열..

1) 코드 구현력 기르기

1. k번째 약수 답은 맞았는데.. 'k번째'의 약수를 구하는 것이 포인트이므로 약수 전부를 구해서 list에 추가할 필요가 없었다. cnt 변수에 약수를 구할 때마다 더해주고, cnt==k일 때 for문에서 break 처리 후 정답 출력 for-else 구문 for문에서 중간에 break로 빠져나오지 않고 끝까지 실행됐을 때, 밑에 있는 else문이 실행된다. N,K = map(int, input().split()) cnt = 0 for i in range(1,N+1): if N%i==0: cnt+=1 if cnt==K: print(i) break else: # 약수를 발견못했을 때 print(-1) 2. k번째 수 리스트 슬라이싱 사용 T = int(input()) for _ in range(T):..

기초100제 문법

역슬래시 출력 print("\\") : \ print("\"") : " print("\'") : ' print("\n") : 줄바꿈 print("\t") : 탭 구분자 split(): 문자열 사이 공백을 기준으로 자른다. split("구분자"): 구분자를 기준으로 자른다. split("구분자", maxsplit="분할횟수") // split(sep="구분자", maxsplit="분할횟수"): 구분자를 기준으로 분할횟수만큼만 자른다. 문자 변환 ord(문자): 하나의 문자를 받고 해당 문자에 해당하는 유니코드 정수를 반환 ex) ord('a') -> 97 chr(정수): 하나의 정수를 받고 해당 정수에 해당하는 유니코드 문자를 반환 ex) chr(97) -> 'a' if문 파이썬에서의 조건문은 if ~ e..

투 포인터

투포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두개의 점 위치를 기록하면서 처리하는 알고리즘이다. 리스트에 담긴 데이터에 순차적으로 접근할 때 시작점과 끝점, 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 특정한 합을 갖는 부분 연속 수열 찾기 투 포인터를 활용하여 다음의 알고리즘으로 문제를 해결할 수 있다. 시작점과 끝점이 첫번째 원소의 인덱스(0)을 가리키게 한다. 현재 부분합이 M과 같으면 count 한다. 현재 부분합이 M보다 작으면 end를 1 증가시킨다. 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다. 모든 경우를 확인할 때까지 2~4번 과정을 반복한다. n = 5 # 데이터의 개수 m = 5 # 찾고자하는 부분합 data = [1,2,3,2,5] cnt = ..

Open API를 활용한 크롤링

Open API(Rest API) API: Application Programming Interface의 약자 응용 프로그램에서 사용할 수 있도록 운영체제나 프로그래밍 언어가 제공하는 기능을 제어할 수 있게 만든 인터페이스 애플리케이션이 인터페이싱(요청과 응답을 주고받는) 체계 API를 통해 소스 및 데이터베이스는 접근하지 못하게 하고, 해당 프로그램을 사용할 수 있도록 기능을 제공 Open API: 공개 API라고 불리며, 누구나 사용할 수 있도록 공개된 API (주로 Rest API 기술을 많이 사용) Rest API: Representational State Transfer API의 약자 HTTP 프로토콜을 통해 서버 제공 기능을 사용할 수 있는 함수 일반적으로 XML, JSON의 형태로 응답을 전..

크롤링 시 문제상황 대처

[기존] urllib + bs4 → [최근] requests + bs4 경우에 따라 예전 사이트의 경우는 urllib 로만 정상적으로 데이터를 가져오는 경우가 간혹 있음 (극히 드묾) requests 라이브러리로 작성 import requests from bs4 import BeautifulSoup res = requests.get('https://~') soup = BeautifulSoup(res.content, 'html.parser') items = soup.select('요소') res는 request 받은 객체가 리턴되기 때문에 res.content로 보내야 한다. urlllib 라이브러리로 작성 from urllib.requests import urlopen from bs4 import Bea..