문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 3085 사탕 게임 제출 언어: Swift 알고리즘 분류: 구현 브루스포스 알고리즘 풀이 브루스 포스 알고리즘 Brute(무식한) Force 알고리즘 : 모든 가능한 경우의 수를 모두 탐색하며 요구 조건에 충족하는 결과만을 가져옴 완전 탐색 알고리즘 주어진 문제를 선형 구조로 구조화 한 후 반복문으로 원하고자 하는 해를 구할 때까지 탐색 BFS(너비 우선 탐색)도 브루스 포스 방식의 완전 탐색 알고리즘이다 알고리즘 설계 입력받은 NxN크기의 사탕들을 (N+1)*(N+1)크기의 배열에 넣어준다 -> 배열의 인덱스 문제를 최소화하기 위해서 사탕 게임을 진행하기 전의 상태가 연속한 사탕 부분의 최대값일 수 있으므로 현재 상태에서의 연속된 사탕의 최대 개수를..
자연어 처리 (NLP) 기술을 접목한 iOS앱 개인 프로젝트를 구상하는 도중 요즘 핫한 chatGPT가 떠올랐다! chatGPT를 이용한 서비스를 구현하기 위해 chatGPT API를 사용해보려고 한다. chatGPT에게 질문을 던지고 대답을 받는 작업을 해보자 1. OpenAI API key 발급받기 아래 링크 의 우측 상단의 View API keys 메뉴로 들어가API key를 발급받는다. OpenAI API An API for accessing new AI models developed by OpenAI platform.openai.com OpenAI API key는 다시 볼 수 없으므로 잘 백업 해놓자! 2. Swift Package 추가 이제 Swift로 ChatGPT를 사용하기 위해 Packa..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1789 수들의 합 제출 언어: Swift 알고리즘 분류: 수학 그리디 이론 풀이 그리디 이론 그리디 이론에 대한 설명은 그리디 알고리즘에 정리해놨으므로 생략하겠다 복잡하게 생각하지 않고 단순하게 while문을 사용하여 구현하니 쉽게 해결이 되었다 알고리즘 설계 해 선택 : N이 최대가 되려면 그 서로 다른 자연수들의 값이 최소가 되어야 하므로 1부터 커지는 방향으로 해 집합에 추가한다 실행 가능성 검사 : 해 집합에 있는 해들의 합이 S를 넘는지 확인한다 해 검사 : 해 집합에 하나의 해를 추가했을 때 S를 넘을 경우, 알고리즘을 종료하고 해의 개수를 count한다 이러한 알고리즘을 바탕으로 다음과 같은 코드를 짰다 합이 S가 되는 서로 다른 자연수..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 2252 줄 세우기 제출 언어: Swift 알고리즘 분류: 그래프 이론 위상 정렬 풀이 위상 정렬 그래프 내의 모든 정점(node)를 선형으로 정렬할 때 사용한다 cycle이 없는 조건일 경우 사용한다 모든 간선(u,v)의 node u가 node v보다 먼저 오도록 정렬하는 알고리즘이다 알고리즘 적용 indegree 배열에 모든 node들로 들어오는 간선의 개수를 저장한다 indegree가 0인 node를 시작 node로 지정하고 queue에 넣어준다 queue가 비어있을 때까지 하나씩 꺼내서 그 node가 들어가는 간선의 도착 node의 indegree를 1씩 빼준다 이 후 indegree가 0이 된 node가 있다면 다시 queue에 넣어준다 이러..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1197 최소 스패닝 트리 제출 언어: Swift 알고리즘 분류: 그래프 이론 최소 스패닝 트리 풀이 최소 스패닝 트리 그래프 내의 모든 node들을 최소의 간선 비용으로 연결하는 트리이다 cycle이 없는 조건일 경우 사용한다 Greedy를 이용한 그래프 탐색 알고리즘이다 Kruskal알고리즘과 Prim알고리즘 이 두 알고리즘으로 해결할 수 있다 Kruskal's Alg 1) 그래프 내의 모든 edge(간선)들을 비용에 따라 오름차순으로 정렬한다 2) 1)에서의 edge들을 최소 스패닝 트리에 추가한다 3) cycle을 형성하는 edge는 건너뛴다 Prim's Alg 1) 임의의 node를 시작 node로 설정 2) 각 node마다 최소 스패닝 트리..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1916 최소비용 구하기 제출 언어: Swift 알고리즘 분류: 그래프 이론 데이크스트라 풀이 DIJKSTRA Negative Cycle이 없는 directed graph에서만 사용 가능하다 시작 node에서 다른 node로 가는 가장 짧은 경로를 구하여 최종적으로 시작 node에서 끝 node까지의 최종 최단경로를 구한다 이 문제에서는 다양한 버스 노선 중 주어진 도시 1에서 5로 가능 최단 경로를 찾는 알고리즘을 작성해야한다 다익스트라 알고리즘 작동 원리는 다음과 같다 각 node까지의 경로 길이를 무한대로 초기화 시작 node의 경로 길이를 0으로 초기화 아직 포함되지 않은 node 중 최소인 것 선택하여 최단경로에 추가 최단경로에 새로 추가된 ..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1806 부분합 제출 언어: Swift 알고리즘 분류: 누적 합 두 포인터 풀이 투포인터 알고리즘 1차원 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다 정렬되어 있는 두 list의 합집합에서 사용 (merge sort의 기초) 포인터는 2개로, start-end로 설정하며 초기에는 stard=end=0 이고 항상 start 현재 result값과 end - start(현재 원소의 최소 길이)중 작은 값으로 초기화 temp값(현재 원소의 부분 합)에서 현재 원소 값을 빼준다 start += 1을 해준다 (앞 포인터를 오른쪽으로 한 칸 이동시킨다) case2. 끝 포인터가 배열의 끝에 도달할 경우 while문을 끝..
이전 값 타입과 참조 타입 글에서 struct보다는 class를 사용하라는 말을 했지만, 특정 프로토콜을 채택해야 하는 상황 등 분명히 class를 사용해야만 하는 경우가 발생한다 앱을 모델링할 경우에 이러한 class 성능을 향상시키기 위한 노력이 반드시 필요하다 지금부터 class의 성능을 향상시키는 방법을 알아보자~ 😎 Static Dispatch vs Dynamic Dispatch 함수를 호출하는 방식인 Static Dispatch와 Dynamic Dispatch을 이용하여 class의 성능을 향상시킬 수 있다. 이러한 함수 호출 방식들에 대해 살펴보자 Dynamic Dispatch Swift에서 class는 상속 기능을 지원하고, 상속한 하위 클래스에서 상위 클래스의 메서드를 오버라이딩해서 사..
