Data Structure & Algorithm
-
[BOJ] 치킨배달 (15686)Data Structure & Algorithm 2021. 10. 7. 09:56
[문제] https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net [풀이] 문제를 처음 읽었을 때 BFS를 통해 풀어야겠다고 생각했는데 그이유는 다음 두 가지다. 집과 치킨집 사이의 최단거리라는 워딩이 주어짐 주어지는 지도 정보가 2차원 배열 형태 BFS로 풀기로 정하고 세운 계획은 다음과 같다. 지도 정보를 2차원 리스트에 저장한다. 모든 치킨집 좌표 중 M개만 선택하는 조합을 생성한다. 지도 정보를 복사한다. 조합을 사용하여 복..
-
[프로그래머스] 디스크 컨트롤러Data Structure & Algorithm 2021. 9. 28. 09:30
[문제] 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr [풀이] 문제 해결을 위해 가장 짧은 실행 시간을 얻어내도록 job 실행 순서를 스케쥴링 해야한다. 스케쥴링에는 다음 두 가지를 고려한다. 요구사항 가운데 먼저 요청된 job이 먼저 실행된다가 있으므로 job 수행 순서를 결정하는 첫 번째 기준은 "요청시각"이다. 두 번째 기준은 실행시간인데, 이 "실행시간"이 heap을 통해 스케쥴링할 대상이다. 실행시간을 기준으로 스케쥴링을 하는 이유는 하나의 job도 실행되고 있지 않는 상태에서는 가장 빨리 ..
-
[프로그래머스] 위장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..