앱등개발자IOS

연속된 부분수열의 합이어야만 가능한 줄 알고, 처음에는 DP를 이용해 풀이했었다. [연속된 부분수열 합으로 생각하여 DP로 풀이한 코드] 아래 코드가 BackTracking ( 조합 )으로 풀이한 문제이다. ( visited 배열은 사용하려다 사용하지 않았다!)

Swift알고리즘 2023. 9. 4. 17:31

기본적인 DP문제

Swift알고리즘 2023. 9. 4. 14:21

BackTracking문제.

Swift알고리즘 2023. 9. 2. 21:22

Swift가 컴퓨터 환경에 따라 Int32, Int64 등 알맞은 자료형으로 사용해주기는 하지만,,, Swift에서도 Overflow가 존재한다.... 13번 줄에서 새로운 값을 저장할 때 % 연산을 해주지 않으면 Overflow로 인해 "런타임 에러"가 난다. 참고! Overflow허용 연산은 앞에 "&"를 붙여주면 된다! (예)

Swift알고리즘 2023. 9. 2. 15:30

기본 Kruskal 알고리즘 문제

Swift알고리즘 2023. 9. 2. 02:01

이분탐색을 사용하는데, 한 단계 더 깊게 생각해야하는 문제이다. Parametric Search 형태의 문제인데, 이미 주어진 수의 나열에서 어떤 값을 찾는 기본적인 이분탐색이 아니라, 어떤 기준을 정하고, 그 기준에서 나온 start, end로 mid를 구하고 bs()함수에 매개변수로 전달한다! ( 이 문제에서는 우리가 구해야하는 "가장 인접한 공유기 사이의 거리"의 범위를 [1 ~ 맨 오른쪽 집과 맨 왼쪽 집 사이 거리] 로 잡고, 이 값들 사이에서 mid값을 갱신해나가면서 모든 공유기 사이 거리가 mid값 이상일 때, 설치할 수 있는 공유기 수를 bs()함수에서 return 받고, 그 때 조건을 만족하는지 체크하는것. 그 값이 c 이상이라는 것 -> 공유기 간 간격을 더 넓힐 수 있으므로, star..

Swift알고리즘 2023. 9. 2. 01:32

백트래킹은 순열/조합/중복순열/중복조합 을 사용하는 경우가 많은데, 이 문제의 경우, "조합" 문제이다. 1,2,3,4,5,6 중 1,4,5가 같은 팀이 된다는 것은 1,4,5 / 1,5,4, / 4,5,1 / 5,4,1 ... 모두 같은 것을 의미한다. 따라서 dfs() 재귀함수를 호출할 때, 이전에 선택한 숫자의 다음 숫자부터 선택하도록 구현해야한다. 이를 start라는 매개변수로 두었고, for문 안에서 0부터가 아닌 start부터 탐색한다! 이를 처리해주지 않아 시간초과가 났었다.

Swift알고리즘 2023. 9. 1. 11:45

간만에 점화식을 세우기 복잡했던 DP 문제였다. 이 문제처럼 3개 연속 취할 수 없는 규칙이 있는 경우, 마지막으로 밟은 곳이 어디인지를 관리해주는 것이 중요하다. 즉, dp[i]가 의미하는 것은 i번째 계단을 밟는 경우에 취할 수 있는 최댓값이 될 것이다. 그렇다면, dp[i]를 구할 때 고려해야할 것은, 1. i-1 계단을 밟았을 경우 => i-1과 i를 밟는 경우이므로, i-2를 밟을 수 없다. 따라서 쉽게 생각할 수 있는 것이 dp[i-3] + data[i-1]이다. 하지만, dp[i-4] + data[i-1]도 존재한다는 것을 생각해야한다. i-5 i-4 i-3 i-2 i-1 i 와 같이 할 경우 최대가 될 수 있기 때문 2. i-2 계단을 밟았을 경우 => 더이상 신경 쓸 것이 없다. (i-2..

카테고리 없음 2023. 9. 1. 10:53