Engineering Note

Dynamic Programming Dynamic Programming은 greedy algorithm과 마찬가지로 최적화 문제를 해결하는 알고리즘이다. 최적화 문제란 가능한 해들 중에서 가장 좋은(최대 또는 최소)해를 찾는 문제이다. 다이나믹 프로그래밍은 입력 크기가 작은 부분문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다. 이때 부분문제들은 다음 문제를 해결할 때 기록해두어 필요할 때 다시 이용하는 메모이제이션 기법을 이용한다. Algorithm 문제풀이 팁 작은 문제부터 해결하기 문제에 주어진 조건을 잘 읽고 마지막에 조건을 붙이는 경우로 생각해보기, 이렇게 하면 메모이제이션을 생각하기가 조금 수월함 마..

dijkstra 최단경로 알고리즘 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘 '음의 간선'이 없을 때 정상적으로 동작 현실세계에서의 길이 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPX 소프트웨어의 기본 알고리즘을 채택되곤 한다. 현재 알고 있는 최단거리 정보를 가지고 최단거리표에 기록하고 그리디한 방법으로 최단거리이동 가능한 곳으로 이동해서 더 짧은 방법이 있으면 표를 갱신하는 방법이 핵심이다. 알고리즘의 원리 출발 노드를 설정한다. 출발노드까지의 거리는 0으로 초기화 한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른..

Priority Queue 대표적인 비선형 자료구조 입니다. 큐와 이름이 유사하지만 동작 방식은 다릅니다. 큐는 먼저 삽입한 값이 먼저 나오는 구조를 가지지만 우선순위 큐는 삽입한 값이라고 먼저 나오는 것이 아닌 우선순위가 높은 값이 먼저 출력됩니다. 우선순위는 프로그래머가 정하지만 대표적인 우선순위는 값의 크기에 따라 정하는 경우가 많습니다. 값이 클경우 우선순위가 높거나 값이 작을 경우 우선순위가 낮은 경우 입니다. Priority Queue를 구현 import heapq class PriorityQueue: ''' 우선순위 큐를 힙으로 구현합니다 ''' def __init__(self) : self.heap = [] def push(self, value) ..

주문관리 시스템 연결리스트로 구현하기 주문 관리 시스템 (연결 리스트) (요구사항은 앞 문제와 같습니다. 그러나 연결 리스트를 이용해 구현해주세요.) 이번 실습 문제에서는 주문 관리 시스템을 구현합니다. 이 주문 관리 시스템은 총 3가지 기능을 지원해야 합니다. 이는 주문생성, 주문취소, 주문조회입니다. 각각의 자세한 설명은 다음과 같습니다. 주문생성: 고객이 쇼핑몰에서 주문을 하게 되면 이 주문은 고유의 주문번호를 갖게 되고, 이 주문번호가 주문 관리 시스템에 등록됩니다. 물론 고객은 여러 명이기 때문에 주문관리시스템 내에 등록된 주문 번호가 여러 개 있을 수 있으며, 먼저 주문을 한 주문번호가 먼저 처리되는 구조입니다. 주문취소: 고객의 요청에 따라 주문은 취소가 될 수도 있습니다. 주문이 취소될 경..

def gcd(a,b): if b == 0: return a else: return gcd(b, a % b) print(gcd(35,14))

자료구조 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석 하는 것 자료구조의 이용 정렬 - 기억장치 내의 자료를 일정한 순서에 의해 나열하는 것 검색 - 기억장치 내의 자료를 찾는 것 파일 편성 - 자료를 기억 매체에 저장할 때의 파일 구조 인덱스 - 파일에서 특정 자료를 빠르게 찾기 위한 색인표 자료구조의 분류와 차이점 선형 자료구조 스택, 큐, 리스트(선형리스트, 연결리스트), 데크 비선형 자료구조 트리, 그래프 선형 리스트와 연결 리스트의 차이 둘다 순서가 존재하는 리스트 자료형이지만 차이가 있다. 선형리스트는 기억 장치 내에 연속적으로 메모리 주소 공간을 가지므로 포인터 연산처럼 인덱스로 접근하기가 용이..

위 그래프를 인접리스트 형태로 표현 해보았다. 먼저 C++의 대괄호([]) 연산자를 이용해 vector 5개를 선언했다. v1,v2가 연결되어 있다고 하면 아래와 같이 작성할 수 있다. map[v1].push_back(v2);// map[v1] 벡터에 v2데이터 추가 #include #include using namespace std; int main() { vector map[5]; //v[0]은 사용 안함 //vector map[1]은 노드 1에 연결된 노드정보 인접리스트형태로 저장 map[1].push_back(2);//map[1][0]에 2라는 데이터가 저장 map[1].push_back(3);//map[1][1]에 3이라는 데이터가 저장 map[1].push_back(4);//map[1][2]에..

Breadth-First Search 넓이 우선 탐색 트리, 그래프 탐색의 대표적인 알고리즘으로 레벨탐색이라고도 불린다. 부모노드의 연결된 자식노드를 모두 탐색한 후 다시 자식노드의 연결된 다음 레벨의 자식노드를 탐색하는 방식이다. DFS(깊이우선탐색)과 반대로 넓이를 먼저 탐색하고 다음 레벨을 탐색하는 완전탐색방법이다. DFS에서는 스택 자료구조를 사용하지만 BFS는 큐를 사용한다. 사용한 자료구조 큐 First In First Out(선입선출 방식의 데이터 구조로 먼저 들어간 데이터를 먼저 삭제하는 자료구조) 위와 같이 이진트리가 주어졌을 때 BFS 그래프 탐색을 구현해 보았다. 우선 이진트리는 C++의 vector 자료구조를 활용해 인접리스트 방식으로 구현한 후 1번 노드 부터 탐색을 진행하도록 코..