안녕하세요! 이번 포스팅에서는 DP, 동적 계획법에 대해서 적어보겠습니다. 동적 계획법 동적 계획법(Dynamic Programming) 은 최적화 문제를 해결하는 알고리즘입니다. 여기서 최적화 알고리즘이란 최대값 또는 최소값을 구하는 문제이거나, 경우의 수를 구하는 문제가 속할 수 있습니다. 동적 계획법은 문제를 작은 문제들로 나누어서 작은 부분 문제들의 해를 구하고, 이것들을 이용해 큰 크기의 부분 문제들을 해결하여 최종 문제를 해결하는 설계 기법입니다. 동적 계획법은 최적 부분문제 구조와 중복 부분문제 구조를 가지고 있어야 한다는 조건이 있습니다. Optimal substructure Optimal substructure, 최적 부분문제라고 해석할 수 있는 이것은 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것입니다. 위에서 동적 계획법은 작은 문제들로

안녕하세요! 오늘 공부한 힙 자료구조를 작성해 보겠습니다. HEAP 힙은 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만든 자료 구조입니다. 힙의 종류에는 최대 힙 (max heap) , 최소 힙 (min heap) 이 있습니다. 최대 힙 최대 힙은 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리입니다. 부모 노드의 키 값은 자식 노드의 키 값보다 항상 큽니다. 그렇다면 최대 힙의 루트 노드는 트리의 최대값이 될 것입니다. 최소 힙 최소 힙은 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리입니다. 부모 노드의 키 값은 자식 노드의 키 값보다 항상 큽니다. 그렇다면 최소 힙의 루트 노드는 트리의 최소값이 될 것입니다. 힙을 분석해보자 힙에 원소를 넣기 위해서는 **현재 트리의 높이(level) 만큼 부

안녕하세요! 이번 포스팅에서는 백트래킹 알고리즘 기법과 그래프 자료구조에 대해서 정리해보겠습니다. Backtracking 알고리즘을 풀 때, 모든 조합을 시도해서 문제의 해를 찾아내는 방법은 해를 얻을 때까지 모든 가능성을 시도합니다. 위의 알고리즘 기법은 보통 재귀 함수로 구현되며 완전 탐색의 대표적인 방법은 BFS, DFS가 있습니다. 하지만 위의 방법을 사용하면 해답이 될 가능성이 전혀 없는 조합까지도 모두 시도해봐야하기 때문에 비효율적 입니다. 재귀 함수가 시간적으로 효율적인 함수가 아닌데다가, 호출 횟수가 시간 복잡도가 되기 때문에 재귀 함수에서 시간적인 효율성을 높이려면 함수 호출 횟수를 줄이는 것이 관건입니다. 백트래킹 알고리즘 기법은 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 가는 방법입니다. **유망하다 `promis

안녕하세요! 이번 포스팅에서는 Greedy 알고리즘과 분할 정복 알고리즘에 대해서 설명하도록 하겠습니다. Greedy 탐욕 알고리즘은 최적해를 구하는 데 사용되는 방법입니다. 일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 그리디적인 접근이 됩니다. Greedy 에서 핵심은 한번 선택된 것을 번복하지 않는다는 것입니다. 항상 그 시점에서 최선의 선택만을 하므로 다시 되돌아가서 확인하는 절차가 없습니다. 따라서 최적성에 대한 검증을 알고리즘 로직을 생각할 때 체크해야 합니다. 탐욕 알고리즘의 필수 요소는 greedy choice property 와 optimal substructure property 가 있습니다. greedy choice property : 탐욕적 선택은 항상 최적해라는 것을 검증해야 한다. *optimal substructure property

안녕하세요! (어제 공부한 내용이지만) 오늘 쓰니까 아무튼 TIL!! 이번 포스팅에서는 트리와 트리 탐색에 자주 쓰이는 BFS , DFS 를 정리해보겠습니다. Tree 트리 자료구조는 부모-자식의 1:N 관계를 가지는 비선형 자료구조입니다. 원소들 간에 계층 관계를 가지는 계층형 자료구조라고도 합니다. 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조입니다. 용어 노드(node) : 트리의 원소 루트 노드(root node) : 트리의 시작 노드인 최상위 노드 간선(edge) : 노드와 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결 형제 노드(sibling node) : 같은 부모 노드의 자식 노드들 -

안녕하세요! 오늘 공부한 Java의 Comparable , Comparator 에 대해서 작성해보겠습니다. Comparable Comparable 은 인터페이스입니다. Comparable 의 compareTo() 메소드는 객체를 정렬하는데 사용됩니다. 자바에서 같은 인스턴스를 비교하는 클래스들은 모두 Comparable 인터페이스를 구현하고 있습니다. 메인 메소드에서 위 코드를 실행시키면 어떤 결과가 도출될까요? int 타입 배열은 물론, String 타입의 배열도 정렬됩니다. 위

안녕하세요! 오늘 공부한 Linked List 에 대해서 간단하게 적어보겠습니다. 리스트 자바에서 리스트는 원소를 관리하는 순서를 가진 데이터의 집합을 가리키는 추상적인 자료형입니다. 동일한 데이터를 가지고 있어도 상관 없습니다. 리스트는 구현 방법에 따라 순차 리스트 와 연결 리스트로 나뉩니다. 순차 리스트 : 배열 기반의 리스트 연결 리스트 : 메모리 동적 할당을 기반으로 구현하는 리스트 순차 리스트 순차 리스트는 쉽게 말해서 자바의 배열을 뜻합니다. 순차 리스트에서는 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있습니다. 순차 리스트에서 삽입 연산은 아래의 순서대로 실행됩니다. > 1. 삽입할 인덱스를 비워둬야 합니다. 2. 삽입할 인덱스가 배열의 마지막이 아닌 가장 앞 또는 중간이라면 삽입 위치 다음의 항목들을 모두 뒤로 이동시켜야 합니다. 3. 그 후 삽입

안녕하세요! 오늘은 공부한 부분집합, 스택, 큐에 대해서 작성해보려고 합니다. 부분집합 집합에 포함된 원소들을 부분적으로 선택하는 것입니다. 다수의 알고리즘은 최적의 부분 집합을 찾는 해법이 자주 쓰입니다. 부분집합 분석해보기 부분집합의 수는 집합의 원소가 n 개일 때, 공집합을 포함해서 2^n 개 입니다. 즉, 원소를 부분집합에 포함하거나 포함하지 않는 경우를 모두 적용한 것입니다. 연장선상으로 시간복잡도는 O(2^n) 이 될 것입니다. n 이 30이라면 약 10억번의 연산이 필요하니, 비효율적인 시간복잡도에 속한다고 할 수 있습니다! 간단한 코드로 보자 재귀적으로 구현을 하는 방법입니다. 위의 방법은 부분집합 원소의 개수가 3개라고는 했지만, 공집합도 포함됩니다. 그래서 모두 원소를 포함하도록 한다면 조합과 같은 로직이 완성될 것입니다. 스택 스택은 **LIFO (Last-

안녕하세요! 오늘은 하루종일 알고리즘 문제만 풀었는데요 ㅎ.ㅎ 푼 알고리즘 중에서 시간 고려하느라 애썼던 문제 풀이를 적어보겠습니다. 문제 요약 이 문제는 주어진 N개의 수를 자신보다 작은 숫자가 몇 개 있는지 계산해서 값을 갱신하는 문제입니다. 주의할 점 여기에서, N 이 최대 1,000,000 이라는 것에 집중해야 합니다. 이 상황에서 시간복잡도는 O(N^2) 이 된다면 시간 초과가 발생할 것입니다. 즉, for 문 순회를 중복으로 하면 안된다는 의미일 것입니다. 처음 생각한 방법 > 입력받은 N 개의 수는 배열로 만들고, Set 을 활용해서 중복을 없앤 배열을 만들어서 계산하자! 위와 같이 생각했지만.. 한 가지 놓친 부분이 있

안녕하세요! 오늘 공부한 알고리즘에 대해 간단하게 정리해보겠습니다 ~ 순열 What is 순열? 🤔 순열은 서로 다른 것들 중 몇 가지를 뽑아서 한 줄로 나열하는 것 을 의미합니다. 순열의 순서는 유의미합니다. 따라서, 순서가 바뀐다면 다른 순열을 뜻합니다. > 예시로, 학교 총회를 뽑는다고 했을 때 부서별로 n명 뽑는다는 것은 뽑히는 순서는 중요하지 않습니다. 뽑히느냐, 안뽑히느냐가 중요하겠죠? 그와 반대로 대학교 예비 번호를 생각해보면, 순서는 너무 중요하겠죠. 1번이라면 대학교에 붙을 수도 있지만, 1000번은 가망이 없다고 생각할 것입니다. 첫 번째 예시인 총회를 n명 뽑는다는 것은 뽑는 순서가 중요하지 않은 조합 , 두 번째 예시인 대학교 예비 번호는 순서가 중요한 순열 입니다! 순열을 분석해보자! 순열을 수학적 식으로 나타내면, nPr 입니다. n 은 총 요소의 개수이고, r