문제 링크 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, ..
문제 링크 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net TMI) 백준 solved.ac에서 중간에 1월 18일 문제 풀었는데 왜 다음날로 문제가 누적되었는지 모르겠네요.. 내 연속 기록 살려내!!! (백준 기록에는 잘 뜨는데 무슨 문제인지 파악해 봐야겠습니다) +) 18일날 처음 AC 받으신게 오전 4시 39분이고 이는 솔브드에선 17일로 판정됩다고 합니다. (즉 solved.ac는 백준 잔디랑 별개로 24시 기준이 아니라 오전 6시 기준으로 기록이 된다고 합니다) +) 그니까 UTC..
문제 링크 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 트리 특성을 이해하고 있는지 물어보는 그래프 탐색 문제 입니다. DFS 핵심 문제 중 하나이고 트리의 성질까지 활용할 수 있는 좋은 문제였습니다. 한칸씩 앞으로 전진밖에 못하는 규칙때문에 어떤 게임말을 움직이는 것이 중요한 것이 아닌 누가 먼저하는지가 중요했습니다. 간선의 총합을 일자 직선으로 나타낼 수 있어 결국 긴 직선에서의 턴제였습니다. 리프노드의 깊이가 간선 개수랑 같았습니다. 다시 말하면, 리프노드 깊이의 총 합 = 모든 노드의 간선의 개수 게..
문제 링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP로 점화식을 만들어 풀 수 있지만 DFS로 풀어봤습니다. 문제에서 중요 포인트가 2로 나누어 떨어질 때나 3으로 나누어질 때 반드시 나누기 2나 나누기 3 연산을 하지 않아도 됩니다. 연산 조건을 만족할 때 그 연산을 반드시 실행하지 않아도 된다는 것만 아시면 됩니다. 또 중요한 포인트가 DFS는 불필요한 곳까지 탐색하여 최솟값을 찾을 때 반드시 백트레킹(= 가지치기) 방법을 써야합니다. 아래 해당 코드입니다. // 백트래킹 (가지치기) if(min count ? count : min; return; } // 백트래킹 (가지치기) if(min