탐욕 알고리즘(그리디 알고리즘) 탐욕 알고리즘 또는 그리디 알고리즘 이라는 것에 대해서 이야기 해봅시다. 탐욕 알고리즘은 주어진 순간 순간마다 가장 최선의 선택을 하는 알고리즘 설계 기법입니다. 매 순간마다 하는 선택은 최선이지만, 전체로 봤을 때는 최적의 선택이라는 보장을 하지는 않습니다. 그리디 알고리즘이 제대로 동작하지 않은 예시로 주로 드는 것은 마쉬멜로우 실험입니다. 예를 들어서, 지금 당장에 마쉬멜로우 1개를 받을 수 있지만, 10분을 기다린 경우 2개의 마쉬멜로우를 받을 수 있는 실험이 있다고 가정해 봅시다. 그리디 알고리즘으로는 지금 당장 1개를 선택하겠지만, 전체로 본다면 10분을 기다린 후에 2개의 마쉬멜로우를 받는게 가장 많은 마쉬멜로우를 받을 수 있을 것 입니다. 그리디 알고리즘은 ..
알고리즘
Stack(스택) 자료구조 구현언어 : C/C++ 사용한 IDE : 비주얼 스튜디오 스택은 먼저들어온 데이터가 가장 나중에 나가는 형태의 자료구조입니다. 반대로 말하면 가장 나중에 들어온 데이터가 가장 처음으로 나가게 됩니다. 이러한 자료구조를 LIFO(Last in first out)라고도 말합니다. 스택 형태 상상해보기 스택은 한쪽이 막혀있는 통의 형태입니다. 통속에 무언가를 넣었을 때 한쪽이 막혀있기 때문에, 처음에 넣은 것을 빼려면 위에 쌓여 있는 다른 것들을 다 빼야 합니다. 아래는 예시 그림입니다. 예를 들어서 위의 그림처럼 한쪽이 막혀있는 통에 숫자가 적혀있는 네모를 1->2->3 순서대로 넣었을 때, 통속에 있는 상자를 다시 빼려면 3->2->1 순으로 나오게 됩니다. 용어 설명 스택의 A..
문제설명 출처 : www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. www.acmicpc.net 평균을 넘는 학생 수 의 비율을 출력하는 문제. 문제풀이 아이디어 그냥 문제의 흐름대로 단순하게 계산. 배열의 길이를 동적으로 할당. 코드 #include #include using namespace std; int main() { int testCase; double average=0; int count = 0; //평균을 넘는 학생 수 cin >> testCase; for (int i = 0; i > N; int..