PS

[알고리즘 - Swift] 순열과 조합 구현하기

순열과 조합 코테 문제를 풀다보면 순열과 조합이 필요한 경우가 있다. Swift에서는 순열과 조합을 직접 구현해야 한다. 순열과 조합은 각각 Stack, 재귀를 통해 구현할 수 있다. 어떻게 구현하는지 순열부터 알아보자. 순열 순열은 서로 다른 m개에서 n개를 골라 줄세우는 것이다. (mPn) 줄을 세우기 때문에 요소들의 순서 또한 경우의 수에 영향을 준다. Stack func permutation(_ array: [T], _ num: Int) -> [[T]] { var result = [[T]]() /// 주어진 원소 개수보다 많은 가짓수를 뽑을 수 없음 guard num 0 { let current = stack.removeLast() let elements = current.0 var visited..

[프로그래머스 - Swift] 가장 먼 노드

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 각 depth에 존재하는 노드의 개수를 묻는 문제였다. 그중 가장 멀리 있는 노드의 개수를 묻는 것이었고, BFS의 기본적인 유형 중 하나인 것 같았다. 큰 응용은 없었던 것 같고, 쉽게 BFS를 떠올릴 수 있었다. queue를 활용하여 BFS로 풀었다. 코드에 대한 설명은 코드에 주석으로 달았다! 코드 import Foundation func solution(_ n:Int, _ edg..

[프로그래머스 - Swift] 네트워크

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 DFS by 재귀 맨 처음엔 간선만 신경을 썼으나, 문제에서 요구하는 '네트워크의 수'는 간선과 아무것도 연결되어있지 않는 노드도 신경을 써서 도출해야 했다. dfs로 재귀를 통해 연결되어있는 노드를 탐색하면, 연결되어 있는 노드를 끝까지 탐색하도록 했다. 이때 탐색했다는 표시도 동시에 해서 최종적으로 탐색되지 않은 (아무것도 연결되어있지 않은) 노드의 개수를 구할 수 있도록 했다. 간..

[Leetcode - Swift] 841. Keys and Rooms

문제 https://leetcode.com/problems/keys-and-rooms/description/ Keys and Rooms - LeetCode Keys and Rooms - There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key. When you visit a room, you may find a set of di leetcode.com 풀이 그래프를 순회하는 문제. DFS와 BFS 둘 다 가능하다. DFS의 런..

[PS] 간단한 Graph 개념과 BFS, DFS 템플릿

Graph 그래프는 정점(vertex)과 간선(edge)의 집합이다. G(V,E)로 표현할 수 있다. 그래프의 종류에는 방향 그래프와 무향 그래프(PS에서 가장 많이 등장), 다중 그래프와 단순 그래프, 가중치 그래프(다익스트라) 등이 있다. 그래프는 현실의 문제를 해결하기 위한 도구로 많이 쓰이기 때문에 문제로 많이 출제된다. 그래프의 예로, 도시들을 연결하는 도로망 (정점 - 도시, 간선 - 도로), 지하철 노선도 (정점 - 정거장, 간선 - 노선), 컴퓨터 네트워크 (정점 - 컴퓨터와 라우터, 간선 - 연결 관계) 등이 있다. 그래프의 표현 방법으로 인접 행렬, 인접 리스트, 암시적 그래프가 있다. 인접 행렬은 모든 연결 관계를 나타낸 것이다. 메모리가 많이 들어 비효율적이다. 인접 리스트는 연결된..

[Leetcode - Swift] 1091 Shortest Path in Binary Matrix

문제 https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ Shortest Path in Binary Matrix - LeetCode Can you solve this real interview question? Shortest Path in Binary Matrix - Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1. A clear path in a binary matrix is a path from leetcode.com 풀이 이 문제는 ..

[프로그래머스 - Swift] 오픈 채팅방 (2019 KAKAO BLIND RECRUITMENT)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42888 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 우선 [유저id : 닉네임] 딕셔너리를 만들었다. record에서 Change가 나오면 result의 닉네임을 다시 바꿔줘야 하므로, 처음부터 변경된 닉네임으로 result를 만드는 게 효율적이기 때문이다. 그래서 최종본(?) 닉네임을 얻기 위해 딕셔너리를 구했다. record에서 Enter, Change가 나오면 유저 id의 닉네임을 할당하는 방식으로 진행했다. 그후 record에서 ..

[Leetcode - Swift] 111. Minimum Depth of Binary Tree

문제 https://leetcode.com/problems/minimum-depth-of-binary-tree/description/ Minimum Depth of Binary Tree - LeetCode Minimum Depth of Binary Tree - Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Example 1: [https:// leetcode.com 풀이 1. 재귀 2 .BFS 최..