할머니의 콤퓨타 도전기

그리디(Greedy) 알고리즘은 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 대표적으로 거스름돈 문제가 있는데, 단순하게 큰 경우 부터 찾는 알고리즘과 같이 간단하게 탐욕적으로 문제를 해결하는 기법 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 등으로 극단적으로 문제를 접근한다는 점에서 정렬 기법이 함께 사용되는 경우가 많음. 최적해에 가까운 값을 구하기 위해 사용 그리디를 통해 구한 결과값이 항상 최적해인게 아님 여러 경우 중 하나를 결정할 때마다, 매순간 최적이라 생각하는 경우를 선택하여 최종 결과값을 구함 반드시 최적해가 보장되는 것이 아니기 때문에 근사치 추정에 활용

큐 한쪽 끝(rear)에서는 삽입 연산만 이루어지며 다른 한쪽 끝(front)에서는 삭제 연산만 이루어지는 유한 순서 리스트 먼저 삽입된 item이 먼저 삭제가 이루어짐 (FIFO, First In First Out) 큐의 표현 순차 표현 1차원 배열 이용 front, rear를 -1로 초기화 하여 큐가 empty임을 표시 (front == rear일 때 큐는 공백) rear에서 삽입되므로 rear가 점차 증가하여 rear == n-1인 경우 큐는 full front에서 삭제가 일어났다면 그 만큼 공간이 비어있음. 따라서 큐에 원소가 꽉차있지 않아도 full 따라서 full이 되었을 때는 첫 원소 위치를 큐의 0번 인덱스부터 위치되게 하고 rear의 위치도 다시 계산 큐 원소 이동에 따른 지연시간 발생 ..

스택 가장 늦게 들어간 자료가 가장 먼저 나가는 구조 (LIFO, Last In First Out) 한 쪽 끝에서만 자료를 넣고 뺄 수 있다 스택의 가장 위를 top, 삽입과 삭제가 top에서 일어남 스택 연산 push(): 스택에 새로운 원소를 삽입 pop(): 스택의 top 원소를 제거하고 반환 empty() : 스택이 비어있는지 검사 size() : 스택의 크기

해싱 개념 데이터 관리/유지 자료구조 리소스 해시 함수(hash function) -> 해시 값(hash value) 해시테이블 해시 함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조 데이터가 저장되는 곳을 버킷(b..

깊이 우선 탐색 (DFS) 루트 노드 (혹은 임의의 다른 노드)에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 깊게 (depp) 탐색 모든 노드를 방문 하고자 하는 경우에 사용 단순 검색 속도는 BFS에 비해 느림 자기 자신을 호출하는 순환 알고리즘의 형태 전위 순회 (Pre-Order Traversals)를 포함한 다른 형태의 트리 순환은 모두 DFS의 한 종류 그래프 탐색의 경우 어떤 노드를 방문했는지 방문 여부를 반드시 검사해야 함 (안하면 무한루프 빠질 위험 있음) 깊이 우선 탐색 (DFS) 과정 a 노드(시작 노드)를 방문 (방문 여부 체크) a와 인접한 노드 차례로 순회 인접한 노드 없으면 종료 a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 ..

그래프 탐색 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것 너비 우선 탐색 (BFS) 루트 노드 (혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 넓게(wide) 탐색 두 노드의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용 BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색 재귀적으로 동작하지 않음 어떤 노드를 방문했었는지 여부 반드시 검사해야함 (안하면 무한루프에 빠질 위험 있음) 방문한 노드들을 차례로 저장한 후 꺼낼 수 있도록 큐(Queue) 사용 너비 우선 탐색 (BFS) 과정 시작 노드 방문 (방문한 노드 체크) 큐에 방문된 노드 삽입 큐에..