본문 바로가기

분류 전체보기351

[leetcode 56] Merge Intervals Given a collection of intervals, merge all overlapping intervals. Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping. NOTE: input types have been changed o.. 2020. 10. 30.
[알고리즘] 0-1 BFS edge가 0 혹은 1의 가중치를 가질 때 사용하는 bfs이다. 사용하는 자료 구조 - 덱 접근 - 다익스트라 알고리즘을 최적화시킨 것이다. 사실 다익스트라 써도 상관없다. 다익스트라도 가중치 있는 노드에서 최단 거리 찾는 알고리즘이기 때문. - 가중치가 0이라는 것은 이전 노드와 동일 레벨이 존재한다는 것이다. 가중치가 1이면 이전노드에 비해 한 레벨 아래에 존재한다는 의미. - 가중치가 0인 것을 우선으로 팝하기 위해 가중치가 0인 경우 큐 앞쪽에, 가중치가 1인 경우 큐 뒤쪽에 푸쉬한다. 하지만 일반적인 큐는 앞에 푸쉬하는 것이 불가능하기 때문에 덱을 사용해서 앞쪽에 푸쉬한다. #include int main(void){ deque dq; dq.push_front(시작노드); while(!dq.em.. 2020. 10. 29.
[백준 13549] 숨바꼭질3 www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 단순 bfs로 접근했다가 틀렸다. 단순 bfs로 접근하면 안되는 이유는 순간이동시에 2*x를 이동하지만 0초가 걸리기 때문이다. 현재 노드에서 아래 레벨로 접근하는게 아니라 같은 레벨 상에 노드가 하나 더 생기는 셈이다. 사용하는 알고리즘 0-1 bfs 0-1 bfs란 그래프에 가중치가 0과 1로 구성된 경우 사용하는 bfs이다. 여기서 가중치란 노드의 레벨로 보면 될 것 같다.. 2020. 10. 29.
[백준 1600] 말이 되고픈 원숭이 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net - 3차원 배열 bfs문제였다. - 처음엔 2차원 배열로 했다가 틀렸다. 3차원으로 해야 하는 이유는 말을 통해서 가는 거리와 원숭이가 가는 거리를 분리해줘야 하기 때문이다. 말을 이용해서는 목적지까지 도착을 못한다고 가정해보자. (원숭이만을 이용해서 갈 수 있다고 가정) 2차원 배열에 path를 등록하여 이미 지나간 거리를 지나가지 않는다면 도착지까지 도달하지 못할 것이다. 그래서 말을 사용했.. 2020. 10. 29.

티스토리툴바