일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- swift
- rxswift
- swift 알고리즘
- swift 연속된 부분 수열의 합
- 123 더하기 풀이
- ac swift 풀이
- 1 2 3 더하기 풀이
- swift 2xn 타일링 백준
- swift 프로그래머스
- 백준 2xn 타일링
- swift 9095 풀이
- swift ac 풀이
- ac 투포인터
- swift 2xn 타일링 풀이
- ac 구현 풀이
- swift codility
- 백준 2xn 타일링 풀이
- swift 2xn 타일링
- swift dfs
- swift 백준 9095
- swift ac 문제풀이
- swift gRPC
- iOS Charts
- MVVM
- 연속된 부분 수열의 합 투포인터
- swift algorithm
- swift 연속된 부분 수열의 합 풀이
- 연속된 부분 수열의 합 swift
- ios
- swift ac
- Today
- Total
목록
728x90
iOS/Algorithm
728x90
반응형
(27)
boraBong
💬 문제 https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/ FrogRiverOne coding task - Learn to Code - Codility Find the earliest time when a frog can jump to the other side of a river. app.codility.com 💬 Idea 처음에는 X 크기를 가진 배열을 false로 모두 초기화하여 생성한 뒤, 반복문을 돌며 해당 인덱스의 값을 true로 바꾼 후 조건문을 통해 해당 배열이 모두 true인지 검사해주는 작업을 거쳤었다. 그러나 이렇게 구현하니 반복문 안에 O(N)의 시간복잡도를 가지는 작업이 들어있어 시간 초..
💬 문제 https://app.codility.com/programmers/trainings/1/flood_depth/ 💬 Idea 물 웅덩이는 maxWall이 더 큰 수로 갱신될 때마다 새로운 웅덩이가 생기므로 큰 웅덩이가 갱신될 때 가장 작은 depth를 100000000로 초기화해주었다. 이후 작은 값이 나올 때마다 minLast를 한 웅덩이 내의 가장 작은 값으로 갱신해주었다. 그리고 큰 웅덩이 내에서 작은 웅덩이가 생길 때마다 maxDepth의 값과 비교하여 큰 값을 저장하도록 했다. 💬 풀이 public func solution(_ A : inout [Int]) -> Int { var maxWall = A[0] var last = A[0] var wall = A[0] var minLast = ..
💬 문제 https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/ 처음엔 굉장히 간단한 문제라 생각했지만, 효율성 테스트를 통과하지 못해 굉장히 애를 썼다. O(N^2)의 효율성을 → O(N + M)으로 높이기 위해 구간합을 사용해주었다. 💬 Idea a, c, g, t 각각의 배열을 만들어 (t는 없어도 됨) 알파벳이 나온 구간에는 이전 값 + 1을 해주어 저장해준다. 이후 P를 돌면서 (P) 에서 (Q + 1) 까지의 차가 0 이상일 때 a,c,g,t 중 조건에 해당하는 값을 ans에 append한다. Q + 1 까지인이유: 이전 인덱스와 비교하여 해당 구간에서 알파벳이 등장했는지를 파악하기 위해 배열의 인덱스를 +..
💬 문제 https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/ 💬 Idea O(N**2)의 풀이밖에 떠오르지 않아서 혹시나..? 하고 제출해봤지만 역시나 😊😊!!!! O(N)의 풀이여야 효율성 테스트를 통과할 수 있었다. 따라서 O(N)의 풀이를 도출하려 해봤지만 도저히 O(N)의 시간복잡도를 갖는 풀이가 생각나지 않았다. 그래서 다른 블로그를 참고했는데, 평균값의 원리라는 수학 공식을 새로 알게되었다 !! 평균값의 원리 💡 구간의 평균은 부분구간의 평균 중 가장 작은 부분구간의 평균보다 크다. 평균은 어느 두 수가 있을 때 가장 작은 수보다 큰 값을 가진다. 이 원리로 생각해보았을 때, 원소가 4개인 그룹의 평균은 앞..
Swift Queue(Dequeue) 알고리즘 구현 트러블슈팅 기록 - Queue 구현시 시간초과 에러가 발생한다면? Swift로 알고리즘 문제를 풀면서 큐 알고리즘 관련한 문제가 나올 때 배열을 이용하여 큐를 구현하곤 했었습니다. (Swift에서는 따로 Queue를 지원하지 않기에) 따라서 enqueue를 구현할 때는 append()를, dequeue를 구현할 때에는 자연스레 removeFirst() 함수를 사용해주었습니다. 그런데 최근에 알고리즘 문제를 풀면서 위와 같은 큐 구현방법이 시간 복잡도 측면에서 효율적이지 않다는 것을 알게 되어 트러블슈팅을 기록하고, 효율적인 큐 구현 방법을 공부해보려 합니다 :( :( ⚠️ Swift에서 Queue(Dequeue) 알고리즘을 구현하며 마주한 시간초과 에러..
💬 문제 코딩테스트 연습 - 뒤에 있는 큰 수 찾기 💬 Idea 1. 첫번째 아이디어 기준 인덱스 + 1 부터 끝까지 완전탐색을 하여 기준 인덱스보다 큰 수를 발견하면 answer에 append하고 break하여 이중 포문을 탈출하자. → 하지만, 시간초과가 발생했다. 2. 두번째 아이디어 stack을 사용하여 저장하고 stack의 마지막 원소를 pop해가면서 기준 인덱스와 비교하자. → 인덱스를 같이 저장하기 위해 stack을 튜플 형태로 저장할 수 있도록 하였다. 💬 풀이 실패한 풀이 - 완전탐색 진행 → 테스트케이스 20, 21, 22, 23 시간초과 발생 import Foundation func solution(_ numbers:[Int]) -> [Int] { var ans: [Int] = [] ..
💬 문제 코딩테스트 연습 - 전력망을 둘로 나누기 💬 Idea 1. 첫번째 아이디어 아이디어 - 간선을 가장 많이 갖고있는 노드 사이를 끊자 결과 → 1,6,7 만 성공 .. 반례 전력망 case에서 가장 많은 간선을 갖고있는 노드는 1과 6이다. (각각 3개씩 갖고 있음) [ case 1 ] case1처럼 1과 4 사이를 끊었을 때 -> 각 송전탑의 개수는 3개 / 5개로 차이는 2이 된다. (5-6 사이를 끊어도 동일) 📍 그러나, 이 case에서는 4와 5 사이를 끊는 것이 더 적은 차이값을 도출한다. 아래의 case2를 보자. [ case 2 ] case2처럼 4와 5 사이를 끊었을 때 -> 각 송전탑의 개수는 4개 / 4개로 차이는 0이 된다. (case1보다 더 적은 차이값 도출 !) 따라서 ..
💬 문제 코딩테스트 연습 - 이모티콘 할인행사 💬 Idea 1. 먼저 이모티콘 수에 맞는 할인율 조합을 구하자 💡 어떻게 구할 것인가?→ dfs 재귀함수를 만들어서 할인율(10%, 20%, 30%, 40%) 각각을 돌며 array에 더해주자. 효율성 높이기 - dfs에서 도출되는 불필요한 조합을 줄이자 (꼭 줄이지 않아도 실행결과는 성공합니다!) user가 갖고 있는 가격 기준의 최저값을 구해 sales를 먼저 필터링해주기 ex. user = [[40, 10000], [25, 10000]] 의 경우 유저들이 구입할 최저 세일 비율이 30% 이므로 할인율 중 30%, 40% 만을 갖고 가격 조합을 만들어줄 수 있다. 2. 할인율 조합을 구한 뒤 해당 조합에서 이모티콘플러스 가입자 수와 판매액이 최댓값인지를..