본문 바로가기

재귀4

[Swift][프로그래머스][DFS] 네트워크 요구능력 : DFS 재귀 코드설명 : 네트워크가 따로따로(?)있는게 몇개인지 구하는 문제이다. 예를 들어서 1번과 2번이 연결되어 있고 3번은 따로있으면 네트워크는 2개이다. 만약 1번과 2번과 3번이 모두 연결되어있지 않으면 네트워크는 3개이다 1번과 2번과 3번이 모두 연결되어있으면 네트워크는 1개이다. 나는 우선 연결그래프를 만들어주었다. 이렇게 노드의 개수와 연결된 간선이 주어지는 경우에는 연결그래프를 만들어주고 문제를 푸는게 좋다. 만약 입출력 예의 1번같은 경우에는 graph에 다음과 같이 들어갈 것이다. graph = [[0,1], [0,1], [2]] 나는 노드를 0번부터 세어주었다. 그래서 0번노드는 0번과 1번이 연결되어있고, 1번노드도 0번과 1번이 연결되어있고, 2번노드는 2번 자신.. 2022. 3. 15.
[Swift][DFS] 백준 1248번 (맞춰봐) 요구능력 : DFS 재귀 코드설명 : 일단 문제를 이해해야하는데,, 예제입력 1에 적혀있는 -+0++++--+로 예를 들어 설명해보자. 규현이가 쓴 수가 A[]라는 배열에 4개가 저장되어 있다고 가정해보면 A[0]의 합, A[0] ~ A[1]의 합, A[0] ~ A[2]의 합, A[0] ~ A[3]의 합이 음수, 양수, 0으로 구분되어 저장되는 것이라고 보면된다. 예제 출력1처럼 -2 5 -3 1일 때 A[0]의 합, A[0] ~ A[1]의 합, A[0] ~ A[2]의 합, A[0] ~ A[3]의 합을 직접해보면 -+0+가 나오는걸 알 수 있다. 이후에도 A[1]의 합, A[1] ~ A[2]의 합, ... 이렇게 구해보면 문제에서 뭘 구해야하는지 이해가 갈것이다. 나는 처음에 result배열에 그냥 평범.. 2022. 3. 15.
[Swift][BruteForce] 백준 2529번 (부등호) 요구능력 : 백트래킹에 대한 이해 코드설명 : 맨 아래에 수정된 코드있습니다. 이 문제는 0~9까지의 수 중에서 부등호의 갯수 +1 개만큼의 수를 뽑아서 부등호 조건에 맞출 수 있는지를 묻는 문제이다. 문제에서 요구하는 부분 1. 부등호의 개수 + 1개 만큼의 수 2. 뽑은 수를 가지고 부등호 조건을 만족하는지 확인 3. 부등호 조건을 만족하는 수들의 최소값과 최대값 출력 1. 1번부터 해결하면 n과m문제를 떠올리면 된다. 이 문제에서는 0부터 9까지의 수 중에서 선택하라고 했고 선택된 숫자는 모두 달라야한다고 했으므로 방문처리까지 해주면서 방문하는 수를 k + 1 (부등호의 개수 + 1)개 뽑았을 때 부등호조건에 비교하기위해서 result라는 배열에 저장해줬다. for i in 0...9 { if !.. 2021. 11. 8.
[Swift][BruteForce] 백준 14889번(스타트와 링크) 요구능력 : 백트래킹에 대한 이해 코드설명 : 이 문제는 팀을 n명중에서 n/2명을 뽑아야된다는게 핵심이다. 그래서 나는 n과 m을 떠올려서 백트래킹 방법으로 팀부터 뽑았다. 다음으로, 내가 스타트팀원들을 뽑았으니까 링크팀원들은 자동적으로 스타트팀원들을 뺀 사람들이 되겠다. 스타트팀원들을 n/2명을 뽑으면 맨 아래 for문에서 방문처리가 되게된다. 그럼 방문처리가 안된 사람들이 링크팀원들인 것이다. n/2명을 뽑았을 때 team1과 team2를 0으로 초기화해준다.(이전에 뽑았던 값을 재사용하게 되는 경우가 없게하기 위함) 그리고 for문으로 arr배열의 전체 인덱스를 돌아주면서 방문하지 않은것은 링크팀(team2)원들이기 때문에 방문하지 않은경우에 team2에 더해주고 방문했다면, 맨 아래에서 뽑은 스.. 2021. 11. 4.