동적 계획법 동적 계획법의 개념 한 가지 문제에 대해 단 한 번만 풀도록 하는 알고리즘 똑같은 연산을 반복하지 않도록 함 복잡한 문제를 더 작은 하위 문제로 나누어 해결 중복 계산을 줄여서 계산 속도를 높일 수 있으며 경우의 수가 많은 경우에도 효율적으로 계산 가능 동적 계획법의 조건 겹치는 부분 문제 (Overlapping Subproblems) 동일한 작은 문제들이 반복하여 나타나는 경우 사용 가능 부분 문제의 결과를 저장하여 다시 계산하지 않을 수 있어야 함 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하여 부분 문제가 중복되지 않는 경우 사용 불가 최적 부분 구조 (Optimal Substructure) 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우..

그리디 알고리즘 그리디 알고리즘의 개념 각 단계에서 최적이라고 생각되는 것을 선택하는 알고리즘 결정을 해야 할 때마다 미래에 대한 생각없이 그 순간에 가장 최선의 선택을 함 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달 근사적인 방법 항상 최적의 값을 보장하는 것이 아님 그리디 알고리즘 방법 문제의 최적해 구조를 결저 현재 상테에서으 문제의 구조에 맞는 최적의 해답 선택 절차를 정의 (선택 절차) 선택 절차에 따라 선택을 수행 선택된 해가 문제의 조건을 만족하는지 검사 (적절성 검사) 조건을 만족하지 않으면 해당 해를 제외 모든 선택이 완료되면 해답을 검사 (해답 검사) 조건을 만족하지 않으면 해답으로 인정 안하고 선택 절차로 돌아가 반복 그리디 알고리즘 조건 탐욕스러운..

완전탐색 완전탐색의 개념 모든 경우의 수를 다 시도하여 정답을 찾는 알고리즘 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방식 '무식하게 풀기'라는 의미의 브루트 포스(Brute Force)라고 부르기도 함 상대적으로 구현이 간단하고 해가 존재하면 항상 찾을 수 있음 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용 완전탐색의 종류 이미지 출처 : https://adjh54.tistory.com/197 1. 브루트 포스 모든 경우의 수를 탐색 경우의 수가 많아질수록 시간 오래 걸림 for이나 while 등 반복문과 if 조건문 등을 활용 // 브루트 포스 사용 예인 최댓값 찾기 public static int bruteForce(int..

이진탐색 이진탐색의 개념 정렬된 배열에서 특정 값을 찾는 알고리즘 이분 탐색이라고도 함 탐색 범위를 절반씩 나누어 찾는 값을 포함하는 범위를 좁혀가는 방식 주로 배열의 인덱스를 기준으로 배열 내의 값을 탐색 이진탐색 방법 이미지 출처 : https://adjh54.tistory.com/187 배열의 중간에 있는 임의의 값(중간 값)을 선택 선택한 값을 찾고자 하는 값과 비교 선택한 임의의 값이 찾고자 하는 값보다 작으면 임의의 값 기준 좌측의 데이터들을, 크면 우측의 데이터들을 대상으로 다시 탐색 해당 값을 찾을 때까지 반복 이진탐색의 장점 검색 속도가 빠름 검색이 반복될 때마다 검색 범위가 절반으로 줄어듦 검색 대상의 크기와 상관없이 빠른 검색 속도를 제공 대량의 데이터를 다루는 알고리즘에서 많이 사용..

해시 해시의 개념 해시 (Hash) : 입력 데이터를 고정된 길이의 데이터로 변환된 값 사용 예 : 암호, 블록체인, 메시지 인증 코드 등 해시의 특징 해시 값(hash value), 해시 코드, 체크섬이라고도 불린다. 키(key)에 데이터(value)를 매핑할 수 있는 데이터 구조이다. 검색과 저장이 빠르게 진행된다. 같은 입력값에 대해서 출력 값을 보장한다. 일방향성을 갖기 때문에 해시값으로부터 key를 역산할 수 없다. 해시 함수 (hash function) 이미지 출처 : https://namu.wiki/w/%ED%95%B4%EC%8B%9C 입력받은 데이터를 해시 값으로 출력시키는 알고리즘 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환 블록체인에서는 해시 함수가 하는 역할은 ‘암호화'로..

정렬 선택 정렬 정렬되지 않은 원소들 중 가장 작은 원소를 찾아 가장 앞의 원소와 교환하는 알고리즘 이미지 출처 : https://gyoogle.dev/blog/algorithm/Selection%20Sort.html 방법 각 루프마다 최대 원소를 찾는다 최대 원소와 맨 오른쪽 원소를 교환한다 맨 오른쪽 원소를 제외한다 하나의 원소만 남을 때까지 반복 public void selectionSort(int[] arr) { int minIdx; int temp; for(int i = 0; i < arr.length - 1; i++) { minIdx = i; for (int j = i + 1; j < arr.length; j++) { if(arr[j] < arr[minIdx]) { minIdx = j; } }..

힙 (Heap) 힙의 개념 힙 (Heap) : 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록(우선순위 큐를 위해) 만들어진 자료구조 힙의 특징 완전 이진 트리의 일종 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리 key(부모 노드) >= key(자식 노드) 중복된 값을 허용 반정렬 상태(느슨한 정렬 상태) 유지 큰 값이 상위 레벨이 있고 작은 값이 하위 레벨에 있음 삭제 연산이 수해오딜 때마다 가장 큰 값을 찾아내기만 하면 되므로 전체를 정렬할 필요 없음 시간 복잡도 : O(logn) 우선순위 큐 (Priority Queue) 큐에 우선순위라는 개념 접목 우선순위가 높은 데이터가 먼저 나감 힙, 배열, 연결리스트로 구현 가능하며 힙으로 구현하는 것이 가장 효율..

그래프 그래프의 개념 그래프 (Graph) : 원소 사이의 연결 관계를 표현할 수 있는 자료구조 예 : 지도, 전기 회로의 소자들 등 그래프의 특징 현상이나 사물을 정점(vertex)와 간선(edge)으로 표현한 유한 집합이다. Gragh G = (V, E)로 표현한다. V : 정점 집합 E : 간선 집합 두 정점이 간선으로 연결되어 있으면 인접(adjacent)라고 한다. 네트워크 모델이다. 2개 이상의 경로가 가능하다. 방향, 무방향 그래프 모두 가능하다. 부모-자식 개념이 없다. 오일러 경로 (Eulerian Tour) 그래프에 존재하는 모든 간선(edge)을 한 번만 통과하면서 처음 정점(vertex)으로 되돌아오는 경로 오일러의 정리 : 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 경우에만..