본문 바로가기
728x90

study/알고리즘

 (44)
[알고리즘] DFS/BFS 공부 : 동빈나 유튜브 + 책 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - DFS/BFS는 대표적은 그래프 탐색 알고리즘 (사전 학습) 자료구조 정리 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 - 삽입(Push) / 삭제(Pop) - Overflow와 Underflow를 신경쓰기 1. 스택 - 선입후출(First In Last Out) / 후입선출(Last In First Out) 구조 - 파이썬에서 별도의 라이브러리 없이 리스트로 구현 가능 stack = [] #순서대로 5 2 3 7 삽입 - 삭제 - 1 4 삽입 - 삭제 stack.append(5) stack.append(2) st..
[알고리즘] 이진탐색 공부 : 동빈나 유튜브 ( https://youtu.be/94RC-DsGMLo?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC ) 이진탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터 탐색 - 시작점, 끝점, 중간점 - 정렬되어 있어야 가능 - 단계마다 탐색 볌위를 2로 나누는 것과 동일 -- O(logN) - 이진탐색은 재귀함수 또는 반복문을 통해 풀 수 있음 #재귀함수버전 def binarySearch(array, target, start, end): if target end로 멈출수도 있음 return None mid = (end+start)//2 if array[mid] == target: return mid..
[알고리즘] 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법인 탐욕적으로 문제를 푸는 알고리즘 대부분 그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없을 가능성이 높기 때문에 알고리즘으로 문제의 해법을 찾았을 경우 정당한지 검토해야 한다. 예제 3- 1 거스름돈 코드 : 시간 복잡도 O(화폐의 갯수) 직접 작성한 코드에서 수정할 부분 - C언어에서 for문을 통해 배열을 사용하는 방법에서 벗어나서 for문을 in과 함께 사용하여 list 데이터를 변수로 바로 꺼내쓸 수 있도록 한다. ex) for coin in coin_type - 7번째 줄 → N %= coin[i]로 간단하게 작성 가능 실전문제 - 큰수의 법칙 처음에 m//k로 계산 실수 --> m//(k+1)로 변경 (배열의..
[알고리즘] 파이썬 문법 복습 - 소수점 값을 비교하는 작업이 필요한 문제 --> round() 함수 이용 인자 : 실수형 데이터, 반올림하고자 하는 위치 - 1 a = 0.3 + 0.6 if a == 0.9: print(True) else: print(False) # False 출력 if round(a, 4) == 0.9: print(True) # True 출력 else: print(False) - 리스트 초기화 #크기가 N이고, 모든 값이 0인 1차원 리스트 초기화 n = 10 a = [0]*n print(a) #[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # 리스트 컴프리헨션을 이용한 N * M 크기의 2차원 리스트 초기화 n = 3 m = 4 array = [[0] * m for _ in range(n)] #[[0,..
반응형

티스토리툴바