목록코딩 (332)
미새문지
트리(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 ==..
소수 1보다 큰 자연수 중 1과 자신만을 약수로 가지는 수 ex) 11은 1x11로만 성립되기 때문에 소수 에라토스테네스의 체 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 효율적으로 소수를 찾는 방법이다. 순서(100 이전의 소수를 모두 찾기) 1을 먼저 제거 2를 제외한 2의 배수 모두 제거 3을 제외한 3의 배수 모두 제거 5를 제외한 5의 배수 모두 제거 7을 제외한 7의 배수 모두 제거 ... 등 제거하고 남은 제일 낮은 수의 배수를 모두 제거하면 소수만 남는다. 일정 범위 내에서 구하기는 이 방법이 좋지만 특정 값이 소수인지 판별하는건 다른 알고리즘이 더 빠르다. 주어진 N개 중에 소수가 몇 개인지 찾기 주어진 N개의 소수를 받아 그 안에 소수가 몇 개인지 찾아야 한다. import..