[BaekJoon] #1260 - DFS와 BFS [Java][C++]
문제 링크 1. 아이디어 주어진 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제로 정점 번호가 작은 것을 먼저 방문해야 한다. 인접 리스트를 활용했는데 이때 정점 번호가 작은 것을 먼저 방문할 수 있게 정렬했다. 인접 리스트의 경우 양방향 연결을 해야 함에 주의해야 한다. 2. 복잡도 접...
문제 링크 1. 아이디어 주어진 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제로 정점 번호가 작은 것을 먼저 방문해야 한다. 인접 리스트를 활용했는데 이때 정점 번호가 작은 것을 먼저 방문할 수 있게 정렬했다. 인접 리스트의 경우 양방향 연결을 해야 함에 주의해야 한다. 2. 복잡도 접...
문제 링크 1. 아이디어 필요한 최소 배추흰지렁이 마리 수는 배추밭에서 연결된 배추들을 한 묶음으로 볼 때, 각 묶음당 한 마리씩 배치하면 된다. 따라서 배추밭의 각 좌표를 순회하며 배추면 해당 배추 묶음을 전부 방문 처리하고 묶음의 수를 세는 과정을 반복하면 된다. 방문 처리를 하면 같은 묶음을 한 번만 셀 수 있으며 구현할 때는 원본 배추...
문제 링크 1. 아이디어 크기가 10인 각 배열에서 3번째로 큰 수를 출력하는 문제로 주어진 배열을 오름차순으로 정렬했을 때, 8번째에 위치한 원소를 찾으면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(T)$ $O(1)$ ...
문제 링크 1. 아이디어 다이나믹 프로그래밍을 활용해 1부터 특정 수를 만들기 위해 필요한 최소 연산 횟수를 구하면 간단하게 해결할 수 있다. 예를 들면 1은 어떤 연산 없이도 바로 만들 수 있으므로 dp[1] = 0이 되며 주어진 연산의 역으로 dp[1 * 3] = 1, dp[1 * 2] = 1, dp[1 + 1] = 1을 구할 수 있다. ...
문제 링크 1. 아이디어 $N$을 $N$번 출력하되 출력하는 문자열의 길이가 $M$자리를 넘어가면 $M$자리만 출력하는 문제다. 2. 복잡도 접근 시간 공간 풀이 $O(N \times D)$ $O(N \times D)$ ...
문제 링크 1. 아이디어 알파벳 소문자로만 이루어진 단어 $S$에서 각 알파벳의 개수를 세는 문제로 카운팅 배열을 활용하면 간단하게 해결할 수 있다. 2. 복잡도 접근 시간 공간 풀이 $O(N)$ $O(N)$ ...
문제 링크 1. 아이디어 날짜의 일의 자리 숫자와 자동차 번호의 일의 자리 숫자가 일치하면 자동차 10부제를 위반한 차량이다. 2. 복잡도 접근 시간 공간 풀이 $O(1)$ $O(1)$ 3. 코드 풀이 [...
문제 링크 1. 아이디어 조건문을 활용해서 나이와 몸무게를 기준으로 분기 처리만 하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(T)$ $O(1)$ ($T$ = 종료 줄을 제외한 테스트 케이스 수) 3...
문제 링크 1. 아이디어 나무 조각의 위치 변경 과정이 버블 정렬 과정과 동일하다. 따라서 버블 정렬을 구현한 뒤 스왑이 발생할 때 현재 나무 조각의 수들을 출력했다. 2. 복잡도 접근 시간 공간 풀이 $O(1)$ $O(1)$ ...
문제 링크 1. 아이디어 오름차순인지 내림차순인지를 판단하는 불 타입 변수들을 활용했다. 현재 음이 이전 음보다 큰지 작은지로 해당 변수를 갱신해서 최종적으로 ascending인지, descending인지, 아니면 mixed인지 판별했다. 2. 복잡도 접근 시간 공간 ...