민혁이의 IT스토리

문제 설명n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.-1+1+1+1+1 = 3+1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3+1+1+1+1-1 = 3사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.제한 사항- 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.- 각 숫자는 1 이상 50 이하인 자연수입니다.- 타겟 넘버는 1 이상 1000 ..

www.acmicpc.net/problem/2667 문제 풀이 위에 그림 처럼 지도가 주어지고 연결된 영역을 찾아야 하므로 그래프 탐색 문제로 판단했다. 모든 정점을 방문해야해서 DFS 혹은 BFS 모드 가능하지만 비교적으로 쉬운 재귀를 이용한 DFS로 구현해 보았다. 추상화된 흐름문제의 요구 조건은 단지의 갯수와 하나의 단지에 몇개의 집이 있는지 물어본다. 단순하게 생각해보자, 일단 그래프를 정해진 방향으로 순회를 하면서 집(1)을 만나면 연결되어 있는 또 다른 집을 찾고, 업다면 다른 단지를 찾아서 또 다시 순회하면 된다. 이렇게 했을 때 시간복잡도는 O(N^2)이다. 1. 순회오른쪽으로 가면서 집을 찾는다. 2. 확인한 집은 지우고 단지 정복하기 3. 새로운 단지 찾기 해결 과정전체 지도를 순..

DFS란 무엇일까?DFS는 그래프 탐색 알고리즘 중 하나로, 한 방향으로 끝까지 파고 들어간 뒤 더 이상 진행할 수 없을 때 다시 돌아와 다른 경로를 탐색하는 방식이에요. 트리 탐색이나 미로 문제 같은 곳에서 자주 등장합니다. 👉 쉽게 말하면, "갈 수 있는 길이 있으면 계속 들어가고, 막히면 돌아와서 다른 길을 찾는 방법"이에요. 동작 방식DFS의 핵심 아이디어는 스택(Stack) 구조입니다.재귀 함수를 사용하면 내부적으로 스택이 사용되기 때문에 구현이 간단해집니다.동작 순서를 정리하면:시작 노드에서 출발아직 방문하지 않은 인접 노드를 하나 골라 방문더 이상 방문할 노드가 없으면 이전 노드로 돌아감 (백트래킹)모든 노드를 방문할 때까지 반복 DFS의 특징 장점구현이 간단하다 (특히 재귀 활용 시)그..