Knowledge

동적 계획법 Dynamic ProgrammingDP라고 불리는 동적 계획법은 이름대로 동적인 알고리즘이 아니다. 이름과 관련이 없으니 DP는 그냥 외워야 한다. DP는 큰 문제를 작은 문제로 나누어 재사용하는 방법을 사용한다.여기서 포인트는 '작은 것으로 나눈다'가 아니라 '재사용한다'를 주목해야 한다. 알고리즘을 처음 공부할 때는 DP에 대해 정확히 이해하지 못했다. 작은 문제로 나눈다는 것에만 집중해 분할정복법(Divide&Conquer)과 비슷한 방법이구나 라고만 알고있었다. 하지만 분할정복과 접근 방식만 같을 뿐, 계산 결과를 재사용한다는 점에서 큰 차이점이 있다.  분할 정복 Divide and Conquer말 그대로 주어진 문제를 분할하여 작은 문제로 나누고, 작은 문제부터 해결해 병합하여 전..

알고리즘 평가 요소 1. 시간 복잡도 (Time Complexity)코드의 실행 시간이 얼마나 빠른가? 알고리즘의 수행 시간을 나타낸다.실행 시간이 빠를수록 주어진 시간 내에 더 많은 일을 할 수 있어 효율적이다. 2. 공간 복잡도 (Space Complexity)얼마나 메모리를 적게 쓰는가? 알고리즘 수행에 필요한 메모리 공간을 의미한다.실행하는 코드가 요구하는 메모리 공간이 적을수록 한번에 사용할 수 있는 여분의 공간이 더 많이 생긴다.더 적은 용량을 사용할수록 더 많은 공간을 사용할 수 있어 효율적이다. 시간복잡도와 공간복잡도는 알고리즘을 평가하는 요소로 중요하게 여기고, 그 중 시간복잡도를 더 고려한다.시간복잡도와 공간복잡도 계산을 할 땐 점근적 표기법을 이용하여 나타낸다.    점근적 표기법 (..

싱글톤 패턴인스턴스를 하나만 존재하도록 강제하는 것. 단 하나의 유일한 인스턴스를 만들어 사용하는 방법을 싱글톤 패턴이라고 한다. 단일 오브젝트로 애플리케이션 내에 전역적으로 접근하여 여러 곳에서 공유한다.  장점객체가 많이 생성되어 리소스를 많이 차지하는 무거운 클래스에서 사용된다.단일 객체로 존재하여 메모리가 낭비되지 않는다.이미 생성된 인스턴스를 사용해 속도가 빠르다. 단점상속이 불가능하여 다형성을 적용할 수 없다.한번만 생성되기 때문에 테스트가 힘들다.싱글톤이 하나만 만들어지는 것을 보장하지 못한다.클래스 안에서 객체를 직접 생성하여 의존성의 역전 원칙(DIP; Dependency Inversion Principle)을 위반한다.  생성 방법밖에서 오브젝트를 생성하지 못하도록 생정자를 Privat..

탐욕법 Greedy Method 각 단계마다 최적의 방법을 찾는 알고리즘. 여러 조각으로 나누고, 단계마다 답의 한 부분을 만들어가는 방법. 탐욕이라는 이름대로 그리디 알고리즘은 다음 단계를 고려하지 않고, 현재 단계에서 최적해를 찾아낸다. 이 때문에 지역적으로 최적인 답을 찾을 때는 매우 유용하게 사용되는 알고리즘이다. 하지만 지역적 최적이 최종적으로 최적이라는 보장은 없다. 1. 문제 해결 방법 1) 선택 절차 Selection Procedure 현재 상태에서 최적인 답을 선택한다. 2) 적절성 검사 Feasibility Check 조건을 벗어나지 않는지 검사한다. 3) 해답 검사 Solution Check 문제가 해결되었는지 검사한다. 아닐 시 선택 절차로 돌아가 반복한다. 2. 정당성 증명 1) ..

Hash Table - (key, value) 한 쌍의 형태로 데이터 저장 key와 value가 한 쌍의 형태로 저장되는 자료구조. 각 key에 해시 함수를 적용해 내부 버킷에 값을 저장하여 관리한다. 트리를 이용하면 해당 위치에 맞는 자리를 찾아야 하지만, 해싱은 key 하나로 쉽게 값을 가져올 수 있다. 특징 순서대로 저장되지 않는다. 트리나 배열보다 빠른 속도로 데이터에 접근할 수 있다. key는 중복된 값을 가질 수 없다. value는 중복된 값이 올 수 있다. key는 value를 찾기 위한 열쇠의 역할을 한다. 만약 동일한 키가 여러개 존재한다면, 해당 키로 우리가 찾고자 하는 값을 찾을 수 없다. 해당 컬렉션에서 키는 유일하게 존재해야 한다. 해시 함수 Hash Function 해시 함수를 ..

트리(Tree) - 계층적 관계를 표현하는 비선형 자료구조. 상위·하위로 나뉘거나 포함하는 관계일 시 계층구조로 표현. 자료가 저장된 노드 Node와 이 노드는 잇는 간선 Edge로 구성 루트 노드 Root node: 최상위에 있는 노드 단말 노드 Leaf node, Terminal node: 하위 노드가 없는 노드 내부 노드 Internal node: 단말 노드가 아닌 (하위 노드가 있는) 노드 형제 노드 Sibling node: 같은 부모 노드를 가지는 노드 레벨 Level: 루트 0레벨부터 아래로 내려갈수록 값 증가 크기 Size: 본인을 포함하여 자손 노드의 수 깊이 Depth: 해당 노드부터 루트까지 간선의 수 높이 Height: 최하 리프에서 루트까지 깊이 = 최대 레벨의 크기와 동일 서브 트..

Stack - Last in, First out : LIFO Queue - First in, First out : FIFO 스택과 큐는 일렬로 늘어선 자료를 표현한다. 자료구조는 데이터 표현에 따라 선형 자료구조와 비선형 자료구조로 나뉜다. 스택과 큐도 배열이나 리스트처럼 선형 자료구조의 일종이다. 이 두 가지를 나누는 기준은 자료를 어떤 순서로 삽입하고 삭제하냐로 볼 수 있다. 1. Stack 스택 : 후입선출 방식을 사용한다. 가장 늦게 들어온 데이터가 가장 먼저 빠져나간다. 웹 브라우저의 뒤로가기를 예시로 들수있다. 우리가 지나온 순서에 따라 스택에 삽입되고, 뒤로가기 버튼을 통해 직전에 왔던 길을 따라 되돌아간다. 이와 같이 가장 먼저 들어온 것이 제일 마지막에 빠져나가는 방식이 스택이다. 기본 ..

순차 리스트: 배열 기반의 리스트 연결 리스트: 메모리 동적 할당을 기반으로 구현된 리스트 리스트 자료구조 기본 기능은 동일하지만 기능을 제공하는 특성에 차이가 있다. 리스트 나란히 저장된 자료구조로 중복된 데이터를 저장할 수 있다. 순서가 있고, 중복을 허용한다. 일렬로 늘어선 자료를 저장하기 때문에 선형 자료구조 라고 부른다. 배열과 비슷하게 볼 수 있지만, 배열과 전혀 다른 형태를 가지고 있다. 배열은 메모리가 연속적으로 위치해 있지만, 연결 리스트의 원소는 각자 메모리를 가지고 다음 원소를 가리키는 형식으로 구서현된다. 각 요소들을 노드 라고 부르며, c언어로 표현하자면 포인터로 다음 요소의 주소값을 가리키고, 자바로 표현하면 다음 요소를 참조하는 방식으로 연결된다. 연결리스트는 많이 사용하는 자..

https://rvrlo.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84Graph [자료구조] 그래프(Graph) Graph - 선형 자료구조로 표현하기 어려운 다:다 관계를 가지는 원소를 표현 G = ( V , E ) vertex 정점: 대상이나 개체 → V : 정점의 집합 edge 간선: 정점 간의 관계 → E : 간선의 집합 그래프는 정점과 rvrlo.tistory.com 그래프 탐색을 알기 위해 그래프에 대한 기본 지식이 있어야 한다. 그래프 탐색의 가장 대표적인 DFS와 BFS 깊이 우선 탐색 Depth First Search : DFS 현재 정점과 인접한 간선들을 하나씩 검사하다가 아직 방문하지..