문제 1561 - 놀이 공원 접근 이분 탐색 문제이다. 시간을 변수로 해서 이분탐색을 진행하면된다. 최소는 1이고, 최대는 가장 시간이 긴 놀이기구에 n명이 모두 탔을 때다. 이분 탐색을 진행하며 해당 시간이 지났을 때 탑승한 인원이 n보다 크다면 정답 후보가 된다. 정답 후보들 중 최소값이 n명을 모두 탑승시킬 수 있는 최소 시간이 된...

문제 1275 - 커피숍2 접근 세그먼트 트리는 구간 합을 구할 때 사용하기 좋은 알고리즘이다. 단순히 풀게 되면 N개의 원소를 가진 배열에서 특정 구간 (x, y)의 합을 구하는데 O(N)의 시간이 걸린다. 그리고 이러한 구간합을 M번 구해야한다면 O(NM)의 시간이 걸릴 것이다. N과 M이 충분히 커진다면, 이러한 방식은 오랜 시간이...

문제 2110 - 공유기 설치 접근 문제 접근은 n의 개수와 좌표의 범위를 봤을 때 이분탐색을 사용해야 한다. 그렇다면 어떤 것으로 이분탐색을 해야할까? 얼핏 봤을땐 공유기를 어떤 집에 배치해야 하는지가 중요해보여서 집을 이용해서 이분탐색을 생각할 수도 있다. 하지만 문제의 핵심은 공유기 사이의 최대 거리를 구하는 문제이다. 공유기...

문제 [3차] 자동완성 접근 Trie 알고리즘을 사용했다. Trie 알고리즘은 문자열 검색에 사용되는 알고리즘이다. 문자열을 트리형식으로 저장하여 빠르게 검색할 수 있다. 각 문자열을 단어 단위로 트리 형식으로 연결한다. 트리의 깊이가 단어의 길이가 되는 형식이다. 트리 노드의 기본 구조는 다음과 같다. 해당 노드의 key, 즉 알파벳...

Contents 옵저버 패턴(Observer Pattern) 서로 상호작용을 하는 객체 사이에서는 가능하면 느슨하게 결합하는 디자인을 사용하자. 옵저버 패턴(Observer Pattern) 옵저버 패턴은 어떤 사건이 발생 했을 때 객체들에게 사건을 알려줄 수 있는 패턴이다. 옵저버 패턴은 크게 주...

Contents 모델 평가 코사인 거리의 응용 A/B 테스트 모델 평가 방법 홀드아웃(Holdout) 교차 검증 부트스트래핑(bootstrapping) 모델 평가 코사인 거리의 응용...

문제 18258 - 큐 2 접근 큐를 사용하는 문제이다. 파이썬에서 split(‘ ‘) 와 split()의 차이를 명확히 깨닳은 문제이다. 예를 들어, ‘ a b ‘ 가 있을 때 split(‘ ‘)를 해주면 [’’, ‘a’, ‘b’, ‘’] 이렇게 나온다. ’ ‘ 공백을 기준으로 나누다 보니, a 앞과 b 뒤에 공백도 분리의 기준으...

문제 1764 - 듣보잡 접근 교집합을 구하는 문제이다. 코드 파이썬 코드 import sys input = sys.stdin.readline n, m = map(int, input().split(' ')) arr1 = set(input().strip() for _ in range(n)) arr2 = set(input...

문제 1717 - 집합의 표현 접근 유니온-파인드의 아마 가장 기본 연습 문제가 아닐까 생각된다. 이미 이전에 한번 풀었기 때문에 크게 문제는 없었다. 풀이 자체가 이전 문제와 비슷하기 때문에 사이클 게임을 참고. 코드 파이썬 코드 import sys input = sys.stdin.readline n, m = ma...

문제 11003 - 최솟값 찾기 접근 슬라이딩 윈도우를 하며 탐색해야 한다. 처음에는 힙(우선순위큐)을 이용하여 문제를 풀었다. 힙에 배열의 값과 인덱스를 저장하고, 배열의 값을 이용해서 힙을 구성한다. 원소를 순서대로 보면서 힙에 넣고, 힙에 최소값이 슬라이딩 구간을 벗어나면 힙에서 제거하는 식으로 풀었다. 힙에서 원소를 추가하거...