본문 바로가기

분류 전체보기

 (224)
[TIL] 퀵정렬 - Quick Sort 퀵정렬 기준점(pivot)을 정해서 기준점보다 작은 데이터를 왼쪽, 큰 데이터를 오른쪽으로 옮긴다. 옮겨진 왼쪽, 오른쪽 리스트는 재귀용법을 사용하여 다시 동일한 작업을 반복한다. 결과값은 왼쪽+기준점+오른쪽 def quickSort(data): if len(data) data[i]: left.append(data[i]) else: right.append(data[i]) return quickSort(left)+[pivot]+quickSort(right) 파이썬의 list comprehension을 사용하면 더 쉬운 코드로 작성 가능하다. def quickSort(data): if len(data) item] right=[item for item in data[1:] if pivot
[python] local variable 'x' referenced before assignment 해결 다음과 같은 에러사항은 외부에 선언한 전역변수를 함수 내에서 지역변수로 호출했기 때문에 발생한다. x=0 def addList(x): x +=1 Error UnboundLocalError: local variable 'x' referenced before assignment Solution 함수 내부의 변수명 앞에 global을 붙여준다. x=0 def addList(x): global x x +=1
[python] 백준 10989번 - 메모리 초과 문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 간단한 문제였는데 정답비율이 너무 낮아서 당황했다. 간단한 sorting 문제였기 때문에 sort()를 사용하여 제출했는데 계속 메모리 초과 문제가 떴다. n = int(input()) lst=[] for i in range(n): lst.append(int(input())) lst.sort() for i in range(len(lst)): print(lst[i]) 구글링을 해본 결과 1. sort() 함수를 사용하..
[TIL] 정렬 - Sorting 정렬 데이터를 정해진 순서대로 나열하는 것으로 여러 기법이 있다. 1. 버블 정렬 (bubble sort) - 인접한 두 데이터를 비교하여 앞에 있는 데이터가 뒤에 있는 데이터보다 클 경우 자리를 바꾼다. - 데이터가 n개일 경우 최대 n-1번의 로직을 적용한다. - 데이터 교환이 필요 없을 경우 (이미 정렬된 상태)가 존재한다. def bubble(data): for idx in range(len(data)-1): swap = False for idx2 in range(len(data)-1-idx): if data[idx2] > data[idx2+1] data[idx2], data[idx2+1] = data[idx2+1], data[idx2] swap = True if swap == False: bre..
[python] 2차원 배열 입력 받기 파이썬에서 간단하게 2차원 배열을 입력받는 방법은 크게 3가지로 구분할 수 있다. ▶ 각 원소를 입력받기 arr = [for _ in range(n)]# 배열의 가로길이 for i in range(n): arr[i] = list(map(int, input().split())) ▶ 원소에 list 자체를 추가하기 arr=[] for i in range(n): arr.append(list(map(int, input().split()))) ▶ 선언하면서 입력받기 arr=[list(map(int, input().split())) for _ in range(n)] arr2 = [[0 for _ in range(n)] for _ in range(n)]# n행 n열의 2차원배열을 0으로 초기화 *참고 블로그 [Pyt..
[TIL] 힙 - Heap 힙(Heap)이란? 완전 이진 트리(Complete Binary Tree) - 최대/최소값을 빠르게 찾기 위함 max heap과 min heap으로 분류 (최대값/최소값을 구하기 위한 구조) 각 노드의 값 >= 해당노드의 자식노드 값 (max heap) (min heap은 반대) 힙 구현시 배열 자료구조를 사용 * 완전 이진 트리 : 노드 삽입 시 가장 하단의 왼쪽 노드부터 차례대로 삽입하는 트리 힙 vs 이진 탐색 트리? -힙 : 최대/최소값 검색을 위한 구조 -이진 탐색 트리 : 탐색을 위한 구조 힙의 인덱스 구조 부모 노드의 인덱스 번호 = 자식 노드 인덱스 번호 // 2 왼쪽 자식 노드의 인덱스 번호 = 부모 노드 인덱스 번호 * 2 오른쪽 자식 노드의 인덱스 번호 = 부모 노드 인덱스 번호 * ..
[TIL] 트리 - Tree 트리(Tree)란? node와 branch를 이용한 데이터 구조 사이클x 탐색 알고리즘에 많이 사용(BST) 용어 노드(Node) : 데이터를 저장하는 기본 요소 (+ Branch) 루트노드(Root Node) : 트리의 최상위 노드 레벨(level) : 하위 브랜치로 연결된 노드의 깊이 부모 노드(Parent Node) : 어떤 노드의 다음 레벨 노드 자식 노드(Child Node): 어떤 노드의 상위 레벨에 연결된 노드 리프 노드(Leaf Node): 자식 노드가 하나도 없는 노드 (= terminal node) 형제 노드(Sibling Node): 동일한 부모 노드를 가진 노드 (= 레벨이 동일) Depth : 트리의 최대 level 이진 트리(Binary Tree) : 노드의 최대 Branch가 ..
[TIL] 해쉬 테이블 - Hash Table 해쉬 테이블(Hash Table)이란? (파이썬의 Dictionary) 키에 데이터를 저장하는 데이터 구조이다. 데이터 검색 속도가 매우 빠르다 배열로 미리 해쉬 테이블 사이즈만큼 생성 후 사용한다. 용어 해쉬(Hash) : 임의의 값을 고정 길이로 변환하는 것 해싱함수(Hashing Function) : key를 가지고 연산하여 데이터의 위치를 찾을 수 있는 함수 해쉬 값(Hash Value) : 해싱함수를 이용하여 key에 대한 연산을 통해 해쉬값을 알아냄 해쉬 주소(Hash Address) : 해쉬 값을 기반으로 key에 대한 데이터의 위치를 찾아냄 슬롯(Slot) : 한개의 데이터를 저장할 수 있는 공간 장점 데이터 검색속도가 빠름 (데이터 저장, 데이터 읽기) // 배열과 비교하여 알아두기 해당..
728x90

티스토리툴바