본문 바로가기

분류 전체보기715

[구름톤 챌린지] 16일차 - 연합 [Python] 풀이 N개의 섬에 대해 양방향으로 연결된 그룹의 개수를 구하는 문제다. 입력시에는 단방향으로만 입력받아야 한다. 1 ~ N 번 노드에 대해 방문하지 않은 노드에대해 bfs를 해주면 된다. 정점 u부터 시작해 연결 가능한 모든 정점을 확인하며, 양방향인 경우에만 방문표시와 함께 다음 탐색대상으로 포함시키면된다. 더 이상 탐색할 수 있는 정점이 없다면 bfs를 종료하며 1을 반환해 그룹의 개수를 증가시키면 된다. 출처 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 2023. 9. 6.
[백준 28282] 운명 [Python] 풀이 왼쪽(L), 오른쪽(R) 각각 총 X개씩 1 ~ K번의 양말을 가지고 있다. 양말 개수의 제곱보다 양말 색상의 제곱에 대해 양말의 짝을 찾는게 더 빠르기 때문에 양말에 대한 정보를 입력받을 때 각 색상의 개수를 세주자. 이제 왼쪽 1 ~ K번 색상의 양말 중 존재하는 양말에 대해 오른쪽 양말과 짝을 지어준다. 만약 중복되는 양말짝이 있을 수 있기에, 앞서 미리 세주었던 개수만큼 곱한 값을 더해주자. pypy3로 제출했다. 소스코드 소스코드 보기 출처 28282번: 운명 동원이는 왼발 전용 양말을 총 4개 가지고 있으며, 각 양말의 색은 1, 3, 2, 4번 색이다. 동원이는 오른발 전용 양말을 총 4개 가지고 있으며, 각 양말의 색은 3, 1, 1, 5번 색이다. 동원이가 양쪽 발에 www.acmi.. 2023. 9. 5.
[백준 26350] Good Coin Denomination [Python] 풀이 화폐의 단위에 대해 화폐 간 최소 두배 이상일 때 "Good coin denominations!", 그렇지 않을 때 "Bad coin denominations!"를 출력해주면 되는 문제다. 두배 이상이 아닐 때 까지 loop를 돌며 비교를 하고, 만약 모든 화폐가 두배 이상이라는 조건을 만족한지 아닌지에 따라 알맞는 문구를 출력해주자. 소스코드 소스코드 보기 출처 26350번: Good Coin Denomination Different countries use different coin denominations. For example, the USA uses 1, 5, 10, and 25. A desirable property of coin denominations is to have each co.. 2023. 9. 2.
[구름톤 챌린지] 15일차 - 과일구매 [Python] 풀이 N개의 과일에 대해 1원당 포만감이 많은 과일을 최대한 K만큼 구할 때 최대 포만감을 구하는 문제다. 입력형식은 과열의 가격 P와 포만감 C로 주어지며, 1원당 포만감은 C / P로 구할 수 있다. 정렬을 위해 1원당 포만감을 첫 번째 요소로 두고, 최대 몇번 먹을 수 있는지 P를 두 번째 요소로 저장해주자. C / P 가 높은 과일을 우선적으로 구매하는 것이 이득이기 때문에, DESC 정렬을 해준 후 탐색을 진행하자. 만약 남은 K가 P 이상이라면(한 과일을 전부 구매할 수 있다면) 원래 과일 한 개의 포만감 만큼 계산해주면 된다. 남은 K가 부족해 한 개의 과일을 전부 구매하지 못한다면, K개의 조각(fruit_slice)만 구매해주자. 위 과정을 거쳐 K가 0이라면 탐색을 중단하고 그렇지 않다.. 2023. 9. 2.
[구름톤 챌린지] 14일차 - 작은 노드 [Python] 풀이 입력받은 양방향 그래프에 대해 정점 K부터 시작해 연결된 정점 중 번호가 작은 정점을 우선적으로 방문하는 문제다. 이미 방문한 정점을 다시 방문해서는 안되며, self-loop는 존재하지 않는다. 번호가 작은 정점을 우선적으로 방문하므로 미리 정렬해주자. dfs를 loop로 구현했다. 정점K부터 시작해 방문한 모든 정점을 방문표시해주며, 현재 정점과 연결된 반대 정점 중 방문하지 않은 정점에 대해 탐색하는 방법이다. 만약 더 이상 다른 정점으로 방문이 불가능한 경우 loop를 빠져나오며, 지금까지 방문한 정점의 갯수와 마지막으로 방문한 정점의 번호를 출력하면 된다. 출처 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 2023. 8. 31.
[구름톤 챌린지] 13일차 - 발전기 (2) [Python] 풀이 이전에 풀었던 문제의 응용버전이다. [구름톤 챌린지] 12일차 - 발전기 풀이 집에 전력을 공급하기 위해서는 그 집에 발전기를 설치하거나, 해당 집 주변에 전력이 공급되고 있는 집이 있어야 한다. 즉, 상하좌우로 붙어있는 집의 그룹이 몇 개인지 구하는 문제이다. kyr-db.tistory.com 이전에는 단순히 집이 있는지 아닌지에 따라 그리고 인접했는지 아닌지에 따라 그룹화 해주었다. 이번에는 집의 유형(house_type)과 인접여부에 따라 그룹화를 진행해주면 된다. 동일 유형의 집이고 인접방향일 때마다 다음 탐색 대상에 넣어주면서 그룹에 속할 수 있는 집의 갯수를 세주어야 한다. 탐색이 끝난 후 만약 그룹에 속한 집의 갯수가 K개 이상이라면 "단지"가 될 수 있다. 각 집의 유형별 존재하는 단.. 2023. 8. 31.

티스토리툴바