알고리즘
[Python] 순열(permutation), 조합(combination) 구현
순열 (Permutation) ''' 3P2 구하기 (nPr) 1 2 1 3 2 1 2 3 3 1 3 2 ''' # 1. DFS를 이용 # 2. 체크리스트 이용 # 순열은 그냥 외운다. def DFS (L): # 종료조건이 필요함 : r 개를 뽑으면 종료 if L == r: print(list(result), end=' ') else: for i in range(len(n)): if checklist[i] == 0: # 0이면 뽑지 않은 것. (False) result[L] = n[i] # 뽑지 않았으니까 뽑고 checklist[i] = 1 # 체크리스트에 뽑았다고 표시 DFS (L+1) checklist[i] = 0 # 백트레버스 할 때 방문표시 지우기 if __name__ == "__main__": ..
[그래프 탐색 알고리즘] DFS/BFS
탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다. DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다. - 스택(Stack) : 선입후출 리스트의 append()와 pop() 메서드를 이용해 구현한다. - 큐(Queue) : 선입선출 리스트로 구현할 수 있지만 시간 복잡도 때문에 비효율적이기 때문에 collections 라이브러리의 deque를 사용한다. append()를 통해 삽입, popleft()를 통해 삭제한다. - 재귀함수(Recursive Function) : 자기 자신을 다시 호출하는 함수 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시..
큐(queue)
더보기 참고 큐(queue) : 선입선출. FIFO(First In First Our) 기반의 자료구조이다. 큐를 구현하는 방법은 세 가지가 있다 : list, deque, Queue 1. list 가장 간단한 방법이지만 pop(0) 또는 insert(0, x)의 시간 복잡도가 O(N)이기 때문에 성능적으로 불리하다. 방향에 따라 다음과 같이 두 가지 형태로 표현할 수 있다. (1) append() : 뒤에서 데이터 추가, pop(0) : 앞에서 데이터 제거 >>> queue = [4, 5, 6] >>> queue.append(7) >>> queue.append(8) >>> queue [4, 5, 6, 7, 8] >>> queue.pop(0) 4 >>> queue.pop(0) 5 >>> queue [6,..
[선형 자료구조] 스택, 큐
더보기 참조 스택(Stack) : 나중에 넣은 데이터가 먼저 반환 (LIFO: Last In First Out) - 파이썬에서의 스택 : 리스트를 사용하여 스택 구조로 데이터를 처리할 수 있다. 데이터 입력 : append() # push 데이터 출력 : pop() # pop, 맨 마지막에 있는 값을 뽑아서 준다. 뽑아낸 데이터는 리스트 내에서 없어짐 큐(Queue) : 먼저 줄 선 데이터가 먼저 반환 (FIFO: First In First Out) - 파이썬에서의 큐 : 마찬가지로 리스트를 이용한다. 데이터 입력 : append() # push 데이터 출력 : pop(0) # get, 맨 앞에 있는 값을 뽑아서 준다. 뽑아낸 데이터는 리스트 내에서 없어짐
[선형 자료구조] 해시 테이블
참고자료 더보기 출처 : 파이썬 알고리즘 인터뷰 (279p~) 해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)을 구현하는 자료구조다. - 해시 테이블의 가장 큰 특징은 시간 복잡도가 O(1)이라는 점이다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. ABC → A1 1324BC → CB (여기서 화살표 역할을 하는 함수가 바로 해시 함수다) - 해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱(Hashing)이라 하며, 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 하나다. - 해싱이 사용되는 분야 : 최적의 검색이 필요한 분야 심볼 테이블 등의 자료구조..