본문 바로가기

programming study/Algorithm

 (275)
[동빈나]이코테 2021 강의 몰아보기 (9)(2021.1.11) 본 내용은 해당 강의 토대로 작성 다이나믹 프로그래밍 1. 다이나믹 프로그래밍 개요 메모리를 적절히 사용하여 수행시간 효율을 비약적으로 향상 시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않는다. 두 가지 방식(탑다운, 보텀업)으로 구성 동적 계획법이라고도 불린다. 동적(Dynamic)의 의미 동적 할당(Dynamic Allocation) : 자료구조에서, 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 여기서는 별다른 의미 없음 2. 다이나믹 프로그래밍의 조건 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있고 이를 모아서 큰 문제를 해결 가능 중복되는 부분 문제 (Overlapping Subpro..
[동빈나]이코테 2021 강의 몰아보기(8) (2021.1.6) 본 내용은 해당 강의 토대로 작성 이진 탐색 1. 이진 탐색 개요 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용하여 탐색 범위 설정 2. 이진 탐색의 시간 복잡도 연산 횟수는 log2N에 비례 시간 복잡도는 O(logN)보장 3. 이진 탐색 소스코드 : 재귀적 구현 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # ..
[동빈나]이코테 2021 강의 몰아보기(7)(2021.1.6) 본 내용은 해당 강의 토대로 작성 정렬 알고리즘 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 문제 상황에 따라 정렬 알고리즘이 공식처럼 사용 1. 선택 정렬 처리되지 않은 데이터 중 가장 작은 데이터를 선택 후 맨 앞에 있는 데이터와 바꾸는 것을 반복 이중 반복문으로 구현 선택 정렬 동작 예시 처리되지 않은 데이터 중 가장 작은 데이터를 선택하여 가장 앞의 데이터와 바꾼다. 이러한 동작을 반복한다. 선택 정렬 소스코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): 0 ~ 9 min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if arra..
[동빈나]이코테 2021 강의 몰아보기(6)(2021.1.4) 본 내용은 해당 강의 토대로 작성 그래프 탐색 알고리즘: DFS/ BFS 탐색(Search)이란 원하는 데이터를 찾는 과정 DFS, BFS 자주 출제되는 유형 1. DFS (Depth-First Search) 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료 구조(혹은 재귀함수)를 이용 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 DFS 소스코드 예제 # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리..
[동빈나]이코테 2021 강의 몰아보기(5)(2021.1.3) 본 내용은 해당 강의 토대로 작성 그래프 탐색 알고리즘: DFS/ BFS 탐색(Search)이란 원하는 데이터를 찾는 과정 DFS, BFS 자주 출제되는 유형 1. 자료구조 스택 Stack 선입후출의 자료 구조 입구와 출구가 동일한 형태 박스를 쌓듯이 나중에 들어온 것을 가장 먼저 뺄 수 있다. 스택 구현 예제 stack = [] # 리스트 자료형 # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) # 가장 오른쪽에 추가 stack.append(2) stack.append(3) stack.append(7) stack.pop() # 가장 오른쪽 제거 stack.append(1) stack.append(4) stack.p..
[동빈나]이코테 2021 강의 몰아보기(4) (2021.1.1) 본 내용은 해당 강의 토대로 작성 그리디 알고리즘 1. 그리디 알고리즘 개요 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 뜻함 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 정당성 분석이 중요 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 일반적인 상황에서 최적의 해를 보장할 수 없는 때가 많다. 코딩 테스트에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제 2. 그리디 유형 문제 풀이 거스름 돈 문제 설명 카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원이 무한이 존재 손님에게 거슬러 줄 돈이 N(10의 배수)원일 때 필요한 최소 동전..
[동빈나]이코테 2021 강의 몰아보기(3)(2020.12.31) [동빈나]이코테 2021 강의 몰아보기(3)(2020.12.31) 본 내용은 해당 강의 토대로 작성 파이썬 문법 부수기 1. 기본 입출력 모든 프로그램은 적절한 입출력 양식을 가지고 있다. 프로그램 동작의 첫 단계는 데이터를 입력 받거나 생성하는 것 자주 사용되는 표준 입력 방법 input() : 한 줄의 문자열을 입력 받는 함수 map() : 리스트의 모든 원소에 각각 특정 함수를 적용할 때 사용하는 함수 # 데이터의 개수 입력 n = int(input()) # 각 데이터를 공백을 기준으로 구분하여 입력 data = list(map(int, input().split())) # 65 90 75 34 99 입력 data.sort(reverse=true) # 내림차순 정렬 print(data) # [99, ..
[동빈나]이코테 2021 강의 몰아보기 (2)(2020.12.30 ~ 31) [동빈나]이코테 2021 강의 몰아보기 (2)(2020.12.30 ~ 31) 본 내용은 해당 강의 토대로 작성 파이썬 문법 부수기 자료형 모든 프로그래밍은 데이터를 다루는 행위 Python의 자료형 정수형, 실수형, 복소수형, 문자열, 리스트 , 튜플, 사전 등 1. 수 자료형 정수형(Integer) 정수를 다루는 자료형 양의 정수, 음의 정수, 0 많은 유형의 문제에서 다루는 자료형 # 양의 정수 a = 1000 print(a) # 음의 정수 a = -7 print(a) # 0 a = 0 print(a) 실수형(Real Number) 소수점 아래의 데이터를 포함하는 수 자료형 변수에 소수점울 붙인 수 대입하면 실수형 변수 처리 소수부가 0, 정수부가 0인 소수는 0을 생략하고 작성 할 수 있음 # 양의..

티스토리툴바