Hello Ocean! 🌼

문제 https://www.acmicpc.net/problem/14906 14906번: 스러피 첫 번째 줄에는 입력될 문자열의 개수를 나타내는 정수 N이 1~10의 범위로 우선 입력된다. 다음 줄부터 N개의 문자열이 입력된다. 문자열은 1~60개의 알파벳 문자로 구성된다. www.acmicpc.net 풀이 스러피 = 스림프 + 스럼프 [스림프] AH AB(스림프)C A(스럼프)C [스럼프] DFG or EFG DF(스럼프) or EF(스럼프) 재귀를 이용했다. isSlimp함수는 input에서 스림프의 시작idx를 return한다. 올바른 스림프를 찾을 수 없을 때에는 -1을 return한다. ex) isSlimp(AH~~~) : 2 isSlimp(ABAHC~~~) : 5 isSlump함수는 input이..

문제 https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 문제가 굉장히 길고 복잡하다.. 꼼꼼히 읽어보면서 이해하는 시간이 필요하다. 요약하자면, 결과적으로 입력받은 문자열이 (100+1+|01)+ 패턴에 해당하는지 아닌지를 판단하면 되는 문제이다. 풀이 (100+1+|01)+를 쪼개서 보자. 100+1+ = A, 01 = B라고 하면, (A|B)+ 이므로, A나 B가 계속 반복적으로 나타나면 된다. B는 01 자체이고, A 는 100+..

문제 https://www.acmicpc.net/problem/7579 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다. 하지만 스마트폰의 메모리는 제한적이기 때문에 한번이라도 실행했던 모든 앱을 활성화된 채로 메인 메모리에 남겨두다 보면 메모리 부족 상태가 오기 쉽다. 새로운 ..

문제 https://www.acmicpc.net/problem/20040 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다. C에 속한 임의의 선분의 한 끝점에서 ..

요약삽입정렬이 미리 정렬되어있는 자료구조에서 가장 빠른 성능을 가진다. 왜?버블정렬은 시간복잡도가 O(N^2)이고,퀵, 머지소트는 분할-정복 과정을 거치기 때문에 느리다.쉘 정렬은 간격이 k라고 했을 때, k가 1이될 때 까지 줄이면서 반복해야 하므로 이미 정렬된 자료구조에서는 삽입정렬보다 빠르지 않다. ** 이진 삽입 정렬이 일반적인 삽입정렬보다 더 빠르다고 말할 수 있다.list내에서 어떤 원소의 위치를 찾을 때, 삽입정렬은 1~n번째 원소를 모두 돌아가면서 보지만,이진 삽입정렬은 이 과정을 이진탐색으로 진행해서 O(logN)의 복잡도를 가지기 때문이다. ** 언어별 기본 제공 sorting 알고리즘Java : Tim Sort, dual pivot quicksortPython : Tim SortC++..

Binary Search Tree(이진 탐색 트리)란? 이진 탐색 + 연결 리스트를 결합한 자료구조의 일종 이진 탐색의 효율적인 탐색 능력 + 빈번한 삽입/삭제 가능하도록 고안 이진 탐색 복잡도 : O(logN) 연결리스트의 삽입/삭제 복잡도 : O(1) 속성 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 가진 노드들로, 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값의 노드들로 구성되어 있습니다. 중복되는 노드는 없어야 하며, 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리입니다. 순회시에는 중위순회 방식을 사용하면, 이진탐색트리 내의 모든 값들을 정렬된 순으로 읽을 수 있습니다. 중위 순회 : 왼쪽 하위 트리 -> root -> 오른쪽 하위트리 연산 검색 / 삽입 / 삭제 생성..