목록알고리즘/알고리즘 공부 (7)

코딩스토리

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
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
확장 유클리드 호제법

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

오랜만에 블로그에 알고리즘 관련 글을 작성하는 것 같은데.. 절대 알고리즘에 손을 놓고 있던 게 아니라 우리 학교 알고리즘 소학회에 참여하느라 ㅎㅎ.. ( KOALA 뽜이팅!!) LCS 알고리즘은 DP를 공부했던 시점부터 계속 공부해야지, 공부해야지 했던 알고리즘인데 결국 오늘에서야 공부했다. ( 다음 주 학회의 주제가 마침 DP여서도 있고 ) 어쨌든 LCS 알고리즘에 대해 알아보면 Longest Common Subsequence, 즉 최장 공통부분 수열이라는 뜻이다. 만약 ACAYKP 란 문자열과 CAPCAK 란 두 개의 문자열이 주어졌을 때, LCS = ACAK 가 된다. 최장 길이 문자열과 살짝 헷갈릴 수 있는데, 우리가 구해야 하는 LCS는 최장 부분 공통 수열, 즉 수열이다. 수열이란 뜻은 결국..
알고리즘/알고리즘 공부 2021. 1. 15. 23:40
트리 - 우선순위 큐와 힙

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 23장 우선순위 큐와 힙에 나온 내용을 바탕으로 작성하였습니다. 개요 우리는 기존에 "큐(Queue)"라는 자료구조를 배웠었다. 큐는 스택과 비슷한 자료구조로 '선입선출'이라는 형태를 갖추고 있다. 그렇다면 우선순위 큐와 큐의 차이점은 무엇일까? 바로 '우선순위', 즉 선입선출 구조이나 '우선순위'대로 원소를 꺼낼 수 있다는 점이다. 우선순위를 만족하게 정렬하려면 여러가지 방법이 있다. 가장 단순한 방법은 O(n)이라는 시간에 모든 원소를 비교해서 정렬할 수 있다. 하지만 당연히 이 방법은 사용하지 않을 것이다. 이진 탐색 트리(Binary Search Tree)를 사용하면 O(logn)의 시간에 정렬할 수 있지만 이는 책의 표현을 빌려 쓰자면 "닭 ..
알고리즘/알고리즘 공부 2020. 10. 2. 18:42
Prev 1 2 Next