문제 n개의 원소를 가진 정수의 집합 S가 주어지고, 임의의 정수 W가 주어졌을 때, 합이 W가 되는 부분집합의 개수와 각 부분집합을 출력하도록 하시오. 입력 첫 줄에 원소의 개수 n과 임의의 정수 W가 주어진다. 둘째 줄에 n개의 정수가 주어진다. 출력 첫 줄에 원소의 합이 W가 되는 부분집합의 개수를 출력한다. 둘째 줄부터 원소의 합이 W가 되는 모든 부분집합을 한 줄에 하나씩 출력한다. 단, 부분집합에서의 원소 출력 순서는 주어진 S의 원소 순서와 동일해야 한다. (백트래킹 순서대로) ※처음 문제를 보고 떠오른 생각 주어진 집합 S의 원소들을 더해서 W를 만들어야 한다. Backtracking을 이용해서 모든 경우의 수를 구한다. 유망성검사를 통해서 가지치기를 함. 만약 뽑은 원소들의 합이 W면 종..
문제 설명 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다. 예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면, (각 손님은 단품메뉴를 2개 이상 주문해야 ..
Backtracking 되추적 알고리즘이라고 한다. 결과를 찾는 도중 막히면 다시 되돌아가서 다시 결과를 찾음. 모든 노드를 탐색해서 만드는 DFS와 비슷하다. DFS vs Backtracking DFS는 모든 노드를 탐색한다. Backtracking은 모든 노드를 탐색하지만, 특정 조건을 설정해서 이 경로가 해가 안될 거라고 판단이 되면 경로를 이탈하고 다시 되돌아간다. --> 이것을 가지치기라고 한다. 가지치기를 통해서 불필요한 경로를 차단해서 효율성을 높일 수 있다. Promising 유망성 검사 - 이 경로가 특정조건을 걸어서 해가 될 것인지 안될 것인지 판단함. nonpromising 하다면, 그 경로는 끝까지 갈 필요가 없으므로, 다시 되돌아감. promising 하다면 계속 진행함. Prun..
문제 다음 소스는 N번째 피보나치를 구하는 C++함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n - 1) + fibonacci(n - 2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. fibonacci(0)은 ..
기존에 c를 하다가 이번에 c++로 넘어오게되었는데, 개인적으로 엄청 편리하다고 생각한 기능이 vector였다. (물론 stack,queue도 많이 쓰지만 그 중에서 가장 유용하다고 생각함 ㅎㅎ..) vector란 C++ STL(Standard Template Library)에 있는 container이다. 쉽게 이해하자면 자동으로 메모리 할당이 되는 배열이라고 생각하면 편하다. --> 자동으로 메모리 할당이 된다는게 엄청나게 큰 이점이고 c++의 장점이라고 생각한다. vector를 사용하기 위해서는 아래처럼 헤더파일을 추가해줘야한다. #include 2)vector 선언방법 vector배열이름; //자료형으로 배열을 만듬. 크기는 0 vector배열이름(size) // size만큼 자료형으로 배열을 만듬..
문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N 줄에는 각각 N개의 자료(0 혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리..
코드를 짜는데 map의 개념이 부족해서 굉장히 시간이 오래 걸렸다. 그래서 부족한 개념을 정리하는데 이 카테고리를 쓸 예정이다. map이란? map을 이해하기 위해서는 set에 대한 이해가 필요합니다. set은 key라고 불리는 원소들의 집합으로 이루어진 컨테이너입니다. key에서 중요한 특징은 중복을 허용하지 않는다는 점입니다. set은 key값의 순서대로 정렬이 되는 특징이 있습니다. 이때의 정렬 방식은 inorder방식을 따릅니다. 중복되면 안 되고 정렬이 되어있다.!! 그럼 map은 무엇이냐? map은 set에서 value값이 추가된 것이라고 보면 된다. map은 set에서 추가된 것이기 때문에 중복을 허용하지 않지만, value는 중복을 허용한다. map의 기본 형태는 map m; map은 pa..
●허프만 코드란? 데이터를 효율적으로 압축하기 위해서 만들어진 알고리즘. 탐욕법을 사용함. 데이터 파일은 통상적으로 이진 코드(binary code)로 표현한다. 각 문자는 코드 워드(code word)라고 하는 유일한 이진 문자열로 표현한다. ●fixed length binary code 각 문자를 표현하는 bit의 개수가 일정하다. 예를 들어 문자의 집합이 {a,b,c}라면 bit 2개만으로 문자를 코드화 할 수 있다. bit 2개로는 4개의 문자를 bit 3개로는 8개의 문자를 표현할 수 있다. a : 00 b:01 c:11 이라고 가정하자. 만약 File이 ababcbbbc라면 결과 코드는 000100011001010110일것이다. ->18비트를 사용한다. ●variable-length binar..
Knapsack Problem(배낭문제) 1)Fractional Knapsack Problem 보석의 무게를 쪼갤 수 있다는 가정을 둔다. 예를 들어 보석이 10kg라도 내가 들고가고싶은 만큼 담아서 가방에 넣을 수 있다. ->greedy를 이용해서 해결 2)0-1 Knapsack Problem 보석의 무게를 쪼 갤 수없다. 예를 들어 보석이 10kg라면 10kg 그대로 가방에 담아야 한다. ->dynamic programming을 이용해서 해결 배낭문제의 목표는 가방에 담는 보석들의 가치 합이 최대가 되야한다. ●Greedy Approach 탐욕법을 통한 전략은 다음과 같다. 단위 무게당 가치가 가장 큰 보석을 담는다. 가방에 최대 무게가 넘지않을때까지 보석을 담는다. 이러한 접근법은 보석을 쪼갤수있는..
