![]()
문제 설명 레스토랑을 운영하던 스카피는 코로나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)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리..
![]()
●허프만 코드란? 데이터를 효율적으로 압축하기 위해서 만들어진 알고리즘. 탐욕법을 사용함. 데이터 파일은 통상적으로 이진 코드(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 탐욕법을 통한 전략은 다음과 같다. 단위 무게당 가치가 가장 큰 보석을 담는다. 가방에 최대 무게가 넘지않을때까지 보석을 담는다. 이러한 접근법은 보석을 쪼갤수있는..
![]()
Scheduling problem은 운영체제에서 다루는 개념이다. 최대한 적은 시간을 사용하면서 많은 작업을 해야 효율적이다 어떻게 하면 효율적으로 배치할 수 있을까? ●FCFS(First-come , First served) 들어온 순서대로 일을 시작한다. 도착 순서는 P1->P2->P3이라고 가정하자. FCFS의 방식은 p1이 먼저 도착했으니까 p1의 일을 다 끝내기 전까지 p2, p3는 일을 시작하지 못한다. P1, P2, P3의 모든 작업이 끝나는데 소요되는 시간은 30이지만, P1, P2, P3가 기다리는 시간은 24+27 = 51이다. p2, p3는 p1에 비해 굉장히 적은 시간을 사용하는 작업임에도 불구하고 p1이 끝날 때까지 기다려야 한다. 이러한 알고리즘은 굉장히 효율적이지 못하다. ●S..
