[프로그래머스] 타겟넘버 Swift (DFS)

완전 기초라서 사실 어렵지는 않았는데, 그냥 문제 풀다가 한번 적어보고 싶어서 기록용으로 남김

 

 

난이도 자체는 크게 어렵다? 느껴질 정도는 아닌데, 알고리즘 놓은지가 너무 오래되어서 머릿속에서는 이렇게 저렇게 하면 되는데 코드로 어떻게 풀어내야 하는지 감이 잡히지 않았음

 

게다가 운영체제나 시스템 프로그래밍 AI에 최적화 된 OS를 만드는 것이 원래 가장 하고 싶은 연구라서 C언어를 주력으로 쓰고 있다가 ..

취업하려면 우선 코테 먼저 뚫어야 그 담에 뭘 봐준다고 해서 Python 3으로 알고리즘 공부 하다가 ... 

iOS 개발의 경우에는 Swift 5로 언어 제한을 두는 곳도 생겨서 Swift 5로 ... 

 

이런 과정을 거치면서 언어의 대혼란이 오는 시기인 것 같음 ㅠ

 

어떤 코테는 종이랑 펜도 불가능하다고 해서 머릿속으로 상상으로만 해야한다는데, 일단 모르겠고 공부하는 중이니까 그냥 그림 그리면서 하기로 함

머릿속으로 하는게 진짜 잘하는 거라던데 ㅜ

 

✅ 코드

//
//  File.swift
//  algorithm
//
//  Created by Hamlit Jason on 2021/08/08.
//

/* 타겟넘버
 https://programmers.co.kr/learn/courses/30/lessons/43165
 DFS 사용
 */

import Foundation

var ans = 0;
func solution(_ numbers:[Int], _ target:Int) -> Int {
    
    dfs(numbers, target, 0, 0)
    return ans
}

func dfs(_ numbers: [Int],_ target : Int,_ sum : Int,_ idx : Int) {
    
    if (idx >= numbers.count) {
        if(sum==target) {
            ans+=1
        }
        return
    }
    
    dfs(numbers, target, sum+numbers[idx], idx+1)
    dfs(numbers, target, sum-numbers[idx], idx+1)
    
}

//print(solution([1, 1, 1, 1, 1], 3))

 

 

사실 대부분의 코테는 OS 연구할 때 처럼 알고리즘의 극한으로 가져가지 않아도 되는데, divide and conquer (분할 정복) 이 방식에 너무 강하게 사로잡혀 있어서 간단한 문제를 어떻게 하면 최적화 시킬지 계속 사로잡혀 있었던 것 같음.

 

아무튼 아래의 논리로 풀어낼 수 있었다!

 

재귀의 로직을 보자면...