개발 공부 기록

Question https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 💡 Solution 아래는 예제 입력으로 주어진 수열입니다. -7 -3 -2 5 8 위 예시에서 부분 수열의 합이 0이 되는 경우는 {-3, -2, 5}으로 한 가지입니다. 우선 정답을 찾기 위해 첫 번째 인덱스인 -7부터 탐색합니다. 예를 들어, {-7, -3, -2}와 {-3, -2}라는 부분 수열이 있다고 생각해봅시다. 둘의 차이점은 보시다..

Question https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 💡 Solution 가장 먼저 팀을 나누기 위해 visited 배열을 이용하여 N명까지 모든 조합을 탐색합니다. 이때 방문한(true) 사람들은 start팀으로, 방문하지 않은(false) 사람들은 link팀으로 구분합니다. 팀을 나눌 때 중요한 점은, 이미 탐색한 사람은 다시 visited를 false로 설정하여 다른 조합을 구성할 수 있도록 합니다. solve가 N / 2만큼 호출되어 팀이 모두 나..

백트래킹이란 DFS와 주로 함께 사용되는 알고리즘 전략으로, 가능한 모든 경로를 탐색하는 도중 해답이 될 가능성이 없다고 판단되는 경로는 더 이상 탐색하지 않고 이전 분기점으로 돌아갑니다. 즉, 불필요한 경로는 조기에 차단하여 탐색의 효율성을 높입니다. 이를 문제 풀이에 적용하여 다시 말하자면, 우리는 경로를 찾기 위하여 현재 노드에서 다음 노드로 나아갈 수 있는 모든 경우를 재귀적으로 찾습니다. 이때 노드가 제한된 조건에 위배된다면 해당 노드를 제외하고 이전의 노드로 돌아가 다음 노드를 확인하는 방식입니다. 즉, DFS를 통해 모든 노드를 탐색하며 더 이상 필요하지 않는 부분들은 쳐내는 방식을 백트래킹이라고 생각하면 됩니다. https://www.acmicpc.net/problem/2580 2580번:..