목록전체 글 (153)

코딩스토리

Dynamic Programming - Knapsack Algorithm(배낭 알고리즘)

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

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

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번 실행하며 더 많이 이긴 사람이 승리 + ..
알고리즘/BOJ 문제 풀이 2021. 7. 7. 14:11
백준 2517번 - 달리기

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(천억...?) 이..
알고리즘/BOJ 문제 풀이 2021. 6. 19. 21:35
Binary Index Tree(BIT, Fenwick Tree)

# 아래 링크의 글에 보충 설명을 더한 글입니다. 먼저 아래 글을 읽고 이해가 잘 안 되신다면 보는 걸 추천드려요 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를..
알고리즘/알고리즘 공부 2021. 5. 28. 00:12
백준 2042번 - 구간 합 구하기

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 일반적인 Prefix Sum으로 구하면 query로 인해 시간 초과가 발생한다. 따라서 Binary Index Tree(펜윅 트리)를 사용하여 구해야 하는 문제이다. 아래는 BIT에 대한 설명이다. https://kimtaehyun98.tistory.com/112 Binary Index Tree(BIT, Fenwick Tree) # 아래 ..
알고리즘/BOJ 문제 풀이 2021. 5. 28. 00:11
확장 유클리드 호제법

확장 유클리드 호제법 기말 기간이라 밀렸던 문제 해결 기법 강의를 듣고 있는데 확장 유클리드 호제법이 나왔다. 유클리드 호제법을 알고 있었고 가끔씩은 백준 푸는 데 사용했었기 때문에 어렵지 않게 이해하고 넘어가야지 했는데 뭐지? 이해가 안가네? 옛날 같았으면 그냥 에라이 모르겠다 하고 넘어갔을 텐데 뭔가 시험에 나올 것 같다는 강렬한 촉이 와서 정리해봤다. (개인적인 이해를 바탕으로 작성했기 때문에 완벽하진 않아요!) 확장 유클리드 호제법을 이해하려면 먼저 유클리드 호제법을 이해해야 한다. 일명 GCD 알고리즘이라고도 불리며 "수학"이란 카테고리에서는 가장 처음 접하는 알고리즘 다운 알고리즘이다. 자세하게 설명하는 건 생략하고 요약하자면 결국 유클리드 호제법을 간단히 말하면 "log 시간안에 최대공약수를..
알고리즘/알고리즘 공부 2021. 5. 25. 02:57
백준 14289번 - 본대 산책 3

https://www.acmicpc.net/problem/14289 14289번: 본대 산책 3 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 결국 정보대에서 정보대까지 d번만에 가는 경우의 수를 구해야 하는 문제였다. 이를 일반화해보면 "A 노드에서 B 노드까지 d번만에 가는 경우의 수"를 구해야 한다. 이 부분에 dp 스럽게 생각해보면 "A노드에서 B와 연결된 모든 노드까지 d-1번 만에 도착하는 경우의 수들의 합"과 같다. 즉 식으로 나타내면 다음과 같다. dp [i][j][k] = i 노드에서 j 노드까지 k번 만에 도착하는 경우의 수라고 가정해보자. 그렇다면 dp[i][j][k]는 아래와 같이 구할 수 있다. for(int a = 1; a i..
알고리즘/BOJ 문제 풀이 2021. 5. 22. 22:27
Prev 1 ··· 3 4 5 6 7 8 9 ··· 20 Next