📝 Algorithm/알고리즘

알고리즘 스터디하면서 재귀에 대해 잘 이해하고 쓰지 못했던 경험이 있다. 피보나치나 팩토리얼 문제 정도는 괜찮은데, 이해도가 조금 부족했어서 그 이상은 체화되지 않아, 쉽게 재귀를 떠올려 사용하지 못했었다. 이번에 코테를 준비하면서, 여러 문제를 풀기보단 부족했던 기본 개념에 대해 다시 이해하고 넘어가보자!라는 마음으로 순열과 조합을 들여다보았고, 순열과 조합을 알아가면서 재귀에 대해서도 자연스레 체화할 수 있었다-!!! 순열 (permutation) 순열이란 서로 다른 n개의 원소에서 r개를 중복 없이 순서를 고려하여 선택하거나 나열하는 것을 의미합니다.(단, 0 조합 func 조합(_ depth: Int, _ start: Int) { if 뎁스가 M까지 도달했다면 { 결과배열 출력 } else { 인..

BFS(너비우선탐색) 1. removeFirst() 사용 func bfs(graph: [[Int]], startX: Int, startY: Int) -> [Int] { var visited = Array(repeating: Array(repeating: false, count: n), count: n) var queue = [(startX, startY)] var result = [Int]() visited[startX][startY] = true while let node = queue.isEmpty ? nil : queue.removeFirst() { let x = node.0 let y = node.1 result.append(graph[x][y]) let dx = [0, 0, 1, -1] let ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 해당 문제를 풀면서 누적합을 처음 접했다. 문제를 보고 값을 계산해서 저장해서 꺼내서 사용하면 될 것 같다는 생각은 들었는데, 정확한 해결방법이 누접합!인지는 몰랐다..! 누적합에 대해 알아보자! 누적합 특정 구간의 합을 찾는데 유용한 알고리즘 누적합 알고리즘은 연속된 원소들의 합을 빠르게 계산하는 알고리즘입니다. 배열과 같은 시퀀스 데이터에서 일부 구간의 합을 찾는 데 사..