[BaekJoon] #6603 - 로또 [Java][C++]
문제 링크 1. 아이디어 1부터 49 사이의 수 중 하나인 $k$개의 수들에 대해 6개를 뽑는 모든 조합을 구하는 문제로 재귀를 활용해서 구하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(T \times K^6)$ $O(K)...
문제 링크 1. 아이디어 1부터 49 사이의 수 중 하나인 $k$개의 수들에 대해 6개를 뽑는 모든 조합을 구하는 문제로 재귀를 활용해서 구하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(T \times K^6)$ $O(K)...
문제 링크 1. 아이디어 초대할 사람은 상근이의 친구와 친구의 친구까지다. 상근이를 기준으로 거리가 2 이내인 모든 사람의 수를 구하면 되므로 최단 거리 BFS를 활용해서 개수를 세었다. 2. 복잡도 접근 시간 공간 풀이 $O(N + M)...
문제 링크 1. 아이디어 최단 거리 BFS를 활용하면 해결할 수 있는 문제로 BFS로 상근이를 이동시키면서 동시에 불도 이동시키는 방식으로 해결했다. 불이 붙으려는 칸으로도 이동할 수 없으므로 불을 먼저 이동시키고 상근이를 이동시켰다. 2. 복잡도 접근 시간 공간 ...
문제 링크 1. 아이디어 최단 거리 BFS를 활용하면 해결할 수 있는 문제로 $S$층부터 $U$층 위로 가거나 $D$층 아래로 가는 과정을 반복하면 된다. 이때 건물의 최소 높이보다 낮은 층이나 최대 높이보다 높은 층으로 가지 않도록 주의해야 한다. 2. 복잡도 접근 시간 공간 ...
문제 링크 1. 아이디어 최단 거리 BFS를 활용하면 해결할 수 있는 문제로 BFS로 지훈이를 이동시키면서 동시에 불도 이동시키는 방식으로 해결했다. 불이 붙으려는 칸으로도 이동할 수 없으므로 불을 먼저 이동시키고 지훈이를 이동시켰다. 2. 복잡도 접근 시간 공간 ...
문제 링크 1. 아이디어 촌수계산은 사람을 노드, 거리를 길이가 1인 간선으로 치환한 그래프에서 두 노드 간 최단 거리를 구하는 것과 동일하다. BFS를 활용해서 촌수를 구하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(N^2)$ ...
문제 링크 1. 아이디어 정수 $A$를 $B$로 바꾸는 문제로 최단 거리 BFS를 활용해서 $A$ 또는 $B$에 각 연산을 적용해보며 수가 나오는지 판단하는 방식으로 풀 수도 있고, 그리디 알고리즘을 활용하여 $B$를 $A$로 만들 수 있는지 판단하는 방식으로도 해결할 수 있다. $B$가 현재 짝수일 경우는 이전 수가 첫 번째 연산을 통해 ...
문제 링크 1. 아이디어 $N$개의 자연수 중 길이가 $M$인 중복 조합을 모두 구하는 문제로 재귀를 활용해서 구하면 된다. 이때 중복되는 중복 조합은 출력하지 않아야 하는데 이는 prv 변수에 최근에 담은 수를 저장하고 반복문 내에서 동일한 수면 건너뛰면 된다. 2. 복잡도 접근 시간 ...
문제 링크 1. 아이디어 $N$개의 자연수 중 길이가 $M$인 중복 순열을 모두 구하는 문제로 재귀를 활용해서 구하면 된다. 이때 중복되는 중복 순열은 출력하지 않아야 하는데 이는 prv 변수에 최근에 담은 수를 저장하고 반복문 내에서 동일한 수면 건너뛰면 된다. 2. 복잡도 접근 시간 ...
문제 링크 1. 아이디어 $N$개의 자연수 중 길이가 $M$인 조합을 모두 구하는 문제로 재귀를 활용해서 구하면 된다. 이때 중복되는 조합은 출력하지 않아야 하는데 이는 prv 변수에 최근에 담은 수를 저장하고 반복문 내에서 동일한 수면 건너뛰면 된다. 2. 복잡도 접근 시간 공간 ...