자료구조

동적 계획법의 핵심 개념최적 부분 구조 (Optimal Substructure):문제를 더 작은 하위 문제로 나눌 수 있으며, 하위 문제의 최적 해답을 사용하여 원래 문제의 최적 해답을 구할 수 있음중복되는 부분 문제 (Overlapping Subproblems):동일한 하위 문제가 여러 번 반복해서 계산됩니다. 이를 해결하기 위해 하위 문제의 해답을 저장하고 재사용동적 계획법의 두 가지 접근 방식상향식 접근법 (Bottom-Up Approach):작은 하위 문제부터 해결해 나가면서, 최종적으로 원래 문제를 해결일반적으로 테이블을 사용하여 하위 문제의 해답을 저장하향식 접근법 (Top-Down Approach):문제를 더 작은 하위 문제로 재귀적으로 분할하여 해결메모이제이션 기법을 사용하여 이미 계산된 ..

검색의 개념어떤 집합에서 원하는 것을 찾는 것 알고리즘의 종류1. 순차검색2. 이진 검색 #검색의 개념 : 어떤 집합에서 원하는 개념을 찾는 것 #정렬되지 않은 집합의 순차 검색 원리와 구현찾을 데이터를 집합의 맨 앞에서 부터 찾아가야한다검색이 성공하는 경우 실패하는 경우로 나뉜다. #클래스와 함수 선언 부분#정렬되지 않은 데이터의 순차 검색def seqSearch(ary, fData) : pos = -1 size = len(ary) print('##비교한 데이터 ==>', end = ' ') for i in range(size) : print(ary[i], end = ' ') if ary[i] == fData : pos = i ..

버블 정렬 개념첫번째 값부터 시작해서 앞뒤 데이터를 비교하여 큰 것은 뒤로 보내는 방법을 사용하는 정렬버블 정렬의 구현#버블 정렬#클래스와 함수 부분def BubbleSort(ary) : n = len(ary) for end in range(n - 1, 0, -1) : for cur in range(0, end) : if (ary[cur] > ary[cur + 1]) : ary[cur], ary[cur + 1] = ary[cur + 1], ary[cur] return ary#전역 변수dataAry = [188, 162, 168, 120, 50, 150, 177, 105]#메인 코드print('정렬 전 -->', dataAry)da..

정렬:자료들을 일정한 순서대로 나열하는 것 선택 정렬:여러 데이터 중에서 가장 작은 값을 뽑는 작동을 반복하여 값을 정렬 삽입 정렬:기존 데이터 중에서 자신의 위치를 찾아 데이터를 삽입하는 정렬 방법 최솟값을 찾는 방법: 1. 배열의 첫번째 값을 가장 작은 값으로 지정 2. 가장 작은 값으로 지정한 값을 다음 차례의 값과 비교하여 가장 작은 값을 변경하거나 그대로 두기 3. 마지막 값까지 비교를 마친 후 현재 가장 작은 값으로 지정된 값을 가장 작은 값으로 결정 #배열에서 최소값 위치를 찾는 함수def findMinIdx(ary) : minIdx = 0 for i in range(1, len(ary)) : #배열의 두번째 칸부터 반복 if (ary[min..

재귀 호출: 함수가 자기 자신을 다시 호출하는 기법기저 사례: 재귀 호출을 멈추는 조건재귀 사례: 함수가 자기 자신을 호출하여 문제를 더 작은 하위 문제로 분할하는 부분장점: 간결성, 문제 분할단점: 성능 문제, 중복 계산#재귀 호출의 작동def openBox() : print('종이 상자를 엽니다. ^^') openBox()openBox()종이 상자를 엽니다. ^^종이 상자를 엽니다. ^^...종이 상자를 엽니다. ^^종이 상자를 엽니다. ^^종이 상자를 엽니다. ^^ #재귀 호출 함수(반환 조건 추가)def openBox() : global count print('종이 상자를 엽니다. ^^') count -= 1 if count == 0 : print('반..

그래프의 기본 개념노드 (Node): 그래프의 정점(Vertex)간선 (Edge): 두 노드를 연결하는 선방향 그래프 (Directed Graph): 간선에 방향이 있는 그래프무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프가중치 그래프 (Weighted Graph): 간선에 가중치(Weight)가 부여된 그래프인접 행렬 (Adjacency Matrix): 그래프를 2차원 배열로 표현인접 리스트 (Adjacency List): 그래프를 리스트의 리스트로 표현  코드들#그래프 정점 집합V(G1) = {A, B, C, D}V(G2) = {A, B, C, D} #그래프 간선E(G1) = { (A, B), (A, C), (A, D), (B, C), (C, D) }E(G2) = { (A..

이진 트리의 개념트리 자료구조는 나무를 뒤집어 놓은 모양트리의 맨위를 뿌리(root)라고 부름루트를 레벨 0으로 두고 밑으로 내려올 수록 레벨이 1씩 증가트리의 각위치는 노드라고 부름위의 그림은 9개이고 각 노드는 선(edge)로 연결되어 있음위 노드와 아래 노드 사이의 관계는 부모 - 자식 관계자식 노드 개수는 차수(degree)라고 부름자식이 없는 노드는 리프(leaf)라고 부름 이진 트리의 종류이진트리는 포화 이진트리(full binary tree), 완전 이진 트리(complete binary tree), 편향 이진 트리(skewed binary tree)3개로 나뉨 포화 이진 트리노드가 꽉 차 있는 상태의 트리노드 개수가 2 ** (높이+1 - 1) 공식으로 계산예) 높이가 3인 포화 이진트리는..

큐의 개념입구와 출구가 따로 있는 자료구조입구와 출구가 다름선입선출 용어rear = 꼬리front = 머리enqueue = 데이터 삽입dequeue = 데이터 추출코드들#큐 생성 #front = 머리 #rear = 꼬리queue = [None, None, None, None, None]front = rear = -1 #front 와 rear 둘다 데이터가 없어서 -1 로 초기화 #데이터 삽입 : enQueue#1. rear(꼬리) 1증가 시킨 후 #2. rear 위치에 데이터 넣기#큐 생성queue = [None, None, None, None, None]front = rear = -1rear += 1queue[rear] = '화사'rear += 1queue[rear] = '솔라'rear += ..

스택한쪽 끝이 막힌 자료구조예) 프링글스 통         _    _4번ㅣ_    _ㅣ3번ㅣ_    _ㅣ2번ㅣ_    _ㅣ    =>    스택의 구조1번ㅣ_    _ㅣ0번ㅣ____ㅣ top : 스택의 맨 위push : 스택 안에 데이터를 집어넣기pop : 스택 안에서 데이터 추출하기peek : top 위치의 데이터 확인하기 #스택 생성stack = [None, None, None, None, None]top = -1 #데이터 입력 pushstack = [None, None, None, None, None]top = -1top += 1stack[top] = '커피'top += 1stack[top] = '녹차'top += 1stack[top] = '꿀물'print('--------- 스택 상태 -----..

원형 선형 리스트의 개념 단순 연결 리스트와 비슷원형 연결 리스트의 마지막 노드가 다시 첫 번째 노드를 가르키도록 설정되어 리스트 형태가 원 형태로 구성 단순 연결 리스트의 구조#노드 생성class Node() : #노드 데이터 만들기 def __init__ (self) : #데이터를 생성할 때 자동으로 생성되는 부분 self.data = None self.link - Nonenode1 = Node()node.data = '다현'node1.link = node1 #원형 #노드 연결class Node() : #노드 데이터 만들기 def __init__ (self) : #데이터를 생성할 때 자동..