본문 바로가기

Study/Algorithm

[12865] 평범한 배낭 https://www.acmicpc.net/problem/12865문제이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.입력첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가.. 더보기
[DP] 문제해결 전략 및 점화식 세우기 https://www.acmicpc.net/step/16백준에서 DP 문제를 해결했다. 아직 두 문제가 남았지만, 이번 DP 문제들은 기존 문제들과는 다르게 생각할만한 것들이 많고, '프로그래밍 사고'의 발전에 도움이 되는 것 같아 자세하게 정리해보려고 한다.DP, 동적 프로그래밍(Dynamic Programming)은 크기가 작은 부분 문제들의 해들을 결합하여 문제를 해결하는 방법을 일컫는다. 이때 분할 정복(Divide and Conquer)과의 차이는 해를 Table에 저장하여 문제를 다시 풀지 않고 테이블에 저장된 결과를 사용하는 상향식 방법이라는 것이다. 이를 통해 불필요하게 중복 계산되는 것을 방지하고, 계산 시간을 줄일 수 있다. 기본적으로 DP는 다음의 순서를 따라서 설계하는게 일반적이다... 더보기
Backtracking 백트래킹 어떠한 문제가 모든 가능성을 조사하지 않고는 해를 구할 수 없는 경우, 모든 가능성을 조직적이고 효율적으로 조사하는 방법 '조사하지 않아도 되는 부분은 조사 대상에서 제외, 해를 빨리 찾는다.' 이러한 백트래킹의 해는 어떠한 제한조건을 만족하는 n개의 원소로 구성된 벡터인 (x1, x2, x3, ..., xn)의 형태로 나타낼 수 있다. 이러한 이유는, 해의 표현을 어떻게 정하느냐 하는 것은 알고리즘의 설계 방향 및 시간복잡도를 결정하기 때문에 위와 같이 단순한 형태로 나타낸다. 따라서, 해를 결정하는 과정에서 아니다 싶은 것은 사전에 제거하는데, 이때 DFS의 변형을 통해 가지치기하여 결정한다. 분기한정 백트래킹과 유사하나, 해를 찾기 위해 백트래킹과 같이 어느 특정한 운행 방법뿐만 아니라 깊.. 더보기
P/NP & Approximation Algorithm 1. 해결 가능한 문제/해결 불가능한 문제 P-완비 문제들은 현실적인 시간내에 풀 수 없는 문제들 (지수시간)이다. 다항식 시간, 현실적인 시간 -> 입력의 크기 n의 다항식으로 표시되는 시간 비다항식 시간, 비현실적인 시간 -> 지수시간, 계승시간 등 2. 결정적 문제 / 최적화 문제 결정적 문제: Yes/No 문제, 존재의 여부 파악 최적화 문제: 문제의 최적값을 찾는 문제 3. NP 완전문제 결정적 문제에만 국한되는 문제이지만, 최적화 문제와 밀접환 관계를 가진다. 결정문제가 풀린다면 최적화 문제도 풀리고 결정문제가 안풀린다면 최적화 문제도 안풀린다. 4. P/NP P: 다항식 시간 내에 결정 문제 해결 가능 NP: P를 포함, 아직 P라고 해결되지 않은 문제, 해를 제공, 해당 해가 Yes임을 다.. 더보기
[Algorithm] Dynamic Programming 동적계획법 Divide & Conquer방식과 유사하나, 차이점은 다음과 같다. [DC] 분할 -> 정복 -> 결합: 공유되는 문제도 다시 해결 [DP] 분할 -> 정복 -> 테이블에 해당 값 저장 -> 분할 된 문제에 적용 저장된 결과를 사용하여 문제해결, 공유되는 문제는 다시 해결하지 않는다. DP는 상향식 접근 방법으로 1. 문제의 해를 구할 수 있는 재귀적인 성질을 설정 2. 작은문제 해결 후 큰 문제의 해를 table에 저장 3. 크기가 작은 문제의 해를 table에 저장, 크기가 큰 문제를 효율적으로 해결한다. 이항계수 구하기 sol.1 recursion int bio1(int n, int k) { if(k == 0 || k ==n) return 1; return (bio(n-1, k-1) +.. 더보기
[Algorithm] Greedy Algorithm 욕심쟁이 기법 단계별로 연속된 선택을 함으로써 문제에 대한 해 백터(solution vector)를 구해나간다. 또한 각 단계별 선택은 전체적으로 최적인(Globally optimal) 선택을 하는 것이 아니라, 정해진 어떠한 선택 기준에 의해 그 단계에서 가장 최선인 선택, 즉 국지적으로 최적인(Locally optimal) 선택을 하는 것이다. 동전 교환 문제 단순 반복문 사용하여 동전의 개수를 최소화 하는 문제 가장 액수가 큰 동전을 차감하는 반복문을 사용한다. 테이프 장치 최적 공간 배정 문제 모든 프로그램에 대한 평균 검색 시간을 최소화하는 프로그램의 저장 순서를 결정하는 문제 가장 용량이 작은 프로그램을 순차적으로 할당한다. 분수 배낭 문제 각 물건의 무게를 Xi라고 할 때, Xi의 값이 0또.. 더보기
[Algorithm] Divide & Conquer 분할정복 주어진 문제를 크기가 작은 여러개의 부분문제로 분할(Divide)하여 부분 문제를 정복(Conquer)한 후에 그 해들을 결합(Combine), 원래 문제에 대한 해를 구하는 재귀방식의 알고리즘 주로 재귀적인 특성을 갖춘 경우가 많다. 알고리즘이 재귀 호출에 의한 경우 그 알고리즘의 수행 시간은 순환 방정식에 의해 표현 가능하다. 가령, T(n)을 입력 크기가 n인 문제에 대한 시간 복잡도 함수라 가정하자. 만일, 문제 크기가 1일 때, 직접 해를 구할 수 있다면, 그때의 시간 복잡도 함수는 C(상수)로 표현이 가능할 것이다. 또한 어떤 문제가 크기 n/b인 a개의 부분문제들로 분할된다고 가정하자. 만약 문제를 분할하는데 d(n)의 시간이 걸리고, 부분 문제들의 해를 결합하여 원래의 문제의 해를.. 더보기
[Algorithm] BFS 탐색 시, 너비를 우선으로 탐색하는 기법으로 시작점과 가까운 것 위주로 탐색한다. 이러한 BFS의 특징은 맹목적 탐색 과 최단길이 보장이다. 0. Queue에 start 노드를 넣는다. 1. Queue에서 하나의 노드를 꺼낸다. 2. 해당 노드에 연결된 노드중 방분하지 않은 노드를 방문하여 차례대로 큐에 삽입한다. 3. 1-2 과정을 Queue에 요소가 남지 않을 때 까지 반복한다. #include #include #include #define MAX_NODE INT_MAX using namespace std; bool visited[MAX_NODE];// Queue의 요소에 접근하였다는 것을 알려주는 배열 vector array[MAX_NODE + 1];// 요소가 들어있는 vector graph vo.. 더보기

티스토리툴바