본문 바로가기

Algorithm

 (25)
그리디 알고리즘(Greedy)과 구현(Implementation) (1) 그리디 알고리즘(탐욕법) - 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미 - 최적의 해를 구할 수 있는지 검토 - 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 문제를 풀 수 있음 문제 1 ) 거스름 돈 문제해결 방법 - 최적의 해를 빠르게 구하기 위해선 가장 큰 화폐 단위부터 돈을 거슬러 주면 됨 - N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 줌 이후, 100원, 50원, 10원을 차례대로 거슬러 줌 * 정당성 분석 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유 - 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없음 if ) 800원..
알고리즘 기초 및 파이썬 기초 문법(6) - 함수와 람다 표현식, 표준 라이브러리 함수 - 함수(Function)란 특정한 작업을 하나의 단위로 묶어 놓은 것 - 불필요한 소스코드의 반복을 줄일 수 있음 - 내장 함수 : 파이썬이 기본적으로 제공하는 함수 - 사용자 정의 함수 : 개발자가 직접 정의하여 사용할 수 있는 함수 1. 함수 정의하기 - 매개변수 : 함수 내부에서 사용할 변수 - 반환 값 : 함수에서 처리 된 결과를 반환 # 더하기 함수 1 def add(a, b): return a + b print(add(3, 7)) # 10 # 더하기 함수 2 def add(a, b): print('함수의 결과:', a + b) add(3, 7) # 함수의 결과: 10 + ) 여러 개의 반환 값 - 파이썬에서 함수는 여러 개의 반환 값을 가질 수 있음 def operator(a, b): ..
알고리즘 기초 및 파이썬 기초 문법(5) - 입출력, 조건문과 반복문 기본 입출력 1. 입력 - input( ) 함수 : 한 줄의 문자열을 입력 받는 함수 - map( ) 함수 : 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용 공백을 기준으로 구분된 데이터를 입력 받을 때 - list(map(int, input( ).split( ))) 공백을 기준으로 구분된 데이터의 개수가 많지 않을 때 - a, b, c = map(int, input( ).split( )) # 데이터의 개수 입력 n = int(input()) # 각 데이터를 공백을 기준으로 구분하여 입력 data = list(map(int, input().split())) + ) 입력을 빠르게 받는 법 - sys 라이브러리에 정의되어 있는 sys.stdin.realine( ) 메서드를 이용 - 단, 입력 후 ..
알고리즘 기초 및 파이썬 기초 문법(4) - 사전, 집합 자료형 사전 자료형 - 키(Key)와 값(Value)의 쌍을 데이터로 가지는 자료형 - 값을 순차적으로 저장하는 리스트와 튜플(인텍스 이용)과 대비 - 원하는 '변형 불가능한(Immutable) 자료형'을 키로 사용 가능 - 해시 테이블(Hash Table)을 이용, 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리 가능 1. 사전 초기화 data = dict() data['사과'] = 'Apple' data['바나나'] = 'Banana' print(data) # {'사과': 'Apple', '바나나': 'Banana'} 2. 사전 자료형 관련 메서드 keys( ) 함수 : 키 데이터만 뽑아서 리스트로 이용 values( ) 함수 : 값 데이터만을 뽑아서 리스트로 이용 data = dict() data[..
알고리즘 기초 및 파이썬 기초 문법(3) - 리스트, 튜플, 문자열 자료형 리스트 자료형 - 여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용 - 리스트 대신 배열 혹은 테이블로 불리기도 함 1. 리스트 자료형 초기화 #직접 데이터를 넣어 초기화 a = [1, 2, 3, 4] # [1, 2, 3, 4] #네 번째 원소만 출력 print(a[3]) # 4 #크기가 N이고, 모든 값이 0 인 1차원 리스트 초기화 n = 4 a = [0] * n print(a) # [0, 0, 0, 0] #반목문을 이용해서 초기화 array = [i for i in range(4)] print(array) # [0, 1, 2, 3] # 0 ~ 9까지 홀수만 포함하는 리스트 array = [i for i in range(10) if i % 2 == 1] print(array) # [1, 3, 5..
알고리즘 기초 및 파이썬 기초 문법(2) - 수 자료형 파이썬 기초 문법 자료형 - 파이썬에서의 자료형 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 등이 있음 수 자료형 정수형 #정수형(양/음의 정수, 0) a = 1000 #양의 정수 b = -7 #음의 정수 c = 0 #0 실수형 - 컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 가짐 - 개발 과정에서 실수 값을 제대로 비교하지 못 할 수도 있음 - round() 함수를 이용하여 문제 해결 - 123.456 소수 셋째 자리에서 반올림 round(123.456, 2) -> 123.46 #실수형 #소수점 아래의 데이터를 포함하는 수 자료형 a = 157.93 #양의 실수 b = -1837.2 #음의 실수 c = 5. #5.0 #소수부가 0일 때 0을 생략 d = -.7 #-0.7 #정수부..
알고리즘 기초 및 파이썬 기초 문법(1) - 알고리즘 기초 알고리즘 성능 평가 1. 복잡도(Complexity) - 알고리즘 성능을 나타내는 척도 (복잡도가 낮을수록 좋은 알고리즘) - 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘 수행 시간 분석 - 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘 메모리 사용량 분석 2. 빅오 표기법(Big-O) - 가장 빠르게 증가하는 항만 표기 (차수가 가장 큰 항만 남김) 3. 알고리즘 설계 팁(Python) 1. Python을 기준으로 5 ~ 15초 가량 시간 소요 2. 상황에 따라 PyPy도 이용해 보는 것도 좋음 3. 코딩 테스트 문제의 시간제한은 통상 1~5초 4. 문제에서 시간제한(수행시간 요구사항)을 가장 먼저 확인 - N의 범위 500인 경우 - O(N^3) 알고리즘 - N의 범위 2,000인 경..
그래프 탐색 알고리즘 DFS & BFS, Backtracking(백트래킹) (2) DFS(Depth-First Search) - DFS : 깊이우선 탐색 - 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 - DFS는 스택 자료구조(혹은 재귀 함수)를 이용 1. 탐색 시작 노드를 스택에 삽입 후 방문 처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼냄 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 + ) Backtracking(백트래킹) - 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기에 정답을 찾아가는 범용적 알고리즘 - 탐색에서는 이 길이 아닌 것 같으면 왔던 길로 되돌아와 다른 선택지로 감 - 재귀로 보통 구현, 재귀..

티스토리툴바