이 문제가 왜 그리디 알고리즘인지 궁금해서 검색해봤다. 그리디 알고리즘은 '최적의 답'을 찾는 것을 목적으로 하는데, 만약 입력값 즉 로프의 한계 중량이 50 90 100으로 나왔다고 치자. 첫번째 케이스로 50 90 100을 모두 사용하면 최대 중량은 150이고, 90 100만을 사용하면 180이다. 이렇게 50을 사용하지 않았을 경우 최적의 답을 낼 수 있어 그리디 알고리즘 문제라고 하는 것이다. 문제 해결 과정은 이렇다. /* * 배열에 입력 숫자 넣고 오름차순 정렬 * list 0 1 2 * 50 90 100 * 입력한 K값 즉 로프의 개수값에서 1씩 빼가며 다음 행동을 수행 * for(i는 0에서 k까지) *compare[k] = list[i] * k //list[3] = 150, list[2]..
문제 해결 알고리즘 1. list에 입력한 바이너리 문자열을 넣는다. 2. 0과 1중 무엇을 뒤집을 지 결정하는 잣대로 연속된 1과 0의 개수를 세도록 한다. 3. 어떻게 연속된 1과 0의 개수를 세느냐 - for문에서 list[i]와 list[i+1]의 변화가 있으면 count, 없으면 넘어가도록 - 0과 1을 구분하기 위해 cnt0, cnt1 변수를 따로 저장하고, list[i+1]이 0이면 cnt0++, 1이면 cnt1++를 실행한다. 4. cnt1와 cnt0중에 적은 것을 출력한다. #include #include using namespace std; int main() { int cnt1, cnt0; char s[1000000]; cin >> s; if (s[0] == '1') { cnt1 = ..
Greedy Algorithms(탐욕법, 탐욕 알고리즘) : 문제 해결 과정에서 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행, 최종 해답에 도달하는 문제 해결 방식이다. 당장 눈앞에 보이는 최적의 상황만을 쫓는다. 문제를 풀며 이해해보자. 거스름돈(BOJ 5585번) #include using namespace std; int main() { int n; cin >> n; // 잔돈 n = 1000 - n; int result = 0; //잔돈의 개수 result += n / 500; // 500원 개수 n %= 500; result += n / 100; n %= 100; result += n / 50; n %= 50; result += n / 10; n %= 10; result += n ..
문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수..
Graph란? : 노드와 엣지(정점과 간선)으로 이루어진 자료구조를 의미한다. 그래프 알고리즘을 이용해, 매트릭스나 연결 리스트로 문제에서 주어진 노드들의 관계를 표현한다. 그래프의 탐색 기법은 4가지로 나뉠 수 있다. 1. BFS 탐색 : 현재 정점과 연결된 정점들을 우선적으로 넓게 탐색! 큐(Queue)를 이용해서 구현, 즉 방문한 노드들을 차례로 저장한 후 꺼낼 수 있도록 한다. >큐가 뭐죠? 더보기 큐(Queue) : 컴퓨터의 기본적인 자료 구조 중 하나로, First in first out 구조로 데이터를 저장한다. 스택과 반대개념 이진 트리의 level order과 동일 chanhuiseok.github.io/posts/ds-2/ 자료구조 - 이진 트리의 Level order traversal..
