코딩스토리

배낭 알고리즘 배낭 알고리즘은 크게 2가지로 나뉜다. 1) 분할 가능 배낭 문제 (Fractional Knapsack Problem) -> 배낭에 담아야 할 물건을 쪼개서 담을 수 있을 때 2) 0 - 1 배낭 문제 (0 - 1 Knapsack Problem) -> 배낭에 담아야 할 물건을 쪼갤 수 없을 때 1번 경우는 보통 그리디 알고리즘으로 해결한다. 뭐.. 풀어보진 않았지만 가치가 높은 물건을 최대한 많이 쪼개서 넣으면 되겠죠? 문제는 2번 경우이다. 사실 0 - 1 배낭 문제는 NP - Complete 문제에 속한다. 알린이라도 NP-Complete는 한 번쯤은 들어봤을 것이다. 내 기억에 NP-Complete 문제 중 하나라도 다항 시간 안에 해결할 수 있다면 모든 NP 문제를 다항 시간에 해결..

SOLID란? "클린 코더"로 유명한 로버트 마틴이 좋은 객체지향 설계를 하기 위한 5가지의 원칙을 제시한 것이다. SOLID는 각각의 원칙의 앞글자를 따서 만들어졌다. SOLID Principles 1. SGP : 단일 책임 원칙 (Single Responsibility Principle) 설명 한 클래스는 하나의 책임만 가져야 한다는 원칙이다. 하나의 클래스는 자신이 담당하고 있는 기능을 수행하는데 집중해야 한다. 따라서 여러 책임을 가지고 있는 클래스가 있다면 각각 개별 클래스로 분할한다. 또는 중복되는 책임을 가지고 있다면 이를 부모 클래스(Super Class)로 정의하여 위임한다. 이를 통해 변경이 있을 때 파급효과가 적어진다(연쇄작용에서 자유롭다). 2. OCP : 개방 폐쇄 원칙 (Open..

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 카드게임의 규칙은 아래와 같다 1. N개의 서로 다른 빨간색 카드 중 M개를 고른다 2. N개의 서로 다른 파란색 카드 중 빨간색 카드의 번호와 같은 카드 M개를 고른다 3. 철수는 빨간색 카드, 민수는 파란색 카드를 가짐 4. 둘은 각각 카드를 한 장씩 내고 번호가 큰 사람이 이김 이 동작을 k번 실행하며 더 많이 이긴 사람이 승리 + ..

https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 문제 분석 문제 내용 자체는 간단하다. A의 등수는 A보다 앞에 있는 사람 중 A보다 달리기 평소 실력이 낮은 친구가 몇 명인지를 알아야 구할 수 있다. 가장 간단한 방법은 당연히 브루트포스이다. 각 인원마다 자신보다 앞에 있는 사람들의 평소 실력을 비교해보면 된다. 이때 문제의 N제한이 50만이기 때문에 당연히 1+2+3+...+50만 = O(50만*50만+1/2) = O(천억...?) 이..

# 아래 링크의 글에 보충 설명을 더한 글입니다. 먼저 아래 글을 읽고 이해가 잘 안 되신다면 보는 걸 추천드려요 https://www.acmicpc.net/blog/view/21 펜윅 트리 (바이너리 인덱스 트리) 블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. Fenwick Tree를 구현하려면, 어떤 수 X www.acmicpc.net Binary Index Tree의 정의는 wiki에 가서 찾아보는게 더 좋을 것이다. BIT의 필요성 BIT란 쉽게 말해 빠른 속도로 구간 합을 구할 수 있게 도와주는 자료구조이다. 이는 Tree를..