자료구조 & 알고리즘 & cs (88) 썸네일형 리스트형 [TIL] 병합정렬 - Merge Sort 병합 정렬 재귀를 사용 리스트를 반으로 나눈 후 각 리스트를 합병 정렬을 이용하여 정렬 리스트를 나누는 split 함수와 이를 다시 병합하는 merge함수가 필요 split 함수 - 재귀용법을 이용하여 리스트를 반으로 나누는 함수 def split(data): if len(data) l_point and len(right) >r_point: if left[l_point] > right[r_point]: merged.append(right[r_point]) r_point+=1 else: merged.append(left[l_point]) l_point+=1 #left 원소만 있을 때 while len(left)>l_point: merged.append(left[l_point]) l_point+=1 #rig.. [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] 백준 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.. [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) : 한개의 데이터를 저장할 수 있는 공간 장점 데이터 검색속도가 빠름 (데이터 저장, 데이터 읽기) // 배열과 비교하여 알아두기 해당.. 프로그래머스 LEVEL2 - 오픈채팅방 ▶ 문제 설명 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. "[닉네임]님이 들어왔습니다." 채팅방에서 누군가 나가면 다음 메시지가 출력된다. "[닉네임]님이 나갔습니다." 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다. 예를 들어, 채.. 이전 1 ··· 5 6 7 8 9 10 11 다음