https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 처음에는 문제가 잘 이해되지 않았지만, 결론적으로 이 문제는 연속으로 이어진 5개의 노드가 있는지 확인하는 문제이다. 따라서, DFS를 이용해 연결된 5개의 노드가 있는지 확인하면 된다. for 문을 이용해 0~N-1번을 각각 시작점으로 둔다. 그리고 인접한 노드를 찾은 뒤, 방문하지 않았다면 다시 인접 노드를 탐색한다. 이렇게 쭉 들어가다가 5번째 노드를 찾으면 종료하고, 찾지 못 했다면 이전의 노드로 돌아온다. 이 때, 이전 노드로 돌아왔다면 방금 찾았던 노드는 방문 체크를 해제해줘야 한다. ..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net * 풀이 첫번째 시도에서는 N x N 크기의 2차원 배열을 만들어 가능한 퀸의 자리를 모두 체크하는 방식을 떠올렸지만 잘 되지 않았다. 하지만 퀸끼리는 1) 같은 행 2) 같은 열 3) 대각선에 놓을 수 없기 때문에 1차원 배열로도 표현할 수 있었다. x축을 인덱스, y축을 값으로 보아 [1,3,0,2] 라면 0열 1행, 1열 3행, 2열 0행, 3열 2행에 퀸이 놓아지는 형식이다. 이렇게 표현한다면 순열 형식으..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 재귀 함수를 이용해 N개의 수열의 부분 집합을 모두 구한 뒤, 합이 S인 경우에 cnt를 1 더해준다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class..

https://www.acmicpc.net/problem/9742 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 풀이 주어진 문자열에 대한 모든 순열을 찾는 재귀함수를 작성한다. 찾은 문자열의 개수를 받는 변수 num을 만들어준 뒤, num이 N번째일 때 해당 순열을 출력하고 재귀를 멈춘다. 만약 모든 순열을 찾았는데도 N번째가 되지 못한 경우 No permutation을 출력한다. + 입력값의 개수가 정해져있기 않기 때문에 EOF 처리가 필요하다. EOF 처리 EOF란? End of File, 데이터 소스로부터..