문제20. 연결 요소 제거하기 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 4주 동안의 구름톤 챌린지의 막을 내리는 문제이다. 지금까지의 문제들을 잘 풀었다면, 오늘 문제도 어렵지 않게 풀 수 있는 DFS/BFS 문제였다. 상하좌우 4가지 방향에 있는 칸들에 대해, 입력받은 p와 같은 경우에만 BFS/DFS를 이용해 파급이 되도록 만들면 된다. 파급이 되는 동안 방문하지 않은 곳이라면 count 를 올려주고, 방문한 곳이라면 해당 칸은 스킵한다. 파급이 끝나면 count의 개수에 따라 "."으로 해당 칸을 바꿀지를 결정하면 된다. 위 내용을 코드로 구현하면 아래와 같다. import sys from collections ..
전체 글
문제19. 대체 경로 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 가중치가 없는 그래프의 최단 경로 탐색 방법에 대한 문제이다. 가중치가 있는 그래프에 대해서는 다익스트라 알고리즘, 벨만-포드 알고리즘, 플루이드 워샬 알고리즘 등을 고려해야 했겠지만, 가중치가 없는 그래프에 대해서는 BFS만을 이용해서 해결할 수 있다. BFS 알고리즘의 특성상, 먼저 큐에 들어간 노드부터 큐에서 꺼내어 쓰기 때문에, 출발지로부터 같은 거리만큼 떨어진 노드는 같은 타이밍에 큐에서 꺼내지게 된다. 당연한 말이지만, 더 멀리 떨어진 노드를 탐색하려면, 가까웠던 노드를 통해서 가야하기 때문에 더 멀리 떨어진 노드보다 가까이에 있는 노드가 더 먼..
문제18. 중첩 점 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 문제의 구현 난이도 자체는 높지 않지만, 무엇을 구현해야 할지에 대한 아이디어를 생각해내는데 조금 시간이 걸리는 문제였다. 우선, 해결책을 비교적 간단하게 떠올릴 수 있도록 단계별로 아이디어를 떠올려보았다. 두 직선이 한 칸에서 중첩이 되려면? 상하 방향으로 뻗은 직선과 좌우로 뻗은 직선이 만나면 중첩이 된다. 상하 방향 직선끼리, 혹은 좌우 방향 직선끼리 만나서는 중첩이 될 수 없다. 해당 칸을 지나가는 직선들의 수를 알고 있을 때, 해당 칸의 중첩 점의 개수를 알 수 있나? 상하 방향의 직선의 개수와 좌우 방향의 직선의 개수를 곱한 값이 해당 칸의 중첩 ..
문제17. 통신망 분석 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 오늘 문제는 그래프 표현 방법들을 알고 있고, 어떤 표현 방식이 적절한지를 판단할 수 있어야 풀 수 있는 문제였다. 오늘 문제의 컴퓨터의 개수, 즉 노드의 개수는 최대 100,000 개이다. 이를 인접행렬을 이용해서 풀기 위해서는 N * N의 이차원 배열이 필요하므로 사용하게 되는 공간은 최대 100,000 * 100,000 = 10,000,000,000 이다. 실제로 인접 행렬 방식으로 문제를 풀어 제출하면, 많은 수의 테스트 케이스에서 Runtime Error가 나는데, 이는 메모리 초과로 인해 발생한 에러이다. 시간적인 문제도 있다. 문제 조건을 보..
문제16. 연합 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 오늘 문제는 유향 그래프에 대한 탐색을 할 수 있는지를 보는 문제이다. 무향 그래프와 유향 그래프는 사실 크게 다르지 않다. 인접행렬 기준으로 설명하자면, 무향 그래프는 array[start_node][end_node]와 array[end_node][start_node]가 같은 값을 가졌고, 어떻게 접근해도 똑같은 결과를 얻었다. 반면에 유향 그래프는 array[start_node][end_node]와 array[end_node][start_node]가 다를 수 있다. 따라서 start_node에서 end_node로 향하는 edge가 있는지를 array[star..
문제15. 과일 구매 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 오늘 문제에서 가장 주의 깊게 보아야할 조건은 바로 "과일을 조각 단위로 구매하는 것이 가능하다"는 조건이다. 이 조건이 없었다면, 과일들의 가격이 다르고, 과일마다 포만감이 다르기 때문에 그리디 알고리즘을 적용할 수 없다. 그럴때는 완전탐색이나 DP 등의 알고리즘을 적용해야 풀 수 있는 문제였을 것이다. 하지만 오늘 문제에는 "과일을 조각 단위로 구매하는 것이 가능하다"는 조건이 있다. 과일을 조각 단위로 구매한다면 가격이 p인 과일 하나를, 가격이 1인 p개의 과일 조각으로 나눌 수 있다. 그리고 이때의 각 과일 조각의 포만감은 c/p가 된다. 이제는 ..
문제14. 작은 노드 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 오늘의 문제는 자료구조 중 하나인 그래프에 대한 기본적인 지식을 알고 있다면 어렵지 않은 문제이다. 그래프는 크게 두 가지 방법으로 표현할 수 있다. 바로 이차원 배열을 사용하는 방식인 인접행렬 방식과, 연결리스트를 사용하는 방식인 인접리스트 방식이다. 두 표현 방법 중 탐색에서 더 큰 효율을 보여주는 방법은 인접행렬 방식이다(단, 메모리 공간을 많이 소모한다는 단점이 있다.). 그래서 이 문제에서 내가 택한 방식은 인접행렬 방식이다. 인접행렬 방식은 이차원 배열의 각 인덱스가 노드가 되고, 두 인덱스로 접근한 배열의 값이 1이면 두 노드 사이에 간선이 있..
문제13. 발전기 (2) 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 문제 해결 방법 오늘 구름톤 챌린지 문제는 어제와 사실상 같은 문제이다. 다만 어제는 1과 0 두 가지 경우로만 고려했다면, 오늘 문제는 1~30의 임의의 수를 고려해야하는 문제이다. 문제를 복잡하게 설명해서 이해하기 어렵지만, 같은 유형 건물이 k 개 이상 붙어있는 곳은 단지가 되고, 가장 많은 단지가 형성된 건물의 유형을 구하면 되는, 사실은 간단한 요구사항을 가진 문제이다. 어제와 같이 BFS를 적용하되 어제는 count를 설치할 발전소의 숫자로 하였다면, 오늘은 k개 이상의 건물이 서로 인접해 있는지를 판단하기 위해, 인접한 건물의 수를 세기 위한 변수로 cou..