본문 바로가기

전체 글232

문자열중 특정문자로 시작해 특정문자로 끝나는지 찾아용 문자열을 입력받아 문자열 내에 아래 중 하나가 존재하는지 여부를 리턴해야 합니다. 'a'로 시작해서 'b'로 끝나는 길이 5의 문자열 'b'로 시작해서 'a'로 끝나는 길이 5의 문자열 // // // // // 처음 작성한 코드는 boolean answer = false; String str = "eiaoalskdfn"; String str1 = str.toLowerCase(); //그냥 str.toLowerCase();는 적용이안된다. 새로운 변수에 할당해줘야 한다. for (int i = 0; i < str1.length(); i++) { if (str1.charAt(i) == 'a' && str1.charAt(i + 4) == 'b') { answer = true; break; } else if .. 2022. 11. 25.
11.24 시간복잡도, Greedy, 구현 시간복잡도를 표현하는 방식은 여러가지다. 그중 가장 많이 쓰이는 Big-O 기법에대해 살펴보겠다. ㅇ O(1) constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나진 않는다. ㅇ O(n) linear complexity. 입력값이 증가함에 따라 시간증가. 입력값 1증가 2초증가하면 O(2n) ㅇ O(log n) logarithmic complexity. BST처럼 경우의수를 절반씩 줄어든다. 입력값이 크면클수록 빠르다. O(n)보다 빠를수도 있다. ㅇ O(n^2) quadratic complexity. 입력값늘때마다 n^2만큼 시간이 늘어남. ㅇ O(2^n) exponential complexity. 가장 느린 시간복잡도를 가진다. 복리라고 생각하면 편함. ㅇ Greedy A.. 2022. 11. 25.
11.22 자료구조-Tree, 그래프, BinarySearchTree(BST), BFS/DFS ㅇ Tree 루트 라는 꼭지점 데이터에서 시작해 간선(edge)로 연결시킨다. 부모노드, 자식노드가 존재하고 자식이 없는 노드는 리프노드라고 한다. 깊이 : 루트 - 0, 그밑의 노드들 - 1, . . . 레벨 : 같은 깊이를 가진 노드들을 묶음 높이 - 리프노드를 기준으로 루트까지의 길이 서브트리 - 루트에서 뻗어 나오는 큰 트리의 내부에 트리구조를 갖춘 작은 트리 ㅇ 그래프 우리가 흔히 아는 수학적인 그런 그래프와는 거리가 멀다. 여러개의 점들이 복잡하게 연결되어 있는 관계를 표현한 자료구조다. 직접적 관계는 두 점 사이를 이어주는 선이 있고, 간접적인 관계는 몇개의 점과 선에 걸쳐 이어진다. 하나의 점은 정점(vertex), 하나의 선은 간선(edge)라고 함. ㅇ 그래프의 표현 방식 인접행렬 - .. 2022. 11. 25.
11.21 자료구조 - Stack, Queue 나도모르게 블로깅이 밀렸다. 정신차리고 다시 해야겠다. ㅇ 자료구조 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것. 대부분의 자료구조는 문제해결에 특화되어있음. 알고리즘 문제에 자주 사용된는자료구조는 Stack, Queue, Tree, Graph ㅇ Stack 말 그대로 쌓이는 자료구조다. 정말 간단히 생각해 프링글스 과자 통이라고 생각하면 된다. 가장 먼저 들어간 자료가 가장 나중에 나오는 후입선출(LIFO - Last In First Out) 구조다. 스택구조에서 데이터를 넣는 것은 push, 꺼내는 것은 pop stack.push(1); stack.push(2); stack.push(3); - - - - - - - - - - - 1 2 3 stack.pop(); stack.pop(); stac.. 2022. 11. 25.

티스토리툴바