전체 글
-
[자료구조] collections module - dequeLanguage Study/Python 2021. 3. 31. 16:39
1. deque 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다. 파이썬에서는 collections 모듈을 이용하여 deque를 사용할 수 있다. import collections dq = collections.deque() 로 생성 from collections import deque dq = deque() 로 생성 list와 동일하게 append(), pop()을 사용할 수 있으며 추가적으로 appendleft(), popleft()도 사용할 수 있다. list.pop(0)이나 list.insert(0, number) 을 이용하면 기본 기능을 이용해서도 구현할 수 ..
-
[프로그래머스] 동적계획법(DP) 01. N으로 표현Algorithm Study/Python 2021. 3. 31. 15:06
programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사..
-
[프로그래머스] 탐욕법(Greedy) 06. 단속카메라Algorithm Study/Python 2021. 3. 17. 18:36
programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 문제설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 ..
-
[프로그래머스] 탐욕법(Greedy) 05. 섬 연결하기Algorithm Study/Python 2021. 3. 17. 16:30
programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 (..
-
[알고리즘] union find (disjoint-set)Algorithm Study/Python 2021. 3. 17. 14:55
Union find는 서로 중복되지 않는 부분 집합으로 나누어진 원소에 대하여 연결되어 있는 다른 원소를 찾거나 분리된 set을 합칠때 사용되는 알고리즘이다. 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1번 항목은 해당 원소의 번호 2번 항목은 원소의 root의 번호를 나타내는 표가 있다. 위 그림처럼 나누어진 집합의 모음이 있다고 가정하자 그렇다면 위의 표는 1 2 3 4 5 6 7 8 9 10 1 1 1 2 2 6 6 6 9 9 이렇게 나타낼 수 있을 것이다. 이 표는 내 parent node의 원소를 나타내고 있지만 이 표만 봐서는 4 , 5와 같은 항목은 1과 연결되어 있는지 직관적으로 알기 힘들다. 그래서 모든 항목들을 해당하는 집합의 root 원소로 표현하는 것..
-
[프로그래머스] 탐욕법(Greedy) 04. 구명보트Algorithm Study/Python 2021. 3. 16. 18:07
programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제설명 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무..
-
[프로그래머스] 탐욕법(Greedy) 03. 큰 수 만들기카테고리 없음 2021. 3. 16. 17:44
programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 문제설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한사항 number는 1자리 이상, 1,000,0..
-
[프로그래머스] 탐욕법(Greedy) 02. 조이스틱카테고리 없음 2021. 3. 16. 17:01
programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 문제설명 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. 예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다. 만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을..