문제 출처 : https://www.acmicpc.net/problem/11047분류 : 그리디 백준 11047 동전0동전을 N종류 가지고 있을 때 K원을 만드는 최소 동전의 개수아무런 조건이 없다고 가정할 때, 큰 것 부터 골라야 최소를 만들 수 있을까? 다음의 예를 보자. 우리는 다음 주어진 가격의 동전을 가지고 있다고 하자.10, 50, 60100원을 만드려고 그리디하게 구하면 60,10,10,10,10이 나오는데실제로 100원을 만드는 최소는 50,50이다.즉, 무조건 큰 것 부터 고르면 안된다는 말이 된다. 그렇다면 어떻게 그리디하게 동전의 최소 갯수를 만들 수 있을까?다시 예로 돌아가 보자.5, 40, 70으로 120원을 만들 경우 70, 40, 5, 5 또는 40, 40, 40이 된다. 이 ..
문제 출처 : https://algospot.com/judge/problem/read/DICTIONARY 이 문제에서 얻어 갈 수 포인트는 위상정렬을 한 후 유효성을 검증하는 것이다. 위상정렬은 DAG에서만 그 유효성을 입증 받을 수 있는데, 이 문제의 경우 주어진 그래프가 DAG가 아닐 수도 있다. 처음에 인접행렬방식으로 그래프를 만든다면, 위상정렬을 모두 마친 후 아래와 같은 방법으로 싸이클의 여부를 알아 낼 수 있다. 위상정렬한 결과 i번 노드와 j번 노드가 순서대로 있다면( i -> j ) j번째 노드에서 i번째로 가는 간선이 있다면 DAG가 아닌것이 되는 것이다. 그것을 인접행렬에서 모두 확인해 주면 된다.(인접 리스트라면 간선의 여부를 찾는데 시간이 더 소요될 것이다) 코드는 아래와 같다. 1..
알고리즘 공부[1] 그래프 (C++)
안녕하세요. 오늘은 그래프에 관하여 알아보겠습니다.그래프는 여러 알고리즘 문제에서 등장하며, 관련된 알고리즘 또한 많기 때문에 잘 알고 있는 것이 중요하다고 생각합니다. Contents그래프그래프의 종류그래프의 경로그래프의 표현 그래프그래프는 vertex(정점)들의 집합 V와 edge(간선)들의 집합인 E로 구성된 자료구조입니다.그렇다면 우리는 그래프를 간략하게로 표현할 수가 있죠. 이러한 표현에서 눈치를 채신 분들도 있겠지만!그래프를 정의하는데 있어서 간선의 길이 그리고 정점의 위치는 신경쓰지 않습니다.정점이 어디에 있든, 간선이 길이와 상관 없이 각 정점과 정점을 이어주는 간선의 유무로만 그래프를 정의합니다. 그래프의 종류그래프의 종류에는 여러가지가 있습니다. 아래 나타난 것 말고도 여러 기준에 따라..