분류 전체보기

[programmers] 프로그래머스 호텔 방 배정(Python)

[programmers] 프로그래머스 호텔 방 배정 (Python) (글쓴날 : 2020.05.18) * programmers, 프로그래머스 문제 Python 언어 풀이입니다. * 소스 코드의 저작권은 글쓴이에게 있습니다. 프로그래머스 호텔 방 배정 1) 문제 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 2) 풀이 과정 * 시간 복잡도 : O(α(n), α : 아커만 함수) 방이 총 k개인 호텔에 고객들을 배정할 때, 만약 고객이 원하는 방이 비어있을 시 그 방을 배정하고, 비어있지 않다면 고객이 원하는 방보다 번호가 크면서 가장 작은 번호의 남은 방을 배정하여, 각 ..

[Baekjoon Online Judge] 백준 2170번 선 긋기(Python)

[Baekjoon Online Judge] 백준 2170번 선 긋기 (Python) (글쓴날 : 2020.05.17) * Baekjoon Online Judge, 백준 2170번 문제 Python 언어 풀이입니다. * 소스 코드의 저작권은 글쓴이에게 있습니다. 백준 2170번 선 긋기 1) 문제 문제 링크 : https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택한 지점은 -1,000,000,000 이상 1,000,000,000 이하의 정수이다. www.acmicpc.net 2) 풀이 과정 * 시간 복잡도 : O(n log n) 도화지에 ..

[Algorithm] 유니온 파인드

[Algorithm] 유니온 파인드 (글쓴날 : 2020.05.16) * 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다. 유니온 파인드 1) 유니온 파인드란? 유니온 파인드란 집합을 관리하는 트리 형태의 자료구조로 Disjoint-set(서로소 집합, 분리 집합)이라고도 하며, 보통 배열에서 인덱스를 노드로 나타내어 각 인덱스의 값에 해당 인덱스의 부모 노드를 저장합니다. 유니온 파인드는 주로 그래프 문제에 적용할 수 있으며, 다른 그래프 알고리즘인 Dijkstra algorithm, Bellman-Ford algorithm 등과 달리, 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용됩니다. 핵심 연산으로는 2가지가 있으며, 유니온 파인드라는 이름과 걸맞게 다음과 같습니다. 1) uni..

[Baekjoon Online Judge] 백준 1976번 여행 가자(Python)

[Baekjoon Online Judge] 백준 1976번 여행 가자 (Python) (글쓴날 : 2020.05.16) * Baekjoon Online Judge, 백준 1976번 문제 Python 언어 풀이입니다. * 소스 코드의 저작권은 글쓴이에게 있습니다. 백준 1976번 여행 가자 1) 문제 문제 링크 : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 2) 풀이 과정 * 시간 복잡도 : O(α(m), α : 아커만 함수) N개의 도시와..

[Baekjoon Online Judge] 백준 1717번 집합의 표현(Python)

[Baekjoon Online Judge] 백준 1717번 집합의 표현 (Python) (글쓴날 : 2020.05.16) * Baekjoon Online Judge, 백준 1717번 문제 Python 언어 풀이입니다. * 소스 코드의 저작권은 글쓴이에게 있습니다. 백준 1717번 집합의 표현 1) 문제 문제 링크 : https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net 2) 풀이 과정 * 시간 복잡도 : O(α(..

[Algorithm] 슬라이딩 윈도우

[Algorithm] 슬라이딩 윈도우 (글쓴날 : 2020.05.15) * 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다. 슬라이딩 윈도우 1) 슬라이딩 윈도우란? 슬라이딩 윈도우 알고리즘은 사실 따로 다룰 필요가 없을 정도로 투 포인터 알고리즘과 비슷합니다. 딱 한 가지 다른 점은 바로 범위의 제한인데, 투 포인터의 경우 연산을 위하여 포인터를 이동시키는 범위에 대한 제한이 전혀 없지만, 슬라이딩 윈도우의 경우 특정 범위를 제한하여 이동하는 특징이 있습니다. 이에 따라 크기가 고정적인 창문(특정 범위)을 옆으로 미는 것(이동)을 묘사하여 슬라이딩 윈도우라는 이름이 붙은 것 같습니다. 이런 슬라이딩 윈도우는 주로, 자료구조 Deque를 사용하여 구현합니다. 예를 들어, N개의 숫자가 들어있는 ..