그냥 블로그

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net[문제요약] 1~6까지 나열된 수열이 몇개 있다. ex) - 1 4 3 - 6 2 5 4 - 2 3 각 수열에 있는 숫자들의 순서는 지켜져야 한다. 하지만 중간에 다른 숫자가 들어와도 된다. 일렬로. [문제 풀이] 처음에 문제를 읽으면서 1) 완탐은 안됨 2) DFS? 3) Union-find? 이렇게 3가지를 생각했는데... 3번 Union-find는 순서를 정할 수 없기 떄문에..

알고리즘을 풀 때 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를 떠올려서 그렇게 진행을 했다.... 근데 풀 수 없었음. 정확히 말하면, 처..

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

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 1. sort 설명 2. 정답 코드 하지만 저는 bits/stdc++.h를 사용합니다 개편한~ 1. sort algorithm sort(start, end, compare)로 되어 있다. 이 때, start와 end에는 주소값이 와야 한다. compare를 넣지 않을 경우 오름차순 정렬이 되고, 내림 차순 정렬의 경우 compare 위치에 greater()을 넣어준다. sort는 qui..