📝 Algorithm

서강 그라운드https://www.acmicpc.net/problem/14938    풀이다익스트라 1. 1부터 N까지 BFS 반복하면서 최댓값 업데이트2. 다음 큐의 cost 더했을 때 수색범위 안이고, 다음 큐의 갯수를 더했을 때 현재 아이템 갯수보다 크다면 큐에 추가하기3. 큐에 들어간 아이템들은 전부 갈 수 있으므로 Set로 관리. bfs 끝난 후 Set에 들어있는 아이템에 해당하는 비용 추가해서 bfs 반환  소스코드let NMR = readLine()!.split(separator: " ").map { Int($0)! }let N = NMR[0], M = NMR[1], R = NMR[2]var items: [Int] = [0]items += (readLine()!.split(separato..

간선 이어가기2 문제https://www.acmicpc.net/problem/14284     다익스트라 알고리즘으로 해결하면 되는 문제이다.bfs로 순회하며, dp 방식으로 접근하면 된다. (말은 쉽다..!) 현재 정점과 다음 방문할 정점과 비교했을 때,dp[다음정점]의 가중치가 dp[현재정점]의 가중치+다음 정점 가중치보다 크면 dp[다음정점]현재값으로 업데이트하고, 큐에 추가하는 것이 핵심이다. 다익스트라 문제를 풀때는 ..다익스트라 문제를 풀 때는 아래 내용을 고려하면서 풀면 된다. 1. dp 배열의 초기값을 Int.max로 두기2. 방향그래프인지 무방향 그래프인지 확인해서 딕셔너리 업데이트3. bfs 시작할 때 시작값의 dp는 0이나 특정 값으로 초기화4. 방문처리를 따로 안함5. 스위프트로 b..

https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 정리1. 문제 요구사항 정의특정 튜플을 표현하는 집합이 담긴 문자열 s가 주어질 때, s가 표현하는 튜플을 배열에 담아 반환문자열 s는 순서가 섞여있음=> 구할 것: s가 표현하는 튜플을 배열로 반환  2. 제약사항5 ≤ s의 길이 ≤ 1,000,0001 ≤ 튜플의 원소 값의 범위 ≤ 100,000  3. 메모리 및 시간복잡도 확인메모리 및 시간 제한 표기되어있지 않음  4. 풀이방법1) {,}..

https://school.programmers.co.kr/learn/courses/30/lessons/134240?language=swift 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 정리1. 문제 요구사항 정의2명의 선수들이 대회에서 책상 양쪽에서 가운데를 향해 음식을 먹는 대결을 함.승리 조건: 중앙에 있는 물을 먼저 먹는 선수환경: 두 선수가 먹는 음식의 종류와 양이 같아야 함.환경: 두 선수가 음식을 먹는 순서도 같아야 함.환경: 칼로리가 낮은 음식을 먼저 먹을 수 있게 배치.환경: 수웅이가 준비해온 음식 중 몇개는 대회에 사용하지 못함.=..

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는 max값..

처음에 생각했던 풀이 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 해당 문제를 풀면서 누적합을 처음 접했다. 문제를 보고 값을 계산해서 저장해서 꺼내서 사용하면 될 것 같다는 생각은 들었는데, 정확한 해결방법이 누접합!인지는 몰랐다..! 누적합에 대해 알아보자! 누적합 특정 구간의 합을 찾는데 유용한 알고리즘 누적합 알고리즘은 연속된 원소들의 합을 빠르게 계산하는 알고리즘입니다. 배열과 같은 시퀀스 데이터에서 일부 구간의 합을 찾는 데 사..