문제 링크 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 접근법 DFS로 원소를 넣는 경우와 넣지 않는 경우를 탐색한다. (조합) DFS로 탐색하면서 입력 개수에 도달하면 원하는 답인지 확인한다. 이렇게 안하고 매 순간마다 if(sum== answer)을 확인하면 return구분이 복잡해진다. 또한 dfs 탐색으로 깊이를 끝까지 탐색해야 이 문제에서 완전 탐색으로 답을 구할 수 있다. private static void dfs(int idx, int sum) { // df..
문제 링크 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 접근법 [백준 일곱 난쟁이 2309] 는 브루트 포스 기법을 이용해서 푸는 스페셜저지 문제이다. 스페셜저지 문제는 문제의 정답이 여러 가지일 때 유저가 출력한 답이 맞는지 안 맞는지 확인하는 문제이다. 이 문제에서는 9명의 키가 주어진다. 그리고 9명의 키 중에 7개를 골라서 합이 100이 되는 7명을 찾고 그 7명의 키를 오름차순으로 출력해주면 된다. 답이 여러개가 존재할 수도 있어 한 번 일곱 난쟁이가 정해지고 출력을 해주면 flag 변수로 답이 한 번만 ..
문제 링크 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 접근법 이 문제는 일반적인 DFS 문제처럼 풀면 조금 어려울 수 있다. DFS의 재귀(스택) 원리를 정확히 이해하고 그래프의 구조를 파악할 수 있어야 쉽게 풀 수 있다. 문제를 정리하면 친구끼리의 관계는 그래프에서 간선으로 나타낼 수 있다. 앞으로 간선 =관계 라는 것을 알고 있으면 다른 문제에도 그래프 탐색을 고려해봐야 한다. DFS로 리스트에 정점을 넣고 DFS로 깊이가 4인 곳을 찾으면 되는데 문제는 입력값이 트리와 그래프 모두 주어진다. 이 문제를 일반적인 트리로 접근하면 입력 테케 2에서 틀린다. 트리는 두 개의 노드 사이에 1개의 경로만을 가지며 ..
문제 링크 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 접근법 노드의 개수 N (1
문제 링크 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 투포인터란? 투포인터 알고리즘은 슬라이딩 윈도우라고 불리기도 한다. N의 값이 매우 커서 완전 탐색 방식으로 풀면 시간 초과가 날 때 투포인터를 풀면 O(N)으로 풀 수 있다, 1차원 배열이 있고, 배열 안에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 설정한다. 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태의 알고리즘 접근법 sum 값을 비교해서 원하는 값보다 큰 경우, 작은 경우, 같은 경우를 분기해서 start, ..
문제 링크 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 이 문제를 풀기전 구간 합 구하기 4를 꼭 풀기바랍니다. 구간 합 구하기 4가 1차원 배열이라면 이번 문제는 2차원 배열 구간합 문제입니다. 시간 초과 이 문제를 입력 값을 살펴보면 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) (제한 시간 1초) 매번 구간합을 구하면 N^2(1024*1024) * M (10만)으로 빅오에서 시간 초과..
문제 링크 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 트리 특성을 이해하고 있는지 물어보는 그래프 탐색 문제 입니다. DFS 핵심 문제 중 하나이고 트리의 성질까지 활용할 수 있는 좋은 문제였습니다. 한칸씩 앞으로 전진밖에 못하는 규칙때문에 어떤 게임말을 움직이는 것이 중요한 것이 아닌 누가 먼저하는지가 중요했습니다. 간선의 총합을 일자 직선으로 나타낼 수 있어 결국 긴 직선에서의 턴제였습니다. 리프노드의 깊이가 간선 개수랑 같았습니다. 다시 말하면, 리프노드 깊이의 총 합 = 모든 노드의 간선의 개수 게..
문제링크 : https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 삼성 역량평가 IM 수준의 대표 문제입니다. 4방탐색과 BFS, DFS를 이용하는 (2차원 배열) 그래프 탐색문제이다. 백준 게시판을 살펴보니, 이 문제의 가로, 세로 입력을 잘못해서 물어보는 경우가 많았다. public class 이차원배열 { public static void main(String[] args) { int N = 4; // 가로 int M ..