미새문지

힙(heap) 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 하는 자료구조 특징 a가 b의 부모노드면 a의 키값과 b의 키값 사이에는 대소 관계가 성립한다. 최소 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 ​ 힙 자료구조 파이썬 힙 모듈은 heapq라는 알고리즘 라이브러리를 제공 내장 모듈이기 때문에 설치할 필요없이 사용가능 모든 부모 노드는 자식 노드보다 값이 작거나 큰 이진 트리 구조인데, 내부적으로는 인덱스 0에서 시작해 n번 째 원소가 항상 자식 원소들보다(2n+1, 2n+2)보다 작거나 최소 힙의 형태로 정렬 기능 heapq.heappush(heap, item) : item을 h..

sys 모듈 파이썬에서 제공하는 표준 라이브러리로 시스템과 관련된 각종 정보들을 제공하는 모듈이다. 몇 가지 기능들 sys.argv 파이썬을 실행하면서 입력된 값을 전달받아 활용할 수 있다. argv를 출력하면 입력된 값을 list형태로 저장하고 있고, 첫번째 배열 값은 항상 실행하는 파일의 이름이다. 그래서 입력된 값은 argv[0]이 아닌 argv[1]부터 시작한다. sys.path 파이썬이 설치되어 있는 경로 및 라이브러리들의 경로를 리스트에 모두 저장하고 있는 변수이다. 이 리스트에 경로를 추가해 파이썬 파일들을 import문으로 불러올 수 있다. sys.executable 현재 실행하고 있는 파이썬 실행파일의 절대경로를 알아낼 수 있다. 실행파일의 경로를 알아내야 할 때 사용 sys.platfo..

트리(Tree) 노드(Node)들이 연결된 계층적인 자료구조 특징 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖는다. 자식 노드도 0개 이상의 자식 노드를 가지는 반복적인 트리를 구성한다. 용어 루트(Root) 트리의 최상위에 있는 노드 부모(Parent) 노드 바로 위에 연결된 노드 자식(Child) 노드 바로 아래에 연결된 노드 리프 노드(leaf Node) 자식이 없는 마지막 노드 내부 노드(Internal Node) 리프 노드를 제외한 모든 노드 레벨(Level) 루트 노드부터의 거리 트리 순회 방법 전위 순회(preOrder) 루트를 먼저 방문하고 왼쪽 자식노드부터 오른쪽 자식 노드까지 순서대로 방문 중위 순회(inOrder) 왼쪽 자식 노드를 먼저 방문하고, 루트..

위상정렬 수서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘 답이 한 가지가 아니라 여러 가지가 존재할 수 있고 DAG(Directed Acyclic Graph)에만 적용이 가능하다. DAG는 사이클이 발생하지 않는 방향 그래프이며, 사이클이 발생하면 위상정렬을 수행할 수 없다. 위상정렬은 두 가지 해결책을 낼 수 있는데 현재 그래프가 위상정렬이 가능한지, 위상정렬이 가능하면 그 결과는 무엇인지이고 스택과 큐를 이용해 알고리즘을 짤 수 있다. 진행 과정(큐를 사용) 1. 진입차수가 0인 정점을 큐에 삽입 2. 큐에서 원소를 꺼내 연결된 모든 간선 제거 3. 간선 제거 이후 진입차수가 0이 된 정점을 큐에 삽입 4. 큐가 빌 때 까지 2번, 3번 과정 반복. 모..

그래프(Vertex, edge, node, arc) 구조 정점(Vertex) 그래프의 기본 단위로, 위치나 상태 등을 표현, 노드(Node)라고 부른다 간선(Edge) 두 개의 정점을 연결하는 선을 말하며 두 정점 사이의 관계나 거리 등을 표현 노드(Node) 간선과 같은 의미이며 특정 상태나 위치를 나타내는 점(dot) 그래프에서 점으로 표현 호(Arc) 방향성이 있는 간선을 의미. 두 정점을 연결하는 선이지만, 한 정점에서 다른 정점으로 방향이 정해져 있다. ​ 그래프는 정점과 정점들을 연결하는 간선으로 구성 그래프는 정점과 간선의 집합으로 이루어진 자료구조이다. 특징 방향성 방향성이 있는 그래프를 유향 그래프(Directed Graph) 방향성이 없는 그래프를 무향 그래프(Undirected Gra..

어제에 이어서 알고리즘 문제만 하루종일 풀었다. ​ 나무 자르기 # # 입력 : # # 나무 개수값 n, 상근이가 가져가고 싶은 길이값 m, 나무 길이들 # # 출력 : # # 절단기의 설정 값 # import sys # namu = list(map(int, sys.stdin.readline().split())) # namu_length = list(map(int, sys.stdin.readline().split())) # namu_length.sort(reverse=True) # # 자른 길이 # # 톱 높이 나무가 제일 큰게 20이면 19로 설정 # saw_height = namu_length[0] - 1 # # 톱 높이를 제일 큰 나무의 -1부터 시작해서 1씩 감소 # for saw_count in..

수 정렬하기 n개의 수가 주어졌을 때, 오름차순으로 정렬하고 중복은 제거해야 한다. n = int(input()) arr = [] result = [] # 입력값 받아 arr배열에 넣기 for i in range(n): arr.append(int(input())) # 배열의 앞 뒤를 하나씩 비교해 앞이 뒤보다 크면 값을 바꾸기 for i in range(len(arr)-1): for j in range(i+1, len(arr)): if arr[i] > arr[j]: arr[i], arr[j] = arr[j], arr[i] else: continue # 중복 제거, arr안에 i값이 없으면 result배열에 넣기 for i in arr: if i not in result: result.append(i) f..

하노이탑 3개의 기둥이 있고 하나의 기둥에 여러 개의 원반이 있는데 각자 크기가 다 다르며 한 번에 한 개의 원반만 옮길 수 있고 크기가 큰 원반은 작은 원반 위에 올릴 수 없다. 재귀 함수를 이용한 알고리즘의 대표 문제이며 다음과 같이 동작한다 옮겨야 할 원반이 하나 뿐이라면, 해당 원반을 출발지 기둥에서 목적지 기둥으로 옮기기 그렇지 않으면 재귀함수를 사용해 가장 큰 원반을 제외한 나머지 원반들을 보조 기둥으로 옮긴다. 가장 큰 원반을 목적지 기둥으로 옮기고, 보조 기둥에 있는 원반들을 목적지로 옮긴다. # 하노이 함수(원판의 갯수, 시작봉, 중간봉, 끝봉) def hanoi(n, start, sub, finish): # 만약 원판의 개수가 1개면 끝봉으로 1번 이동하면 끝이니까 리턴값 if n ==..