할머니의 콤퓨타 도전기

해싱 개념 데이터 관리/유지 자료구조 리소스 해시 함수(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) 과정 시작 노드 방문 (방문한 노드 체크) 큐에 방문된 노드 삽입 큐에..

브루트 포스는 완전 탐색, 모든 경우의 수를 탐색하여 결과를 도출하는 기법 (노가다와 다굴을 논리적이고 과학적으로 하는 방식) 어쩔 수 없이 모든 경우의 수를 탐색해야 하는 경우, 모든 경우의 수를 요구하는 문제에서 주로 사용

이분 탐색 탐색 범위를 두 부분으로 분할해서 찾는 방식. 따라서 전부를 탐색하는 것에 비해 속도가 빠름 시간 복잡도 O(log(n)) 1. 이미 정렬이 되어있어야 이분 탐색 가능 2. left, right로 mid 값을 결정 3. mid 값과 구하고자 하는 값 비교 4. 비교할 때 mid 값보다 구하고자 하는 값이 크면 left를 mid + 1로, 낮으면 right를 mid-1로 만듦 5. left > right 가 될 때 까지 위의 과정을 반복해 구하고자 하는 값 찾음

다이나믹 프로그래밍이란 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 크고 어려운 문제가 있으면, 그것을 먼제 잘게 나누어 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것 Memoization이 사용됨 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야할 때는 저장된 값을 단순히 반환하기만 하면 됨 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 -> 이 두 가정이 모두 성립하면 다이나믹 프로그래밍 사용 가능