Swift를 이용한 알고리즘 공부

알고리즘 세팅

자료구조

Round	Name	Swift
0	Stack	Link
1	Queue	Link
2	Heap	Link
3	Dictionary	Link

개념

Round	Title	Keyword
0	인접행렬	adjacency matrix
1	인접리스트	adjacency list
2	깊이 우선 탐색	Depth First Search
3	너비 우선 탐색	Breadth First Search
4	DFS BFS 비교	비교
5	트리 순회	Tree

백준

Round	Title	C++	Swift
탐색 알고리즘
1012	유기농 배추	Link	Link	Connected Component 개수 구하기 → BFS 또는 DFS 모두 가능. 인접한 배추 묶음을 하나의 영역으로 간주.
2178	미로탐색	Link	Link	최단 거리 구하기 (BFS) → (0,0)부터 (N-1,M-1)까지 최소 이동 칸 수를 구함.
2468	안전영역		Link	Connected Component 개수 구하기 → 모든 높이에 대해 안전 영역의 개수를 구함. BFS/DFS 모두 가능.
2583	영역 구하기		Link	넓이 구하기 + Connected Component → 직사각형이 그려진 도화지에서 남은 영역의 개수와 넓이를 구함.
1992	쿼드트리		Link	분할정복 (재귀, 큰 문제를 하위 문제로 쪼개어 상위 문제를 해결) → 2차원 배열을 같은 숫자로 구성된 4등분 단위로 압축. 재귀적으로 처리하며 필요 시 괄호로 묶음. Stack으로도 구현 가능.

프로그래머스

Round	Title	C++	Swift
워밍업
1	배열 정렬하기	Link	Link	sort(by:), sorted(by:)를 이용해 배열을 정렬할 수 있다.
2	배열 제어하기	Link	Link	sorted(by:)는 비교 함수를 인자로 받아 정렬 기준을 지정할 수 있다.
3	두 수를 뽑아서 더하기	Link	Link	var set = Set()로 정의하고, Set은 중복 제거에 유용하며 insert, remove로 관리할 수 있다.
4	모의고사	Link	Link	return point .sorted { $0.key < $1.key } // 1. key 기준 오름차순 정렬 .filter { $0.value == point.values.max() } // 2. 가장 큰 value를 가진 항목만 필터링 .map { $0.key } // 3. 해당 key들만 추출하여 반환
5	행렬의 곱셈	Link	Link
6	실패율		Link	sorted(by:)는 두 요소를 비교하는 함수를 인자로 받아 정렬 기준을 직접 지정할 수 있다.
7	방문 길이		Link	좌표 이동 시 중복된 길을 Set으로 처리하는 시뮬레이션 문제다.
[Stack]
8	올바른 괄호		Link	스택과 카운팅 방식 모두 괄호 짝 검증에 사용될 수 있다.
9	10진수를 2진수로 표현하기		Link	map: 배열 요소에 연산을 적용해 새 배열을 만든다. joined: 문자열 배열의 요소들을 하나의 문자열로 이어 붙이는 함수다.
10	괄호 회전하기		Link	문자열 슬라이싱과 인덱스 offset을 이용한 회전 구현이 가능하다. .s.index(s.startIndex, offsetBy: i)
11	짝지어 제거하기		Link	스택과 단락평가로 조건 검사를 간결하게 할 수 있다.
12	주식가격		Link	알고리즘이 떠오르지 않으면 O(n^2)으로 정확성 테스트 정보 확보하자.
13	크레인 인형뽑기 게임		Link	board열을column)별로 스택 형태로 변환하여 인형 뽑기 연산을 효율적으로 수행할 수 있다.
14	표편집		Link	up, down 배열을 이용해 연결 리스트 동작을 시뮬레이션하고, 삭제 행은 스택에 저장해 O(1)로 복구하고, U/D 이동은 연결을 따라 처리한다.
[Queue]
15	요세푸스 문제		Link	큐를 사용해 k-1번 회전 후 k번째 원소를 제거하는 과정을 반복하여 제거 순서를 구할 수 있다.
16	기능개발		Link	각 작업의 배포일까지 필요한 날짜를 계산하고, 앞선 작업보다 늦게 끝나는 경우 해당 날짜로 갱신해 같은 날 배포될 기능 개수를 구한다.