분류 전체보기

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬 알고리즘을 알고 이 문제를 풀면 완벽히 이해할 수 있다. https://solution-is-here.tistory.com/124 [알고리즘] 위상정렬(topological sorting) 파이썬으로 마스터 하기 위상정렬은 순서가 정해져 있는 작업을 수행할 때 차례대로 수행할 수 있도록 도와주는 정렬 알고리즘의 일종입니다. 위상정렬의 수행과정은 ..

안녕하세요! 오늘은 제가 서포터즈로 활동하게 된 체리 워크에 대해 소개하는 시간을 가져보려고 합니다! 우선 체리 워크는 블록체인 기반 기부 플랫폼 ‘체리’에서 운영하는 서비스입니다. 체리는 누적 후원금액이 70억, 후원 횟수가 10만 건이 넘을 정도로 요즘 인기 있는 플랫폼이라고 말할 수 있습니다. 요즘은 모두가 어려운 시기라고 생각합니다. 나 혼자 살기도 어려운데 남까지 돕기는 힘들다는 의견을 다들 가지곤 하죠. 이러한 생각은 지표에서도 나타납니다. 위 그래프에서도 볼 수 있듯이 2021년 기준 ‘경제적 여력이 없음’이 기부를 하지 않는 이유 중 무려 45.4%나 차지하는 모습을 확인할 수 있습니다. 그런데 체리 워크는 내가 내 돈을 사용하지 않아도 기부를 할 수 있다는 점에서 요즘과 같이 모두가 어려..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 스택과 그리디 알고리즘을 섞은 문제다. 첫째 줄에 N과 K가 주어지고, 둘째 줄에는 N자리 숫자가 주어진다. N자리 숫자에서 K개의 숫자를 지워서 가장 큰 수를 만드는 것이 이 문제다. 입력과 출력을 비교했을때 앞에 있는 작은 수들을 지워야 숫자가 커지는 것을 알 수가 있다. 나는 리스트를 하나 만들어서 숫자를 넣은 뒤, 뒤에 있는 숫자와 비교해서 더 작으면 제거하는 방식으로 접근했다. 코드와 함께 설명하겠다. 1 2 3 4 5 for n in mission_nu..

위상정렬은 순서가 정해져 있는 작업을 수행할 때 차례대로 수행할 수 있도록 도와주는 정렬 알고리즘의 일종입니다. 위상정렬의 수행과정은 크게 3가지로 나눌 수 있습니다. 1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음 2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제 3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다. -출처 위키백과 말로만 들으면 약간 어렵게 느껴질 수 있습니다. 그림과 함께 설명하겠습니다. 자기 자신을 가리키는 변이 없는 꼭짓점은 (5,7,3)으로 찾을 수 있습니다. 5를 가지고 2단계를 수행하면 5->11 이 변을 삭제하는 것입니다. 그리고 7을 가지고 2단계를 실행시키면 7->11, 7->8 두 개의 변이 삭제 ..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 이 문제는 전형적인 그리디 알고리즘 문제다. 그리디 알고리즘은 선택의 순간마다 당장의 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 최적값을 구하는데 사용되는 방법이다. 문제에서는 수를 적절히 묶어 최대 값이 나오게 하는 것이 최적 값이다. 보통 이런 문제는 첫째 줄에 수열의 크기가 주어진다. 둘째 줄부터는 n개의 수가 주어진다. 우리는 이 문제를 풀때 몇 가지 상황을 ..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 이 문제는 이렇게 쉽다고?? 이런 생각이 들었던 문제 같다. 첫째 줄에 카드의 개수가 주어진다. 둘째 줄부터는 카드가 주어진다. ex) 카드가 10,20,40 이렇게 주어지면 (10 + 20) + (30 + 40) 이렇게 계산을 한다. 이것을 보고 카드를 오름차순으로 정렬을 하고 리스트를 하나 만든 뒤, 더한 값을 리스트에 추가할 생각을 했다. 1 2 3 4 heap = [] num..