[BaekJoon] #15651 - N과 M (3) [Java][C++]
문제 링크 1. 아이디어 1부터 $N$까지의 수 중 길이가 $M$인 중복 순열을 모두 구하는 문제로 재귀를 활용해서 구하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(M \times N^M)$ $O(M)$ ...
문제 링크 1. 아이디어 1부터 $N$까지의 수 중 길이가 $M$인 중복 순열을 모두 구하는 문제로 재귀를 활용해서 구하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(M \times N^M)$ $O(M)$ ...
문제 링크 1. 아이디어 1부터 $N$까지의 수 중 길이가 $M$인 조합을 모두 구하는 문제로 재귀를 활용해서 구하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(M \times 2^N)$ $O(M)$ ($N...
문제 링크 1. 아이디어 1부터 $N$까지의 수 중 길이가 $M$인 순열을 모두 구하는 문제로 재귀를 활용해서 방문 체크를 하며 구하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(M \times N! / (N - M)!)$ ...
문제 링크 1. 아이디어 각 지점에서 목표지점까지의 최단 거리를 구하는 문제로 BFS를 이용하면 해결할 수 있다. 각 지점에서 매번 목표 지점까지의 거리를 구하는 것이 아니라 목표 지점에서 각 지점까지의 거리를 구하는 방식으로 한 번의 BFS로 모든 지점까지의 거리를 구할 수 있으며 이를 2차원 배열 dist에 저장했다. dist의 경우 초기...
문제 링크 1. 아이디어 무방향 그래프에서 연결 요소의 개수를 구하는 문제로 BFS나 DFS를 활용해서 각 노드에 대해 방문하지 않았으면 모든 연결된 노드를 방문 처리하고 개수를 하나씩 세도 되며, 유니온 파인드 알고리즘을 활용해서 서로소 집합을 만든 후 집합의 그룹장의 개수를 세어도 된다. 2. 복잡도 접근...
문제 링크 1. 아이디어 테스트 케이스별로 9회 동안 각 팀의 점수 합을 더해서 비교만 하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(T)$ $O(1)$ ($T$ = 테스트 케이스 수) 3. 코드 ...
문제 링크 1. 아이디어 사탕을 나누는 것은 몫으로, 남은 사탕은 나머지를 구하는 것으로 간단하게 구할 수 있다. 2. 복잡도 접근 시간 공간 풀이 $O(T)$ $O(1)$ ($T$ = 테스트 케이스 수) ...
문제 링크 1. 아이디어 주어진 지도에서 섬의 개수를 구하는 문제로 대각선으로 연결되어도 동일한 섬이라서 대각선까지 탐색하는 팔방 탐색을 활용하면 된다. 지도의 각 좌표에 대해 땅이면 해당 땅이 위치한 섬의 모든 땅을 방문 처리를 하는 과정을 반복하는 방식으로 해결할 수 있다. 2. 복잡도 접근 시...
문제 링크 1. 아이디어 주어진 지도의 모든 좌표를 순회하며 집이 있는 곳이면 단지의 크기를 구하고 개수를 세면 된다. 단지의 크기는 BFS나 DFS를 활용해서 구하면 되고 이를 오름차순으로 정렬해서 출력했다. 2. 복잡도 접근 시간 공간 BFS ...
문제 링크 1. 아이디어 치즈는 외부 공기와 두 변 이상 접촉한 경우 한 시간 후에 사라진다. 이때 모눈종이의 가장자리는 치즈가 놓이지 않는 것으로 가정하므로 무한 루프를 돌며 모눈종이 가장자리 중 임의의 좌표에서 BFS를 통해 두 번 이상 치즈가 존재하는 것으로 판단된 좌표들을 찾아서 녹이는 방식으로 해결했다. 치즈가 존재하는 좌표를 발견...