그냥 블로그

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net [문제 요약] 비용이 측정된 간선이 있고, 가장 작은 비용으로 갈 수 있는 값을 구해라. [아이디어 구현 과정] 사실, 플로이드 워샬을 오랜만에 풀어보고 싶어서 제목만 보고 선택하게 되었는데, 보다보니까 플로이드는 기억이 안나고 Dijkstra만 생각이 났다... 시간 복잡도를 계산 해보니 다익스트라를 사용한다고 시간 초과에 걸리지 않았고, 그냥 다익스트라를 사용하기로 했다 ㅎ 시간복잡도는 최대 100개 도시, 100,000개 버스 => 1. 한개의 도시에서 다른..

알고리즘을 풀 때 map을 많이 사용해 왔는데, 이걸 구현하는게 레드 블랙 트리라는 사실은 알고 있었다. 하지만, 색을 지정하고 균형 트리를 이룬다는 것 외에 정확한 개념을 모르고 있기도 했고, STL을 구현하면서 C++ 실력을 올리기 위해 map STL을 잡았는데, 레드 블랙 트리를 모르고 map 자료구조를 구현할 수 없기 때문에 한 번 알아보기로 했다. *약간의 써칭 + 위키피디아 레드 블랙 트리를 참고해서 정리, 구현한 글입니다. 오류나 질문은 환영입니다! 레드-블랙 트리 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배..

이진 탐색 트리란?이진탐색을 위한 이진트리.모든 노드의 Key는 유일하다. (중복 없음)왼쪽 자식은 나보다 작다오른쪽 자식은 나보다 크다 이진 탐색 트리의 장점 일반 이진 탐색은 중앙 요소를 알아야하기 때문에 "배열"에서만 사용 가능. 연결 리스트는 이진 탐색에 적합하지 않다. 배열의 크기가 변화면 안되는 정적 이진 탐색 트리 배열을 사용해 탐색할 때보다 시간 복잡도가 작다 O(logN) 동적으로 데이터 집합 크기가 바뀌고 순서가 바뀌어도 문제가 없다. 주의할 점트리 모양이 한쪽으로 치우치면 트리 탐색의 장점인 O(logN) 시간복잡도가 마치 배열을 순차 탐색하는 듯하는 O(N)에 가까워지게 된다. => 데이터를 추가/삭제 할 때 트리 모양을 균형있게 만드는 "레드 블랙 트리"가 있다. (C++ map ..

https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'www.acmicpc.net [문제 설명] 10*10 크기의 보드에 빨간 구슬, 파란 구슬, 통과할 구멍이 각각 1개씩 있다. 보드를 기울여서 구슬이 직선으로 움직이고 빨간 구슬이 10번 이내로 구멍을 통과하면 된다. 이때, 파란 구슬은 통과하면 안됨! [풀이 과정] 처음에 문제를 보고 완전 탐색, DFS를 떠올려서 그렇게 진행을 했다.... 근데 풀 수 없었음. 정확히 말하면, 처..

2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 백준 2357번 최솟값과 최대값 문제를 풀면서 세그먼트 트리에 대해 접하게 되었다. 처음에는 DP로 풀어보려고 끙끙대고 있다가 안되길래 분류표를 보니 세그먼트 트리라는 걸 알 수 있었다.. 새로운 자료구조를 한번 정리해보기로 했당... 세그먼트 트리 (인덱스 트리)? 주어진 데이터의 `구간 합`과 `데이터 업데이트`를 빠르게 수행하기 위해 고안해낸 자료구조 형태 *구간 합과 다른 점은 데이터 업데이트가 빈번하게 일어나도 속력..

https://www.acmicpc.net/problem/1796 1796번: 신기한 키보드동혁이의 키보드에는 버튼 세 개와 LCD창 한 개가 달려 있다. LCD창에는 문자열 S가 쓰여 있다. 그리고 커서는 문자열의 가장 왼쪽 글자에 위치해 있다. 버튼 세 개는 왼쪽, 오른쪽, 엔터키이다. 왼www.acmicpc.net [...] 일단, 처음에 문제를 보면서 "타자 입력" "엔터나 오른쪽 왼쪽"을 보고 stack, bfs를 떠올렸다. 혹시 DP? 하기도 했는데 아니겠지하고 넘어감 ㅎㅎ.. 그리고 문제를 풀면서 풀이 방법에 근접한 방법을 생각해 냈는데 난독 이슈로 이상한 방법으로 풀이를 하다가 집어 던졌다... stack + 오른쪽 왼쪽 막 구현 하고 그런 거엿음 ㅋㅋㅋ 나중에 분류 표랑,, 스터디원 분이..