앱등개발자IOS

기본 최소 스패닝 트리 문제이다. 아이디어를 떠올리기 까다롭지만 떠올리기만 한다면 간단히 구현할 수 있는 문제! 최소 스패닝 트리를 만들고, 마지막에 연결한 edge (비용이 가장 많이 드는 간선)의 값만 빼주면 된다!!

Swift알고리즘 2023. 9. 5. 00:01

DFS문제로 보이나, 단순 DFS로만 풀면 시간초과가 나는 문제. DP개념을 얹어 시간을 단축시켜야한다! 포인트 3가지 1. dfs(x, y) 함수가 의미하는 것 : x, y 위치에서 (n-1, m-1)까지 갈 수 있는 경로의 수 2. 그 경로의 수를 저장하는 곳이 rarr 3. rarr 을 -1로 초기화하는 것은 "방문한 적 없음"을 의미 ( 방문 했었으나, 갈 수 있는 경로가 없을 때 0을 채워야하므로 차이를 둔 것)

Swift알고리즘 2023. 9. 4. 23:37

연속된 부분수열의 합이어야만 가능한 줄 알고, 처음에는 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