[프로그래머스][Python] 네트워크
문제를 정리해보자. A와 B가 직접적으로 연결되어 있고 B와 C가 직접적으로 연결되어 있다면, A와 C는 간접적으로 연결된 것이다. 따라서 A, B, C 모두 연결되어 있다. 이를 모두 같은 네트워크상에 있다고 한다. 몇 개의 네트워크가 있는지 구하는 문제이다. 제한사항과 입출력 예를 보자. [[1, 1, 0], [1, 1, 0], [0, 0, 1]]은 양방향이다. 표로 나타내면 아래와 같다. 1이면 길이 있고, 0이면 길이 없다. 풀이를 생각해보자. 예를 들어보자. 노드는 12개이다. 네트워크는 3개이다. 시작노드 0번을 연결된 노드를 확인한다. 0번 -> 1번 -> 2번 -> 5번 -> 7번 -> 6번 -> 3번 -> 4번 이렇게 직접적으로 연결된 부분을 확인한다. (DFS) 다음 시작노드는 1번이다..
[프로그래머스][Python] 타겟 넘버
문제를 정리해보자. n개의 음이 아닌 정수가 있다. 이 수들을 적절히 더하거나 빼서 원하는 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들어보자. 위와 같이 5가지 방법이 있다. 주의해야 할 점은 연산순서가 바뀐다고 경우의 수가 늘어나지 않는다. 예를 들어 [1, 2, 3]으로 -6을 만든다고 해보자. -1-2-3, -2-1-3, -3-2-1등 다 같은 경우이다. 풀이를 생각해보자. 예를 들어 [1, 1, 2, 3]을 가지고 있다고 해보자. 1. 시작은 1, 2, 3중 하나로 잡는다. (사진에서는 1로 잡았다. 하나를 잡아야 중복되는 결과가 나오지 않는다.) 2. 누적값에 해당 수로 +와 -연산한다. (누적값이 없다면 0으로 시작) 3. 그 값을 누적시킨다. 4. 잡지 않..
