Contents
-
[프로그래머스] 위장Data Structure & Algorithm 2021. 9. 10. 17:22
[문제] 코딩테스트 연습 - 위장 programmers.co.kr [풀이] -시행착오- 코테 때와는 다르게 어떤 타입의 문제인지 미리 알 수 있는 상태였고 hash 유형이니까 별생각 없이 주어진 clothes 리스트를 가공하여 {의상 종류: 의상 이름} 형태로 딕셔너리를 만들어 놓고 풀어가려고 시도했던 것이 화근이 되었다. 이렇게 생각없이 딕셔너리부터 만들어 놓은 뒤에 진행된 사고의 흐름은 다음과 같았다. 적어도 하나의 의상은 입어야 한다는 제한사항이 있네! 특정 의상 타입 가운데 하나의 의상을 선택해 시작 의상으로 설정하고 나머지 타입들에 해당하는 의상을 넣거나 넣지 않거나 해서 의상 요소들을 저장하면서 중복된 의상들의 경우는 제거하면 ([파랑 안경, 검정 티, 빨강바지]와 [검정 티, 빨강바지, 파랑..
-
슬라이딩 윈도우 (sliding window)Data Structure & Algorithm 2021. 9. 9. 16:45
[슬라이딩 윈도우란?] 슬라이딩 윈도우는 윈도우라고 부르는 일정 구간을 단방향으로 이동시켜 가면서 윈도우 안에 있는 데이터를 이용해 주어진 문제를 해결하는 알고리즘이다. 슬라이딩 윈도우는 데이터의 정렬여부와 관계없이 사용 가능하다. [예제1: 최대 슬라이딩 윈도우 - 구간 내 최댓값 구하기] 배열 nums = [3, 2, 4, -1, 2, -3, 5, -4, 6] 이고 구간(window)의 크기 k = 3이라고 하면 초기에 구간을 가장 왼쪽에 배치하고 이후 한칸씩 오른쪽으로 시프트 해가면서 구간 안에 최댓값을 구해본다. [3, 2, 4, -1, 2, -3, 5, -4, 6] --> 4 [3, 2, 4, -1, 2, -3, 5, -4, 6] --> 4 [3, 2, 4, -1, 2, -3, 5, -4, 6]..
-
빠른 구간 합 구하기(누적 합)Data Structure & Algorithm 2021. 9. 8. 15:07
[1차원 리스트의 누적합] N개의 정수를 원소로 갖는 배열이 주어졌을 때 모든 구간 합을 구하기 위해서는 2중 반복문을 실행하면서 선형탐색 결과를 더해가야 한다. 하지만 별도의 누적합계 테이블을 만들어 놓으면 연산을 많이 줄일 수 있다. import sys data = [-40, 20, -10, 10, -30, 10] table = [0] for d in data: table.append(table[-1] + d) max = -sys.maxsize s_idx = 0 e_idx = 0 for i in range(1, len(table)): for j in range(i): if max < table[i] - table[j - 1]: max = table[i] - table[j - 1] s_idx = j -..
-
트라이(TRIE)Data Structure & Algorithm 2021. 9. 7. 16:27
[Trie란] Trie(retrieval: 검색)는 검색 트리의 일종으로 일반적으로 문자열의 각 문자를 키로 하여 순차적으로 문자열의 구성 정보를 저장하는 데 사용한다. 주로 검색어 자동완성, 사전 찾기, 문자열 검사 등에 사용된다. [Trie의 시간복잡도] insert: 문자열 개수를 N라 하고 가장 긴 문자열의 길이를 L이라 할 때 Trie에 모든 데이터를 삽입하는 작업의 시간 복잡도는 O(N * L)이다. search: 찾고자 하는 문자열의 길이가 L이라고 할 때 해당 문자열의 유무를 확인하는 시간 복잡도는 O(L)이다. [Trie의 구현] from collections import defaultdict class TrieNode: def __init__(self): self.word = '' # ..
-
투 포인터(Two Pointers)Data Structure & Algorithm 2021. 9. 7. 09:42
[투 포인터] 투 포인터 알고리즘은 리스트의 데이터에 순차적으로 접근하기 위한 알고리즘이다. 그 이름에서 알 수 있듯이 순차적 접근에 필요한 인덱스 두 개가 필요한데, 두 인덱스를 담아둘 수 있는 각각의 변수를 두고 그 값을 변경해가며 리스트에 접근한다. [투 포인터를 활용한 예 - 특정 합의 연속된 부분 수열 개수 구하기] 만약 [3, 2, 1, 5, 4, 1, 2]와 같은 리스트가 있다고 할 때, [3, 2]나 [1, 5, 4]와 같이 원본 리스트의 원소 순서를 그대로 유지한 부분 리스트를 연속된 부분 리스트라고 한다. 이때 연속된 부분 리스트 원소의 총합이 5인 부분 리스트의 수를 구해보도록 하자. 투 포인터 left, right 모두 첫번째 인덱스를 가리키도록 초기화한다. left ~ right에..
-
파라메트릭 탐색(Parametric search)Data Structure & Algorithm 2021. 9. 6. 14:14
[파라메트릭 탐색이란] 파라메트릭 탐색은 최적의 해를 탐색하는 문제를 yes/no의 결정 문제들로 나눠서 해결하는 탐색 방법이다. 사고 싶은 물건이 있을 때 내가 가진 예산 내에서 살 수 있는 가장 비싼 제품을 고르는 것과 같은 문제가 파라메트릭 탐색을 적용하여 해결한 수 있는 문제이다. 단 파라메트릭 탐색을 위한 전제 조건은 데이터가 정렬되어 있어야 한다는 것이다. 내가 사고자 하는 제품 단가들이 다음과 같이 주어진다고 하자. goods_prices = [15, 17, 22, 26, 28, 30] 현재 예산은 27원이라 할 때 구매할 수 있는 가장 비싼 제품은 26원이다. 이 과정을 파라메트릭 탐색을 통해 진행해보자. 먼저 탐색 전에 양 끝의 인덱스를 left, right로 설정한다. 중앙 인덱스 mi..
-
[프로그래머스] 프린터Data Structure & Algorithm 2021. 9. 5. 16:38
[문제] 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr [풀이] 처음 문제를 접하고 우선순위라는 키워드 때문에 priority queue를 사용하는 문제일 것으로 생각했으나, 요구사항을 확인한 결과 항상 최선의 priority를 찾아 pop 하는 priority queue와는 다른 동작이 필요했다. 문제의 요구사항을 정리해보면 다음과 같다. while queue가 비어있지 않을 동안 if queue[0]가 가장 우선순위가 높은 출력물이면 then queue[0]를 popleft한다. 카운터를 1 증가 시킨다. ..
-
Circular Buffer with PythonData Structure & Algorithm 2021. 9. 4. 11:10
circular buffer의 데이터를 저장할 공간을 list를 사용하여 확보한다. 데이터의 시작점(front)와 끝점(rear)을 각각 0으로 설정한다. 데이터가 삽입될 때는 rear에 1을 더해주고 rear % 저장공간의_길이에 해당하는 인덱스에 저장한다. 데이터를 삭제할 때는 front에 1을 더해주고 front % 저장공간의_길이 에 해당하는 인덱스의 값을 되돌려준다. front == rear 이면 circular buffer가 비어있는 것이다. front == (rear + 1) % 저장공간의_길이 이면 circular buffer가 가득 찬 것이다. class CircularBuffer: def __init__(self, k: int): self.q_len = k + 1 self.front =..