본문 바로가기

🐍 Algorithm32

[알고리즘/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.

[알고리즘/Swift] BOJ 4803 트리 :: 그래프, DFS + Python 💡 풀이 방법 연결된 노드를 저장할 2차원 배열 graph, 방문처리를 위한 1차원 배열 visited 이 필요하다. DFS 를 통해 트리가 아닌지를 확인하고 트리의 개수를 세는데, 노드 전체를 방문할 수 있도록 방문하지 않은 노드에 대해 DFS 를 수행한다. 👀 DFS 과정에서 트리가 아닌지 확인하는 방법은 ?! 문제에서 주어진 "트리는 사이클이 없는 연결 요소이다." 를 통해,, 트리를 탐색하는데 사이클이 생긴다면, 트리가 아닌 것임을 체크한다. graph 배열에서는 연결된 노드를 전체 저장하므로, 이전에 방문한 노드를 사이클로 인식할 수 도 있다. 이를 방지하기 위해 다음 노드와 이전 노드가 같은지 확인하는 작업을 추가한다. (이전 노드 == 다음 노드) 는 이미 지나온 길이므로 DFS 를 수행하지.. 2021. 5. 30.

[알고리즘/Swift] BOJ 1743 음식물 피하기 :: 그래프, DFS/BFS Swift 로 풀어보는 그래프 문제입니다! 이번주에 Swift 스터디에서 그래프를 나가는데, 알고리즘 스터디에서도 그래프 문제풀이가 주제이네요 😀 개념과 문제를 동시에 접하니까 좋아요! 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진 www.acmicpc.net 👀 풀이 방법 입력으로 주어지는 좌표를 가지고 그래프(2차원 배열의 맵)을 만들 수 있어요! 좌표 (r, c) 는 2차원 배열에서 arr[r-1][c-1] 과 같이 접근할 수 있습니다. (문제가 좀 특이한데..) 통로에 떨어진 음식물 .. 2021. 5. 27.

[알고리즘/Swift] BOJ 14725 개미굴 :: 문자열, 트라이 트리 (Trie Tree) 알고리즘 스터디 지난주 주제는 "문자열" 이었습니다. 트라이 트리를 활용한 문제가 인상적이었고, 많이 활용되는 알고리즘이라고 합니다. 이번주 Swift 알고리즘 책에서도 트리 중, 트라이 트리를 공부해서 정리해보려고 합니다! 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 👀 풀이 방법 이 문제에서는 아래 그림으로 힌트를 줬어요. 처음 문제를 봤을 땐 트라이 트리를 모르는 상태였지만, 아.. 뭔가 트리구조를 활용해야하는 구나를 알게 되었죠! 그래서 찾아보니, 트라이 트리를 활용해서 푸는 문제라는 .. 2021. 5. 26.

이전 1 2 3 4 다음

티스토리툴바