algorithm

[Algorithm] Permutation & Combination(순열과 조합)

순열과 조합 코드를 작성해보자.Python에서 직접 코드를 작성할 필요가 없다.from itertools import permutationsfrom itertools import combinationsdata = [1, 2, 3]list(permutations(data, 2)) # (1, 2), (1, 3), (2, 1), ...list(combinations(data, 2)) # (1, 2), (1, 3), (2, 3)이렇게 제공되는 함수가 있기 때문에 원하는 개수에 맞는 순열, 조합 요소를 뽑아준다. 하지만 Swift에서는 직접 구현해야하니...한번 작성해보자.순열원하는 함수 형태는 다음과 같다.func permutations(data: [T], count: Int) -> [[T]]?제네릭을 사용..

[Algotithm] Sliding Window

오늘은 Sliding Window 에 대해 알아보도록 하겠습니다.배열이나 문자열 같은 선형 데이터 구조에서 고정되거나 변화하는 크기의 윈도우를 이동시키며 데이터를 처리하는 기법입니다.여기서 윈도우란 연속된 요소의 SubArray라고 할 수 있습니다.해결해야 하는 문제에 따라 고정 슬라이딩 윈도우, 가변 슬라이딩 윈도우로 나뉠 수 있습니다.고정 슬라이딩 윈도우문제예시https://www.acmicpc.net/problem/12891평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비..

[99클럽 코테 스터디 7일차 TIL] 모음사전 - 프로그래머스

7일차 문제는 완전탐색 문제이다.거의 백준과 프로그래머스에서 문제를 가져오는거 같다. https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는,길이 5 이하의 모든 단어가 수록되어 있습니다.사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.단어 하나 word가 매개변수로 주어질 때,이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세..

[99클럽 코테 스터디 6일차 TIL] 나무 자르기 - 백준 2805

4~5일차에 DFS/BFS 문제가 나와서 주제가 바뀌는 줄 알았지만 다시 나와버린 이분탐색 https://www.acmicpc.net/problem/2805상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어..

[99클럽 코테 스터디 5일차 TIL] 알고리즘 수업 - 너비 우선 탐색 1 - 백준 24444

어제는 DFS라서 혹시나 했더니 역시나 오늘은 BFS다. https://www.acmicpc.net/problem/24444오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다.아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다.정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다.정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 for each v ∈ V - {R} ..