📝 Algorithm

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 그래프, 다익스트라 연습을 하려고 시도했던 문제이다. 기존에 그래프를 순회할 때 아래처럼 많이 사용했었는데, 시간초과가 나서 idx로 큐에 접근하는 방법으로 수정했다. while let q = queue.isEmpty() ? nil : queue.removeFirst() X부터 큐(일반 배열)에 넣음 (거리배열dist는 ma..

처음에 생각했던 풀이 1. 딕셔너리 생성 = "의상의 종류":["의상이름"] 2. 범위 (1...의상의 종류 수) dp 테이블 만들기 3. dp 테이블 결과 반환 이 순서대로 그림을 그리고 규칙을 찾아 dp 테이블을 만들어 해결하려 했었다.. 규칙을 찾고 싶었는데, 감만 오고.. 생각했던 대로 해결되지 않아서 "프로그래머스의 질문하기"를 확인해봤는데 명쾌한 수학적 풀이가 있어서 기록해두고자 한다. 고등학생 때 이 문제를 봤으면 좀 더 빠르게 해결방식을 알아냈을 듯 하다,,ㅎ.ㅎ 해결 방식 의상의 종류 1가지 상의일 경우 반환값 = 상의 개수 (아래부턴 편의상 "개수" 생략) 의상의 종류 2가지 상의, 하의일 경우 반환값 = 상의 + 하의 + 상의 * 하의 의상의 종류 3가지 상의, 하의, 신발일 경우 반..

알고리즘 스터디하면서 재귀에 대해 잘 이해하고 쓰지 못했던 경험이 있다. 피보나치나 팩토리얼 문제 정도는 괜찮은데, 이해도가 조금 부족했어서 그 이상은 체화되지 않아, 쉽게 재귀를 떠올려 사용하지 못했었다. 이번에 코테를 준비하면서, 여러 문제를 풀기보단 부족했던 기본 개념에 대해 다시 이해하고 넘어가보자!라는 마음으로 순열과 조합을 들여다보았고, 순열과 조합을 알아가면서 재귀에 대해서도 자연스레 체화할 수 있었다-!!! 순열 (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 ..

import Foundation func checkLowerCase(_ input: String) -> Bool { let lowercaseSet = CharacterSet.lowercaseLetters return input.rangeOfCharacter(from: lowercaseSet.inverted) == nil } let st = ["ss", "s1", "11", "SS", "d-"] for s in st { if checkLowerCase(s) { print(s) } } // ss https://developer.apple.com/documentation/foundation/characterset

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