백준
-
백준. 11047 동전0 | 파이썬, 그리디 알고리즘IT/알고리즘 해설 2021. 10. 28. 00:31
문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 해설 이 문제는 그리디 알고리즘을 사용한다. 그리디 알고리즘이란, 말그대로 "탐욕적"으로 문제를 해결하는 방식인데, 해결해나가는 과정에서 가장 최선의 선택을 해서 풀어나가는 알고리즘이다. 그렇기 때문에 항상 가장 올바른 답을 도출하지는 않는다. 그러나 속도 면에서 다른 그래프 탐색 알고리즘보다 빠르다는 장점이 있다. 준규는 동전을 총 N종류를 가지고 있고, 이 동전들을 사용해서 K원만큼 만들려고 한다. K원을 만들기 위해서 가장 큰 동전부터 선택해나가면서, K원이 될 때까지 동전을 찾으면 된다...
-
백준 1707. 이분 그래프 (파이썬)IT/알고리즘 해설 2021. 10. 8. 22:05
문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 해설 진짜 역대급으로 삽질했던 문제인 것 같다. 결론부터 말하면 이분 그래프는 dfs나 bfs로 풀 수 있다. 여기서는 dfs로 풀어보기로 한다. 먼저, 이분 그래프가 무엇인지와 dfs가 무엇인지부터 짚고 넘어가보자. 1) 이분 그래프란? - 문제만 보고서는 솔직히 무슨 소리인지 이해가 되질 않았다. 그래서 한참을 문제를 보고 이해하려고 하다가, 결국은 검색으로 해결하였다. (앞으로 문제가 조금 더 친절해졌으면 좋..
-
백준 1038. 감소하는 수 (파이썬)IT/알고리즘 해설 2021. 9. 23. 22:06
문제 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 해설 이 문제는 제대로 안 읽으면 헷갈릴 수 있다. 난이도가 solved.ac 기준 골드 5인데, 문제 자체가 어렵게 쓰여서 골드 5인듯하다. 알고리즘 자체는 어렵지 않다. N번째 감소하는 수란, 0부터 시작해서 감소하는 수 집합에서 N번째 수는 무엇인지 묻는 문제이다. 여기서 감소하는 수란, 주어진 숫자의 맨 첫자리부터 끝자리까지 계속해서 감소하는 수..
-
백준 1012번. 유기농 배추 (C++)IT/알고리즘 해설 2021. 6. 2. 00:47
문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. (한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다) 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇..