https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 이 문제는 동전 1과 유사한 문제다. 단, 동전 1과 다르게 동전 합의 최소 개수를 구하는 문제다. 동전 합의 최소 개수를 구하기 위해선 그리드 알고리즘이나 DP를 사용하면 된다. 이 문제인 경우 동전의 가치가 배수 관계가 아니기 때문에 DP를 사용해야만 한다. DP 식은 아래와 같다. 동전의 가치인 arr[i-1]에 따라 dp[j]를 구한다. 이때 arr[i-1]..
분류 전체보기
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 DP를 통해 해결해야한다. 예제에 따라 동전 3개인 1, 2, 5를 통해 10을 만들려면 아래와 같은 경우의 수가 존재한다. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 2 1 1 1 1 2 2 2 1 1 2 2 2 2 2 2 2 2 2 1 1 1 1 1 5 1 1 1 2 5 1 2 2 5 5 5 위 경우의 수는 동전 1을 사용할 때 10원..
SOLID란? 객체지향 디자인 원리들을 사용하면 유지보수가 쉽고, 유연하고, 확장이 쉬운 소프트웨어를 개발할 수 있다. 이 원리들은 디자인 패턴보다 범위는 작지만 표준화 작업에서 아키텍처 설계에 이르기까지 다양하게 적용되고 있다. SOLID에는 5가지 원칙이 존재한다. SRP (Single Responsiblity Principle) - 단일 책임 원칙 OCP (Open Closed Principle) - 개방 폐쇄 원칙 LSP (Listov Substiution Principle) - 리스코브 치환 원칙 ISP (Interface Segreation Principle) - 인터페이스 분리 원칙 DIP (Dependency Inverstion Principle) - 의존성 역전 원칙 SOLID를 통해 디..
Array의 특징 Array는 크기가 정해진 캡슐화된 컨테이너 클래스 플릿이다. 크기가 고정되어 있어 heap이 아닌 stack 공간에 원소가 저장된다. 기본 자료형으로 제공하는 고정 배열과 동일한 공간에 저장된다. Array는 원소의 타입과 배열의 크기를 매개변수로 사용한다. Array는 배열이기 때문에 연속된 메모리 공간에 데이터를 저장한다. Array 컨테이너를 사용 시 고정 배열을 사용할 때와 다르게 함수 전달 시 포인터로 형 변환 되지 않는다. 고정 배열보다 Array를 사용하면 내장 멤버 함수를 통해 편리하게 원소에 접근할 수 있다. [], at()을 통한 임의 접근으로 원소에 접근할 수 있다. 생성 및 원소 접근 Array는 요소의 자료형과 원소의 개수를 명시하여 생성할 수 있다. []과 a..
List의 특성 List는 Node 기반 컨테이너이다. List는 이중 연결 리스트(Doubly Linked List)로 구현되어 있다. 이중 연결 리스트 구조로 인해 임의의 위치에 있는 요소에 바로 접근할 수 없다. 원소의 시작과 끝 위치만 기억하기 때문에 임의의 위치에 있는 요소에 접근하기 위해서는 링크를 하나씩 따라가야한다. itr++ // itr ++ itr-- // --itr 가능 itr + 5 // 불가능! List는 Vector와 달리 노드 기반으로 서로 연결되어 있어 원소를 삽입하거나 삭제할 때 모든 원소를 밀어내지 않아 속도가 빠르다. 삭제시 반복자가 가리키는 원소 자체를 삭제해야 원소가 사라지며, 동작자체에서 반복자를 무효화 시키지 않는다. List는 이중 연결 리스트로 구현되어 있여 ..
Vector의 특성 Vector는 동적 배열로 구현되어 있다. 동적이란 프로그램이 실행될 때 무언가가 변화한다는 뜻이다. Vector는 실행 시 원소의 개수가 변할 수 있다. 배열에서 변화할 수 있는 것은 원소의 개수이기 때문이다. Vector는 연속된 메모리를 사용하여 원소를 저장한다. 원소가 가득차게되면 메모리를 요청하여 새로 확보한다. 현재 담을 수 있는 원소의 개수보다 더 큰 메모리 공간을 요청 새 메모리에 현재 원소를 모두 복사 복사한 원소들의 다음 위치에 새 원소를 추가한다. 이전에 사용한 메모리는 반환한다. Vector의 메모리 할당 연산은 큰 비용을 요구한다. 장단점 장점 Vector의 크기는 동적으로 조정이 가능하다. Vector는 [] 연산자를 통해 배열과 같이 특정 인덱스의 원소에 바..
Unordered Map의 특성 표준이 아닌 hash map 대신 unordered_map을 표준으로 정의 마이크로소프트에서도 hash_map보다는 unordered_map을 권장하고 API 문서도 제공 hash map은 성능이 보장되지 않기 때문에 권장되지 않는다. 순서있게 자료를 유지하지 않고, 입력받은 Data를 테이블에 저장한다. 입력받은 Data를 Hash 함수를 통해 Hash Table에 저장하는 것이 핵심 Key-Value 쌍으로 데이터를 저장하고, Key를 통해 Data를 빠르게 찾을 수 있다. Hash 함수를 사용하는 이유 많은 양의 Data를 저장할 때, 검색 속도를 O(1) 수준으로 만들어 버리는 강력한 솔루션이다. 시퀀스 기반의 Vector와 list 등의 검색 속도는 데이터 양에 ..
What? Red - Black Tree는 자가 균형 이진 탐색 트리이다. 레드 - 블랙 트리는 아래와 조건을 만족한다. 모든 노드는 빨간색 혹은 검은색이다. 루트 노드는 검은색이다. 모든 리프 노드들은 검은색이다. (NIL, Null leaf, 자료를 갖고 있지 않고 트리의 끝을 나타내는 노드) 빨간색 노드의 자식은 검은색이다. (빨간색 노드가 연속으로 나올 수 없다 - Double Red) 모든 리프 노드에서 Black Depth는 같다. (리프 노드에서 루트 노드까지 가는 경로에서 검은색 노드의 개수가 같다) Red- Black Tree는 STL의 map, set에서 사용한다. 삽입 과정 레드 블랙 트리에서 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다. 이는 4번 조건을 위배되는..
