본문 바로가기

전체 글1270

[백준] 11724 연결 요소의 개수 - Graph Theory / Java • 문제 링크 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net • 풀이 과정 무향 그래프의 정점이 모두 연결되어 있고 하위 그래프와 나머지 그래프 사이에 연결이 없을 경우, 이를 연결 요소라 명칭하며 아래의 예시에서는 (0, 1, 2, 3), (4, 5, 6), (7, 8) 총 3개의 연결 요소가 존재한다. 이러한 연결 요소의 개수는 dfs / bfs 로 탐색하여 구할 수 있으며 해당 문제에선 연결 리스트를 활용한 dfs로 풀이하였다. 모든 노드를 .. 2022. 7. 10.
[백준] 16198 에너지 모으기 - Backtracking / Java • 문제 링크 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net • 풀이 과정 구슬을 선택함에 따라 해당 구슬이 제거됨을 구현해야 하므로 List 자료구조를 사용한다. list 변수에 입력받은 값을 재귀 호출 함수를 통해 탐색하여 선택한다. 첫 번째와 마지막 인덱스는 제외하여 탐색하고, 값이 제거됨에 따라 첫 번째와 마지막 인덱스만 남았을 시, 즉 리스트의 크기가 2일 시 해당 분기의 탐색을 종료한다. 현재 인덱스의 이전 인덱스, 다음 인덱스의 값을 곱하여 energy 변수에 더한 후 매개변수로 전달하며, .. 2022. 7. 9.
[백준] 10819 차이를 최대로 - Backtracking / Java • 문제 링크 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net • 풀이 과정 방문 여부를 확인하는 재귀 호출 함수로 입력받은 배열의 중복을 허용하지 않은 모든 순열을 구한다. 순열에 문제에 제시된 (arr[0] - arr[1]) + (arr[1] - arr[2]) + ... + (arr[n - 2] - arr[n - 1]) 의 연산을 수행하는데 이는 배열의 현재 인덱스와 다음 인덱스를 뺀 값을 sum 변수에 연속해서 더하며 식의 최댓값을 구하는 순서를 찾기 위해, 뺄셈의 값은 절대값으로 계산한다. 각각의 순열에서 구해진 연산.. 2022. 7. 8.
[백준] 6603 로또- Backtracking / Java • 문제 링크 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net • 풀이 과정 while 문에서 입력의 한 라인을 StringTokenizer 로 받되, 첫 토큰이 0이 아닐 시에만 탐색을 수행한다. 첫 토큰이 곧 문제상 k값이며 int 배열 arr 와 boolean 배열 visit 의 크기를 k 로 생성하고 원소를 저장한다. 해당 배열을 재귀 함수의 깊이가 6일 때까지 호출하여 탐색하며, 인덱스의 방문 여부를 확인하는 방식으로 구한 각각의 순열을 StringBuilder 에 적절히 줄바꿈하여 하나의.. 2022. 7. 7.
[백준] 9663 N-Queen - Backtracking / Java • 문제 링크 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net • 풀이 과정 탐색을 할 체스판을 1차원 배열로 정의하고 퀸의 위치의 열을 배열의 인덱스 값, 행을 배열의 원소의 값으로 간주하여 접근한다. 예를 들어 n = 4 이고 배열의 값이 [2, 0, 1, 3] 일 경우 체스판의 퀸의 위치는 아래와 같다. 기본적으로 퀸은 자신의 위치 기준 가로, 세로, 대각선을 모두 차지한다. 각각의 퀸을 놓을 수 있는 자리를 탐색할 때 depth 는 행을 의미하며 재귀적으로 0 ~ n 까지의 해당 열의 모든 행을 검사한다. 각 행이 다.. 2022. 7. 6.
[백준] 2529 부등호 - Backtracking / Java • 문제 링크 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net • 풀이 과정 방문 여부를 확인할 boolean 배열을 활용하는 재귀 함수로 모든 순열을 확인하되, 입력으로 주어진 부등호에 맞는 다음 수를 선택하는 함수로 검사하여 다음 수를 결정한다. 이전 인덱스의 수와 현재의 수가 부등호 조건에 맞을 경우에 String 변수에 더하는 방식이며 String 변수의 길이가 비교할 수의 크기와 같을 때 해당 분기 탐색이 완료되었으므로 List 에 더한다. 자연스럽게 모든 순열 중 최대값은 List 의 마지막 인덱.. 2022. 7. 5.

티스토리툴바