기록하고 싶은 것들

이진 탐색 알고리즘순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 이진 탐색의 시간 복잡도단계마다 탐색 범위를 2로 나누는 것과 동일 , 연산횟수는 log2N에 비례즉, 이진 탐색은 탐색 범위를 절반씩 줄이고 시간 복잡도는 O(log2N) # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target:..

정렬 알고리즘정렬(sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 선택 정렬처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] # 스와프 print(array) 시간 복잡도는 O(N**2) 삽입 정렬처리되지 않은 데이터를 하나씩 ..

그래프 탐색 알고리즘대표적인 그래프 탐색 알고리즘이 DFS/BFS는 코딩테스트에서 매우 자주 등장하는 유형 스택 자료구조선입후출의 자료구조 입구와 출구가 동일한 형태(ex : 박스 쌓기) 스택 구현 예제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.pop() print(stack) # 최하단 원소부터 출력 print(stack[::-1]) # 최상단 원소부터 출력 큐 자료구조선입 선출의 자료구조입구와 출구가 모두 뚫린 터..

그리디 알고리즘그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법정당성 분석이 중요일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많지만,코딩 테스트에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황임 ex) 거스름 돈: 문제아이디어: 가장 큰 화폐 단위부터 돈을 거슬러줌큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장최소한의 아이디어를 떠올리고 정당한지 검토 n = 1260 count = 0 array = [500,100,50,10] for coin in array: count += n // coin #해당 화페로 거슬러 줄..

실수 값을 제대로 비교하지 못하는 상황 발생시ex) 0.6+.0.3을 0.899999 로 나타냄이럴 때는 round()함수를 이용하여 문제해결 수자료형의 연산파이썬에서는 나누기 연산자(/)는 나눠진 결과를 실수형 반환몫을 구할때는 a//b 리스트 자료형데이터를 연속적으로 담아 처리하기 위해 사용하는 자료형배열 또는 테이블이라고 부름 리스트 인덱싱과 슬라이싱리스트 뒤에서 부터 원소를 접근할 때 음수 사용리스트에서 연속적인 위치를 가지는 원소를 가져올 때는 슬라이싱 사용(끝 인덱스는 실제 인덱스보다 1을 더 크게 설정) 리스트 컴프리헨션 a = [i for i in range(50)]array = [i for i in range(20) if i % 2 == 1]2차원 리스트를 초기화할 때 효과적으로 사용 가..