본문 바로가기

🐍 Algorithm35

[99클럽 코테 스터디 5일차 TIL] 백준 수열 Swift 오늘의 문제- 백준 수열- https://www.acmicpc.net/problem/2559 오늘의 학습 키워드- N 의 크기와 시간 복잡도- 투 포인터 접근 방법N 의 크기와 시간 복잡도- 입력이 2 - 단순하게 2차원 반복문으로 배열에서 연속적인 합을 구하게 되면- 최대 시간 복잡도는 N * N = 00,000,000,000 이 될 수 도 있다. 투 포인터- 범위를 지정해서 전체 합을 구해야 하는데, 2차원 반복문으로 계산하기에는 시간 복잡도가 크기에 다른 방식을 찾아야 했다.- 시작, 끝 지점을 계산해놓고, 순서대로 인덱스를 증가시키면서 계산하면 시간 복잡도가 줄어들 수 있다. 문제 풀이// 매일 9시 학교에서 측정한 온도// 3 -2 -4 -9 0 3 7 13 8 -3// 연속적인 며칠 동안의 .. 2025. 4. 5.

[99클럽 코테 스터디 4일차 TIL] 백준 안전 영역 Swift 오늘의 문제- 백준 안전 영역- https://www.acmicpc.net/problem/2468 오늘의 학습 키워드- BFS(너비 우선 탐색), DFS(깊이 우선 탐색)- BFS + Queue- DFS + Stack BFS (너비 우선 탐색) - 최단 거리, 최소 횟수, 최소 비용 같은 최소 문제를 해결 할 때 자주 사용된다.- 모든 경우를 한 단계씩 탐색하기 때문에 최단 거리 문제에서 유리하다.- Queue 를 사용해서 같은 레벨 순으로 탐색하기 때문에 최단 거리를 자연스럽게 구할 수 있다.- 그래프에서 연결된 영역을 탐색하는 문제에서도 유용하다.- 섬의 개수 찾기, 감염된 영역 구하기, 색칠된 영역 구하기 등 .. DFS (깊이 우선 탐색)- 그래프나 트리에서 한 방향으로 끝까지 탐색한 후, 다시 .. 2025. 4. 3.

[99클럽 코테 스터디 2일차 TIL] 백준 피보나치 비스무리한 수열 Swift 오늘의 문제- 백준 피보나치 비스무리한 수열- https://www.acmicpc.net/problem/14495오늘의 학습 키워드- 재귀함수의 문제점, 다이나믹 프로그래밍 (DP) 방식, 피보나치 수열 잘못된 접근 1. 단순하게 재귀 함수로 f(n) = f(n-1) + f(n-3) 로 도전해보았으나 런타임 에러가 발생했다.- 일반적으로 함수 호출이 많아질 경우에는 런타임 에러가 발생한다.- 함수 호출 스택이 쌓이기 때문에 제한이 되는게 아닐까 싶다.2. 중간에 계산한 결과를 Array 에 저장하고 빠르게 반환하도록 했지만, 함수 호출이 많아 런타임 에러로 실패했다.3. 1 해결 방법- 재귀 함수가 아닌 반복문을 이용해 피보나치 비스무리한 수열의 값을 계산했다.- 반복문을 돌면서 해당 인덱스의 값을 계.. 2025. 4. 2.

[알고리즘/Swift] 그래프탐색(DFS/BFS) - 타겟넘버, 네트워크, 단어변환, 여행경로 1. 타겟 넘버 (DFS) 1을 더하거나 뺄 수 있기 때문에, 더하거나 빼는 경우에 대해 한번씩 DFS 를 수행해준다. 이를 그래프로 그려보면 이해하기 쉽다. 숫자를 하나 더하거나 빼는 것을 그래프의 깊이 탐색이라고 생각하면 된다. import Foundation func dfs(numbers: [Int], target: Int, i: Int, total: Int) -> Int { if i == numbers.count { return total == target ? 1 : 0 } let count1 = dfs(numbers: numbers, target: target, i: i+1, total: total - numbers[i]) let count2 = dfs(numbers: numbers, targe.. 2021. 7. 21.

[알고리즘/Swift] 해시 - 베스트앨범 Swift 스터디 11주차 - 해시 :: 위장, 베스트앨범 [알고리즘/Swift] 프로그래머스 - 위장 (해시) Python3 로 풀었던 문제를 Swift 로 다시 풀어봤어요. iOS 개발을 좀더 효율적으로 하기위해서 Swift 데이터구조, 알고리즘 공부의 필요성을 느꼈습니다. 🤔 '위장' 문제에 대한 접근 방법은 이전 포 jellysong.tistory.com 👀 첫번째 풀이 # 딕셔너리 형태 playDict 는 ["장르" : (총 재생곡수, [재생곡수])] 형태의 딕셔너리이다. 같은 장르의 총 재생곡수에 따라 1차 정렬을 해줘야하기 때문에, 총 재생곡수를 추가적으로 저장했다. musicDict 는 ["장르_재생곡수" : [고유번호]] 형태의 딕셔너리이다. 같은 장르에 같은 재생곡수를 가진 노래가 여러.. 2021. 7. 6.

[알고리즘/Swift] 정렬 문제풀이 - K번째수, 가장 큰 수, H-Index Swift 스터디 10주차 6/24 스터디 4주차 챕터였던 "정렬 알고리즘" 에서 삽입 정렬, 병합 정렬, 퀵 정렬에 대해 학습했었습니다. 이와 관련되서 프로그래머스의 정렬 챕터를 통해 알고리즘 문제 풀이를 진행했습니다. ✔︎ K번째수 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하는 문제이다. 👀 입출력 array : Int 배열, 1 2021. 6. 25.

[알고리즘/Swift] 스택/큐 문제풀이 - 프로그래머스 기능개발, 프린터, 다리를 지나는 트럭 Swift 스터디 9주차 6/15 . 스터디 3주차 챕터였던 "고급 데이터 구조의 활용" 에서 스택, 큐, 순환 버퍼, 우선순위 큐, 연결 리스트에 대해 학습했었습니다. 이와 관련되서 알고리즘 문제 풀이를 진행했고, 프로그래머스의 스택/큐 챕터를 풀었습니다. [Swift] 스터디 3주차 - 스위프트 데이터 구조와 알고리즘 5/4 진행했던 스위프트 데이터 구조와 알고리즘 책의 3장 '스위프트 고급 데이터 구조의 활용' 스터디 정리입니다! 👀 3장 요약 3장에서는 Swift 기본 데이터 구조 중 Collections (Array, Dictionary, Set) jellysong.tistory.com ✔︎ 기능개발 💡 참고 사항 "뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다." -> Queue.. 2021. 6. 16.

[알고리즘/Swift] BOJ 1038 감소하는 수 - 완전 탐색 🤔 문제 유형 :: 브루트포스(완전탐색) / 백트래킹 💡 풀이 방법 ✔︎ 감소하는 수가 어떻게 구성되는지 먼저 생각해본다. 👉 n 자리의 숫자라면 첫째 자리가 고정되어있을 때, 두번째는 첫째 자리보다 작은 값으로, 세번째는 두번째 자리보다 작은 값으로, n번째 자리는 n-1 번째 자리보다 작은 값으로 구성된다. ✔︎ 문제를 풀면서 참고해야 하는 사항들 감소하는 수의 최대값은 9876543210으로, 최대 자리수는 10자리이다. 감소하는 수의 최소값은 0으로, 최소 자리수는 1이다. 감소하는 수의 개수는 1022개이다. N = 1023 부터는 -1을 출력해야 한다. ✔︎ 풀이를 정리하자면 ?! 자리 수를 지정하고, 자리수에 따라 감소하는 수를 찾는다. --- 0 부터 9까지 반복한다. (혹은 1 ~ 10).. 2021. 6. 9.

[알고리즘/Swift] BOJ 1644 소수의 연속합 - 투 포인터 & 에라토스테네스의 체 👀 필요한 공부 에라토스테네스의 체 소수를 판별하는 알고리즘. 투 포인터 일차원 배열에서 두 개의 포인터를 지정해 계산하는 방법 💡 풀이 방법 위에서 언급한 두 개념을 전부 적용해서 문제를 풀면 됩니다. 먼저, 에라토스테네스의 체를 이용해 소수를 찾습니다. 찾은 소수 배열을 통해 투 포인터로 접근해서 연속된 소수의 합으로 N 이 만드는 경우의 수를 체크하면 됩니다! checkPrimes 함수 :: 에라토스테네스의 체를 이용해 소수를 판별하는 함수 findSeries 함수 :: 투 포인터를 이용해 연속된 소수의 합으로 자연수를 나타낼 수 있는 경우의 수를 세는 함수 🐥 Swift 풀이 // 소수의 연속합 func checkPrimes(n: Int, isPrimes: inout [Bool]) { // 2 부.. 2021. 6. 1.

이전 1 2 3 4 다음

티스토리툴바